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.[1] 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 ${\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. For a group of ${\displaystyle \scriptstyle n}$ participants, the protocol executes 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 exponent ${\displaystyle \scriptstyle x_{i}}$. A detailed description of a method for such proofs is found in RFC 8235.

After this round, each participant computes:

${\displaystyle g^{y_{i}}=\prod _{j<i}g^{x_{j}}/\prod _{j>i}g^{x_{j}}}$

Round 2: each participant ${\displaystyle \scriptstyle i}$ publishes ${\displaystyle \scriptstyle g^{c_{i}y_{i}}}$ and a zero-knowledge proof for the proof of the exponent ${\displaystyle \scriptstyle c_{i}}$. Here, the participants chose ${\displaystyle \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 ${\displaystyle \scriptstyle \prod g^{c_{i}y_{i}}}$. If no one vetoed, each will obtain ${\displaystyle \scriptstyle \prod g^{c_{i}y_{i}}\;=\;1}$. On the other hand, if one or more participants vetoed, each will have ${\displaystyle \scriptstyle \prod g^{c_{i}y_{i}}\;\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, ${\displaystyle \scriptstyle \sum {x_{i}\cdot y_{i}}\;=\;0}$. For example, if there are three participants, then ${\displaystyle \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.[2]

References

1. F. Hao, P. Zieliński. A 2-round anonymous veto protocol. Proceedings of the 14th International Workshop on Security Protocols, 2006.
2. David Chaum. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability Journal of Cryptology, vol. 1, No, 1, pp. 65-75, 1988