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 [F. Hao, P. Zieliński. [http://www.cl.cam.ac.uk/~fh240/pdf/avnet.pdf A 2-round anonymous veto protocol] . "Proceedings of the 14th International Workshop on Security Protocols, 2006.] . It presents an efficient solution to the Dining cryptographers problem.

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

After this round, each participant computes:

.

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 participant chose $c\_i=x\_i$ if he wants to send a "0" bit (no veto), or a random value if he wants to send a "1" bit (veto).

After round 2, each participant computes $prod\; g^\{c\_i\; y\_i\}$. If no one vetoed, he will obtain $prod\; g^\{c\_i\; y\_i\}=1$. On the other hand, if one or more participants vetoed, he will have $prod\; g^\{c\_i\; y\_i\}\; eq\; 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 [David Chaum. [http://dx.doi.org/10.1007/BF00206326 The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability] Journal of Cryptology, vol. 1, No, 1, pp. 65-75, 1988] .

References