Daily Archives: 2006-04-05

AV-net – a new solution to the Dining Cryptographers Problem

Last week in the 14th International Workshop on Security Protocols, I presented a talk on the paper: A 2-round Anonymous Veto Protocol (joint work with Piotr Zieliński), which interested some people. The talk was about solving the following crypto puzzle.

In a room where all discussions are public, the Galactic Security Council must decide whether to invade an enemy planet. One delegate wishes to veto the measure, but worries about sanctions from the pro-war faction. This presents a dilemma: how can one anonymously veto the decision?

This veto problem is essentially the same as the Dining Cryptographers Problem first proposed by Chaum in 1988 — how to compute the Boolean-OR securely. However, Chaum’s classic solution, DC-net, assumes unconditionally secure private channels among participants, which don’t exist in our problem setting. Our protocol, Anonymous Veto Network (or AV-net), not only overcomes all the major limitations in DC-net, but also is very efficient in many aspects (probably optimal).