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^[1]. It presents an efficient solution to the Dining cryptographers problem.

Description[]

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

Round 1: each participant ${\displaystyle i}$ selects a random value ${\displaystyle x_i \in_R \mathbb{Z}_q}$ and publishes the ephemeral public key ${\displaystyle g^{x_i}}$ together with a Zero-knowledge proof for the proof of the exponent ${\displaystyle x_i }$.

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