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 [math]\displaystyle{ \scriptstyle G }[/math] with a generator [math]\displaystyle{ \scriptstyle g }[/math] of prime order [math]\displaystyle{ \scriptstyle q }[/math] in which the discrete logarithm problem is hard. For example, a Schnorr group can be used. For a group of [math]\displaystyle{ \scriptstyle n }[/math] participants, the protocol executes in two rounds.
Round 1: each participant [math]\displaystyle{ \scriptstyle i }[/math] selects a random value [math]\displaystyle{ \scriptstyle x_i \,\in_R\, \mathbb{Z}_q }[/math] and publishes the ephemeral public key [math]\displaystyle{ \scriptstyle g^{x_i} }[/math] together with a zero-knowledge proof for the proof of the exponent [math]\displaystyle{ \scriptstyle x_i }[/math]. A detailed description of a method for such proofs is found in RFC 8235.
After this round, each participant computes:
- [math]\displaystyle{ g^{y_i} = \prod_{j\lt i} g^{x_j} / \prod_{j\gt i} g^{x_j} }[/math]
Round 2: each participant [math]\displaystyle{ \scriptstyle i }[/math] publishes [math]\displaystyle{ \scriptstyle g^{c_i y_i} }[/math] and a zero-knowledge proof for the proof of the exponent [math]\displaystyle{ \scriptstyle c_i }[/math]. Here, the participants chose [math]\displaystyle{ \scriptstyle c_i \;=\; x_i }[/math] 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 [math]\displaystyle{ \scriptstyle \prod g^{c_i y_i} }[/math]. If no one vetoed, each will obtain [math]\displaystyle{ \scriptstyle \prod g^{c_i y_i} \;=\; 1 }[/math]. On the other hand, if one or more participants vetoed, each will have [math]\displaystyle{ \scriptstyle \prod g^{c_i y_i} \;\neq\; 1 }[/math].
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, [math]\displaystyle{ \scriptstyle \sum {x_i \cdot y_i} \;=\; 0 }[/math]. For example, if there are three participants, then [math]\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 }[/math]. 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
- ↑ F. Hao, P. Zieliński. A 2-round anonymous veto protocol. Proceedings of the 14th International Workshop on Security Protocols, 2006.
- ↑ David Chaum. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability Journal of Cryptology, vol. 1, No, 1, pp. 65-75, 1988
 |  |
