Anonymous veto network

Template:Short description In cryptography, the anonymous veto network (or AV-net) is a multi-party secure computation protocol to compute the boolean-OR function. It was first proposed by Feng Hao and Piotr Zieliński in 2006. This protocol presents an efficient solution to the Dining cryptographers problem.

A related protocol that securely computes a boolean-count function is open vote network (or OV-net).

Description

All participants agree on a group $G$ with a generator $g$ of prime order $q$ in which the discrete logarithm problem is hard. For example, a Schnorr group can be used. For a group of $n$ participants, the protocol executes in two rounds.

Round 1: each participant $i$ selects a random value $x_i{\in }_R{\mathbb{Z}}_q$ and publishes the ephemeral public key $g^{x_i}$ together with a zero-knowledge proof for the proof of the exponent $x_i$. A detailed description of a method for such proofs is found in Template:IETF RFC.

After this round, each participant computes:

$g^{y_i}=\prod _{j<i}{g}^{x_j}/\prod _{j>i}{g}^{x_j}$

Round 2: each participant $i$ publishes $g^{c_i{y}_i}$ and a zero-knowledge proof for the proof of the exponent $c_i$. Here, the participants chose $c_i=x_i$ if they want to send a "0" bit (no veto), or a random value if they want to send a "1" bit (veto).

After round 2, each participant computes $\prod g^{c_i{y}_i}$. If no one vetoed, each will obtain $\prod g^{c_i{y}_i}=1$. On the other hand, if one or more participants vetoed, each will have $\prod g^{c_i{y}_i}\ne 1$.

The protocol design

The protocol is designed by combining random public keys in such a structured way to achieve a vanishing effect. In this case, $\sum x_i\cdot y_i=0$. For example, if there are three participants, then $x_1\cdot y_1+x_1\cdot y_2+x_3\cdot y_3=x_1\cdot (-x_2-x_3)+x_2\cdot (x_1-x_3)+x_3\cdot (x_1+x_2)=0$. A similar idea, though in a non-public-key context, can be traced back to David Chaum's original solution to the Dining cryptographers problem.