Anonymous veto network

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{Z}_q and publishes the ephemeral public key \scriptstyle g^{x_i} 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^{y_i} = \prod_{ji} g^{x_j}

Round 2: each participant \scriptstyle i publishes \scriptstyle g^{c_i y_i} 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^{c_i y_i}. If no one vetoed, each will obtain \scriptstyle \prod g^{c_i y_i} ;=; 1. On the other hand, if one or more participants vetoed, each will have \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, \scriptstyle \sum {x_i \cdot y_i} ;=; 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.

References

References

1. F. Hao, P. Zieliński. [http://homepages.cs.ncl.ac.uk/feng.hao/files/av_net.pdf A 2-round anonymous veto protocol]. ''Proceedings of the 14th International Workshop on Security Protocols'', 2006.
2. David Chaum. [https://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