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. 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
with a generator
of prime order
in which the discrete logarithm problem is hard. For example, a
Schnorr group A Schnorr group, proposed by Claus P. Schnorr, is a large prime-order subgroup of \mathbb_p^\times, the multiplicative group of integers modulo p for some prime p. To generate such a group, generate p, q, r such that
:p = qr + 1
with p, q prime. ...
can be used. For a group of
participants, the protocol executes in two rounds.
Round 1: each participant
selects a random value
and publishes the ephemeral public key
together with a
zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...
for the proof of the exponent
. A detailed description of a method for such proofs is found in .
After this round, each participant computes:
:
Round 2: each participant
publishes
and a
zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...
for the proof of the exponent
. Here, the participants chose
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
. If no one vetoed, each will obtain
. On the other hand, if one or more participants vetoed, each will have
.
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,
. For example, if there are three participants, then
. 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]
The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability
Journal of Cryptology, vol. 1, No, 1, pp. 65-75, 1988
References
{{DEFAULTSORT:Anonymous Veto Network
Public-key cryptography
Zero-knowledge protocols