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).

About Feng Hao

Feng Hao is currently a professor of security engineering in the Department of Computer Science, University of Warwick, UK. He graduated from the Computer Lab, University of Cambridge with a PhD in 2007 under the join supervision of Prof Ross Anderson and Prof John Daugman.

2 thoughts on “AV-net – a new solution to the Dining Cryptographers Problem

  1. A small problem that I think someone brought up in the workshop itself – wouldn’t this primitive reveal how many vetoes were placed?

  2. No. A guy did mention a possible attack, but after I explained to him, he realized that it didn’t work.

Leave a Reply

Your email address will not be published. Required fields are marked *