In cryptography, the anonymous veto network (or AV-net) is a multi-party secure computation protocol to compute the boolean-OR function. It presents an efficient solution to the Dining cryptographers problem.
All participants agree on a group
G
with a generator
g
of prime order
q
in which the discrete logarithm problem is hard. For example, a Schnorr group can be used. For a group of
n
participants, the protocol executes in two rounds.
Round 1: each participant
i
selects a random value
x
i
∈
R
Z
q
and publishes the ephemeral public key
g
x
i
together with a zero-knowledge proof for the proof of the exponent
x
i
. A detailed description of a method for such proofs is found in the article Fiat-Shamir heuristic.
After this round, each participant computes:
g
y
i
=
∏
j
<
i
g
x
j
/
∏
j
>
i
g
x
j
Round 2: each participant
i
publishes
g
c
i
y
i
and a zero-knowledge proof for the proof of the exponent
c
i
. Here, the participants chose
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
∏
g
c
i
y
i
. If no one vetoed, each will obtain
∏
g
c
i
y
i
=
1
. On the other hand, if one or more participants vetoed, each will have
∏
g
c
i
y
i
≠
1
.
The protocol is designed by combining random public keys in such a structured way to achieve a vanishing effect. In this case,
∑
x
i
⋅
y
i
=
0
. For example, if there are three participants, then
x
1
⋅
y
1
+
x
1
⋅
y
2
+
x
3
⋅
y
3
=
x
1
⋅
(
−
x
2
−
x
3
)
+
x
2
⋅
(
x
1
−
x
3
)
+
x
3
⋅
(
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.
