Open vote network – Wikipedia

In cryptography, the open vote network (or OV-net) is a secure multi-party computation protocol to compute the boolean-count function: namely, given a set of binary values 0/1 in the input, compute the total count of ones without revealing each individual value. This protocol was proposed by Feng Hao, Peter Ryan, and Piotr Zieliński in 2010.^[1] It extends Hao and Zieliński’s anonymous veto network protocol by allowing each participant to count the number of veto votes (i.e., input one in a boolean-OR function) while preserving the anonymity of those who have voted. The protocol can be generalized to support a wider range of inputs beyond just the binary values 0 and 1.

Description[edit]

All participants agree on a group

${displaystyle scriptstyle G}$

with a generator

${displaystyle scriptstyle g}$

of prime order

${displaystyle scriptstyle q}$

in which the discrete logarithm problem is hard. For example, a Schnorr group can be used. Assume there are

${displaystyle scriptstyle n}$

participants. Unlike other secure multi-party computation protocols that typically require pairwise secret and authenticated channels between participants in addition to an authenticated public channel, OV-net only requires an authenticated public channel available to every participant. Such a channel may be realized by using digital signatures. The protocol runs in two rounds.

Round 1: each participant

${displaystyle scriptstyle i}$

selects a random value

${displaystyle scriptstyle x_{i},in _{R},mathbb {Z} _{q}}$

and publishes the ephemeral public key

${displaystyle scriptstyle g^{x_{i}}}$

together with a zero-knowledge proof for the proof of the knowledge of the exponent

${displaystyle scriptstyle x_{i}}$

. Such proofs may be realized by using Schnorr non-interactive zero-knowledge proofs as described in RFC 8235.

After this round, each participant computes:

${displaystyle g^{y_{i}}=prod _{ji}g^{x_{j}}}$

${displaystyle scriptstyle i}$

publishes

${displaystyle scriptstyle g^{x_{i}y_{i}}g^{v_{i}}}$

where

${displaystyle scriptstyle v_{i}}$

is either 0 or 1, together with a 1-out-of-2 zero knowledge proof for the proof that

${displaystyle scriptstyle v_{i}}$

is one of

${displaystyle scriptstyle {0,1}}$

. Such 1-out-of-2 proofs may be realized by using Cramer, Gennaro, and Schoenmakers’ zero-knowledge proof technique.^[2]

After round 2, each participant computes

${displaystyle scriptstyle prod _{i}g^{x_{i}y_{i}}g^{v_{i}}=g^{sum _{i}v_{i}}}$

. Note that all

${displaystyle scriptstyle x_{i}}$

values vanish because

${displaystyle scriptstyle sum _{i}{x_{i}y_{i}}=0}$

. The exponent

${displaystyle scriptstyle sum _{i}v_{i}}$

represents the count of ones. As it is usually a small number, the count can be computed by exhaustive search.

Overall, the 2-round efficiency is the theoretically best possible. In terms of the computational load and bandwidth usage, OV-net is also the most efficient among related techniques.^[1]

Maximum secrecy[edit]

The OV-net protocol guarantees the secrecy of an input bit unless all other input bits are known. The protection of secrecy is the maximum since when all other bits are known, the remaining bit can always be computed by subtracting the values of known input bits from the output of the boolean-count function.

Applications[edit]

A straightforward application of OV-net is to build a boardroom voting system, where the election is run by voters themselves. For a single candidate election, each voter sends either “No” or “Yes”, which correspond to 0 and 1. Every voter, as well as an observer, can tally the “Yes” votes by themselves without needing any tallying authority.

There are standard methods to extend a single-candidate election to support multiple candidates. A straightforward method is to run the single-candidate election in parallel for multiple candidates, and each voter casts “Yes/No” to each of the candidates. Additional zero-knowledge proofs are needed if the voter is limited to vote for only one candidate. Another method is to modify the encoding of candidates: instead of using 0 and 1 for “No” and “Yes” in a single-candidate election, encode each candidate with a unique number such that the tally for each candidate can be unambiguously computed. In this case, a more general 1-out-of-n zero-knowledge proof is used instead where n is the number of candidates.

Implementation[edit]

A prototype implementation of OV-net was presented by McCorry, Shahandashti, and Hao at Financial Cryptography’17 as a smart contract over Ethereum’s blockchain.^[3] The source code is publicly available. This implementation forms part of the Newcastle University team’s solution on “Removing Trusted Tallying Authorities: Self-Enforcing E-Voting over Ethereum“, which was awarded third place in the 2016 Economist Cybersecurity Challenge jointly organized by The Economist and Kaspersky Lab.

References[edit]

1. ^ ^{a b} Hao, F.; Ryan, P.Y.A.; Zieliński, P. (2010). “Anonymous voting by two-round public discussion” (PDF). IET Information Security. 4 (2): 62. doi:10.1049/iet-ifs.2008.0127.
2. ^ Cramer, Ronald; Gennaro, Rosario; Schoenmakers, Berry (1997-05-11). A Secure and Optimally Efficient Multi-Authority Election Scheme. Advances in Cryptology — EUROCRYPT ’97. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. pp. 103–118. CiteSeerX 10.1.1.43.5825. doi:10.1007/3-540-69053-0_9. ISBN 978-3540690535.
3. ^ Patrick McCorry, Siamak F. Shahandashti and Feng Hao (2017). “A Smart Contract for Boardroom Voting with Maximum Voter Privacy” (PDF). Financial Cryptography, 2017.