Dining cryptographers problem
Encyclopedia
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
.
(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
, A and C share 
, and B and C share 
.
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
, B would announce 
, and C would announce 
. On the other hand, if A paid, he would announce 
.
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.
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.
1. Collision - If two cryptographers paid for the dinner, their messages will cancel each other out, and the final XOR result will be
. 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
. 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.
David Chaum
David Chaum is the inventor of many cryptographic protocols, including blind signature schemes, commitment schemes, and digital cash. In 1982, Chaum founded the International Association for Cryptologic Research , which currently organizes academic conferences in cryptography research...
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
Dining philosophers problem
In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them....
.
Description
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 AgencyNational Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
(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
, A and C share , and B and C share .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
, B would announce , and C would announce . On the other hand, if A paid, he would announce .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 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
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
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
. 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
. 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
Anonymous veto network
In cryptography, the Anonymous Veto Network is a multi-party secure computation protocol to compute the boolean-OR function. It presents an efficient solution to the Dining cryptographers problem.-Description:...
solution.