Anonymous veto network explained

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

\scriptstyleG

with a generator

\scriptstyleg

of prime order

\scriptstyleq

in which the discrete logarithm problem is hard. For example, a Schnorr group can be used. For a group of

\scriptstylen

participants, the protocol executes in two rounds.

Round 1: each participant

\scriptstylei

selects a random value

\scriptstylex_i\in_RZ_q

and publishes the ephemeral public key

\scriptstyle

	x_i
g

together with a zero-knowledge proof for the proof of the exponent

\scriptstylex_i

. A detailed description of a method for such proofs is found in .

After this round, each participant computes:

	y_i
g

=\prod_j<i

	x_j
g

/\prod_j>i

	x_j
g

Round 2: each participant

\scriptstylei

publishes

\scriptstyle

	c_iy_i
g

and a zero-knowledge proof for the proof of the exponent

\scriptstylec_i

. Here, the participants chose

\scriptstylec_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

	c_iy_i
g

. If no one vetoed, each will obtain

\scriptstyle\prod

	c_iy_i
g

= 1

. On the other hand, if one or more participants vetoed, each will have

\scriptstyle\prod

	c_iy_i
g

≠ 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 ⋅ y_i} = 0

. For example, if there are three participants, then

\scriptstylex₁ ⋅ y₁+x₁ ⋅ y₂+x₃ ⋅ y₃ = x₁ ⋅ (-x₂-x₃₎+x₂ ⋅ (x₁-x₃₎+x₃ ⋅ (x₁+x₂₎ = 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

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