Anonymous veto network

From Glitchdata
Jump to navigation Jump to search

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 <math>\scriptstyle G</math> with a generator <math>\scriptstyle g</math> of prime order <math>\scriptstyle q</math> in which the discrete logarithm problem is hard. For example, a Schnorr group can be used. For a group of <math>\scriptstyle n</math> participants, the protocol executes in two rounds.

Round 1: each participant <math>\scriptstyle i</math> selects a random value <math>\scriptstyle x_i \,\in_R\, \mathbb{Z}_q</math> and publishes the ephemeral public key <math>\scriptstyle g^{x_i}</math> together with a zero-knowledge proof for the proof of the exponent <math>\scriptstyle x_i</math>. A detailed description of a method for such proofs is found in the article Fiat-Shamir heuristic.

After this round, each participant computes:

<math>g^{y_i} = \prod_{j<i} g^{x_j} / \prod_{j>i} g^{x_j}</math>

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

  1. F. Hao, P. Zieliński. A 2-round anonymous veto protocol. Proceedings of the 14th International Workshop on Security Protocols, 2006.
  2. David Chaum. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability Journal of Cryptology, vol. 1, No, 1, pp. 65-75, 1988