Dining cryptographers problem
In cryptography, the dining cryptographers problem studies how to perform a secure multi-party computation of the boolean-XOR function.
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In cryptography, the dining cryptographers problem studies how to perform a secure multi-party computation of the boolean-XOR function. David Chaum first proposed this problem in the early 1980s and used it as an illustrative example to show that it was possible to send anonymous messages with unconditional sender and recipient untraceability.
Anonymous communication networks based on this problem are often referred to as DC-nets (where DC stands for "dining cryptographers"). Despite the word dining, the dining cryptographers problem is unrelated to the dining philosophers problem. Supposing none of the cryptographers paid, then A announces 1 \oplus 0 = 1 , B announces 1 \oplus 1 = 0 , and C announces 0 \oplus 1 = 1 .
On the other hand, if A paid, she announces \lnot (1 \oplus 0) = 0 . The three public announcements combined reveal the answer to their question. One simply computes the XOR of the three bits announced.
If the result is 0, it implies that none of the cryptographers paid (so the NSA must have paid the bill). Otherwise, one of the cryptographers paid, but their identity remains unknown to the other cryptographers. David Chaum coined the term dining cryptographers network, or DC-net, for this protocol.
Limitations
The DC-net protocol is simple and elegant. It has several limitations, however, some solutions to which have been explored in follow-up research (see the References section below). 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.
Disruption : Any malicious cryptographer who does not want the group to communicate successfully can jam the protocol so that the final XOR result is useless, simply by sending random bits instead of the correct result of the XOR. This problem occurs because the original protocol was designed without using any public key technology and lacks reliable mechanisms to check whether participants honestly follow the protocol.
Complexity : The protocol requires pairwise 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.
A related anonymous veto network algorithm computes the logical OR of several users' inputs, rather than a logical XOR as in DC-nets, which may be useful in applications to which a logical OR combining operation is naturally suited.
History
David Chaum first thought about this problem in the early 1980s. The first publication that outlines the basic underlying ideas is his. The journal version appeared in the very first issue of the Journal of Cryptology.
Generalizations
DC-nets are readily generalized to allow for transmissions of more than one bit per round, for groups larger than three participants, and for arbitrary "alphabets" other than the binary digits 0 and 1, as described below.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1334072905 under CC BY-SA 4.0; modifications have been made.