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.

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

• David Chaum (1988). "The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability". Journal of Cryptology 1 (1): 65–75. doi:10.1007/BF00206326. http://www.cs.cornell.edu/People/egs/herbivore/dcnets.html. 

• P. Golle and A. Juels. Dining Cryptographers Revisited. In proc. of Eurocrypt 2004.