Anonymous Veto Network

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 $\scriptstyle G$ with a generator $\scriptstyle g$ of prime order $\scriptstyle q$ in which the discrete logarithm problem is hard. For example, a Schnorr group can be used. For a group of $\scriptstyle n$ participants, the protocol executes in two rounds.

Round 1: each participant $\scriptstyle i$ selects a random value $\scriptstyle x_i \,\in_R\, \mathbb_q$ and publishes the ephemeral public key $\scriptstyle g^$ together with a zero-knowledge proof for the proof of the exponent $\scriptstyle x_i$. A detailed description of a method for such proofs is found in .

After this round, each participant computes:

:$g^ = \prod_ g^ / \prod_ g^$

Round 2: each participant $\scriptstyle i$ publishes $\scriptstyle g^$ and a zero-knowledge proof for the proof of the exponent $\scriptstyle c_i$. Here, the participants chose $\scriptstyle 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 $\scriptstyle \prod g^$. If no one vetoed, each will obtain $\scriptstyle \prod g^ \;=\; 1$. On the other hand, if one or more participants vetoed, each will have $\scriptstyle \prod g^ \;\neq\; 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, $\scriptstyle \sum \;=\; 0$. For example, if there are three participants, then $\scriptstyle 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.David Chaum
The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability
Journal of Cryptology, vol. 1, No, 1, pp. 65-75, 1988

References

{{DEFAULTSORT:Anonymous Veto Network
Public-key cryptography
Zero-knowledge protocols