Dining cryptographers problem

In cryptography, the dining cryptographers problem studies how to perform a secure multi-party computation of the boolean-OR function. David Chaum first proposed this problem in 1988, and used it as an illustrative example to show it was possible to send anonymous messages with unconditional sender and recipient untraceability.

Despite the word "dining", the dining cryptographers problem is unrelated to the dining philosophers problem.

Contents

Description

Dining cryptographers problem illustration

Three cryptographers gather around a table for dinner. The waiter informs them that the meal has been paid by someone, who could be one of the cryptographers or the National Security Agency (NSA). The cryptographers respect each other's right to make an anonymous payment, but want to find out whether the NSA paid. So they decide to execute a two-stage protocol.

In the first stage, every two cryptographers establish a shared one-bit secret, say by tossing a coin behind a menu or by writing down a secret bit and then privately XORing it with each other participant's secret bit in turn to generate the requisite shared secrets. Suppose, after the coin tossing, cryptographer A and B share a secret bit 1, A and C share 0, and B and C share 1.

In the second stage, each cryptographer publicly announces a bit, which is the Exclusive OR (XOR) of the shared bits he holds if he didn't pay the meal, or the opposite of the XOR if he paid. Suppose none of the cryptographers paid, then A would announce 1 \oplus 0 = 1, B would announce 1 \oplus 1 = 0, and C would announce 0 \oplus 1 = 1. On the other hand, if A paid, he would announce \lnot{(1 \oplus 0)} = 0.

After the second stage is the truth revealing. One simply performs XOR of all the announced bits. If the result is 0, then it implies that none of the cryptographers paid (so NSA must have paid). Otherwise, it would imply one of the cryptographers paid, but his identity remains unknown to the other cryptographers.

The above protocol was named by David Chaum as the Dining Cryptographers network, or DC-net.

Generalization

The protocol can be generalized to a group of n participants, each with a shared secret key in common with each other participant. In each round of the protocol, if a participant wants to transmit an untraceable message to the group they invert their publicly announced bit.

The participants can be visualized as a fully connected graph with the vertices representing the participants and the edges representing their shared secret keys.

Limitations

The DC-net protocol is simple and elegant. It, however, has several limitations.

1. Collision - If two cryptographers paid for the dinner, their messages will cancel each other out, and the final XOR result will be 0. This is called a collision, and allows only one participant to transmit at a time using this protocol. In a more general case, a collision happens as long as any even number of participants send messages. The measure suggested by David Chaum is to re-transmit the message once a collision is detected, but the paper does not explain exactly how to arrange the re-transmission.

2. Disruption - The cryptographer who last announces the bit has the advantage of manipulating the final result. For example, if he is dishonest, he can jam the protocol so that the final XOR result is always 0. This problem occurs because the original protocol was designed without using any public key technology; but as a downside, the protocol lacks reliable mechanisms to check whether participants honestly follow the protocol.

3. Complexity - The protocol requires pair-wise shared secret keys between the participants, which may be problematic if there are many participants. Also, though the DC-net protocol is "unconditionally secure", it actually depends on the assumption that "unconditionally secure" channels already exist between pairs of the participants, which is not easy to achieve in practice.

All of the above limitations are addressed in the Anonymous veto network solution.

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Dining cryptographers protocol — The dining cryptographers protocol is a method of anonymous communication. It offers untraceability of both the sender and the recipient.The method is as follows: three or more cryptographers (nodes) arrange themselves around a circular dinner… …   Wikipedia

  • Dining cryptographers protocol/Rewrite — Problem Statement Dining Cryptographers A group of cryptographers is enjoying dinner at a local restaurant. Upon requesting their bill, the cryptographers are surprised to learn from their host that payment for the dinner has already been… …   Wikipedia

  • Anonymous veto network — In cryptography, the Anonymous Veto Network (or AV net) is a multi party secure computation protocol to compute the boolean OR function [F. Hao, P. Zieliński. [http://www.cl.cam.ac.uk/ fh240/pdf/avnet.pdf A 2 round anonymous veto protocol] .… …   Wikipedia

  • DC — Contents 1 Places 2 Organizations 3 Science and technology 4 …   Wikipedia

  • Anonymous P2P — An anonymous P2P computer network is a particular type of peer to peer network in which the users are anonymous or pseudonymous by default. The primary difference between regular and anonymous networks is in the routing method of their respective …   Wikipedia

  • Bletchley Park — Infobox Museum name = Bletchley Park imagesize = 200 caption = During World War II, codebreakers at Bletchley Park decrypted and interpreted messages from a large number of Axis code and cipher systems, including the German Enigma machine. For… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.