Open vote network

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. 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

All participants agree on a group [math]\displaystyle{ \scriptstyle G }[/math] with a generator [math]\displaystyle{ \scriptstyle g }[/math] of prime order [math]\displaystyle{ \scriptstyle q }[/math] in which the discrete logarithm problem is hard. For example, a Schnorr group can be used. Assume there are [math]\displaystyle{ \scriptstyle n }[/math] 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 [math]\displaystyle{ \scriptstyle i }[/math] selects a random value [math]\displaystyle{ \scriptstyle x_i \,\in_R\, \mathbb{Z}_q }[/math] and publishes the ephemeral public key [math]\displaystyle{ \scriptstyle g^{x_i} }[/math] together with a zero-knowledge proof for the proof of the knowledge of the exponent [math]\displaystyle{ \scriptstyle x_i }[/math]. Such proofs may be realized by using Schnorr non-interactive zero-knowledge proofs as described in RFC 8235.

After this round, each participant computes:

[math]\displaystyle{ g^{y_i} = \prod_{j\lt i} g^{x_j} / \prod_{j\gt i} g^{x_j} }[/math]

Round 2: each participant [math]\displaystyle{ \scriptstyle i }[/math] publishes [math]\displaystyle{ \scriptstyle g^{x_i y_i}g^{v_i} }[/math] where [math]\displaystyle{ \scriptstyle v_i }[/math] is either 0 or 1, together with a 1-out-of-2 zero knowledge proof for the proof that [math]\displaystyle{ \scriptstyle v_i }[/math] is one of [math]\displaystyle{ \scriptstyle \{0, 1\} }[/math]. Such 1-out-of-2 proofs may be realized by using Cramer, Gennaro, and Schoenmakers' zero-knowledge proof technique.

After round 2, each participant computes [math]\displaystyle{ \scriptstyle \prod_i g^{x_i y_i}g^{v_i} = g^{\sum_i v_i} }[/math]. Note that all [math]\displaystyle{ \scriptstyle x_i }[/math] values vanish because [math]\displaystyle{ \scriptstyle \sum_i {x_i y_i} = 0 }[/math]. The exponent [math]\displaystyle{ \scriptstyle \sum_i v_i }[/math] 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.

Maximum secrecy

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

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

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. 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.