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

All participants agree on a group ${\displaystyle \scriptstyle G}${\displaystyle \scriptstyle G} with a generator ${\displaystyle \scriptstyle g}${\displaystyle \scriptstyle g} of prime order ${\displaystyle \scriptstyle q}${\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}${\displaystyle \scriptstyle n} participants, the protocol executes in two rounds.

Round 1: each participant ${\displaystyle \scriptstyle i}${\displaystyle \scriptstyle i} selects a random value ${\displaystyle \scriptstyle x_{i},円\in _{R},円\mathbb {Z} _{q}}${\displaystyle \scriptstyle x_{i},円\in _{R},円\mathbb {Z} _{q}} and publishes the ephemeral public key ${\displaystyle \scriptstyle g^{x_{i}}}${\displaystyle \scriptstyle g^{x_{i}}} together with a zero-knowledge proof for the proof of the exponent ${\displaystyle \scriptstyle x_{i}}${\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}}}${\displaystyle g^{y_{i}}=\prod _{j<i}g^{x_{j}}/\prod _{j>i}g^{x_{j}}}

Round 2: each participant ${\displaystyle \scriptstyle i}${\displaystyle \scriptstyle i} publishes ${\displaystyle \scriptstyle g^{c_{i}y_{i}}}${\displaystyle \scriptstyle g^{c_{i}y_{i}}} and a zero-knowledge proof for the proof of the exponent ${\displaystyle \scriptstyle c_{i}}${\displaystyle \scriptstyle c_{i}}. Here, the participants chose ${\displaystyle \scriptstyle c_{i}\;=\;x_{i}}${\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}}}${\displaystyle \scriptstyle \prod g^{c_{i}y_{i}}}. If no one vetoed, each will obtain ${\displaystyle \scriptstyle \prod g^{c_{i}y_{i}}\;=\;1}${\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}${\displaystyle \scriptstyle \prod g^{c_{i}y_{i}}\;\neq \;1}.

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}${\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}${\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]

• Public-key cryptography
• Zero-knowledge protocols

• Articles with short description
• Short description is different from Wikidata