The Dining Cryptographers in CyberspaceAlan Westrope, 1998
In 1988, Dr. David Chaums paper The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability was published in the Journal of Cryptology. The paper begins:
Three cryptographers are sitting down to dinner at their favorite three-star restaurant. Their waiter informs them that arrangements have been made with the maitre dhotel for the bill to be paid anonymously. One of the cryptographers might be paying for the dinner, or it might have been NSA (U.S. National Security Agency). The three cryptographers respect each others right to make an anonymous payment, but they wonder if NSA is paying. They resolve their uncertainty fairly by carrying out the following protocol:
Ive cobbled together a simple demonstration of this scenario, as it might be seen by a hidden camera in the ceiling above the table. Clicking the Toss coins button simulates a round of coin tosses, using oversized coins with heads represented by 1 and tails by 0. The number of participants can be adjusted from 3 to 9, helping to illustrate that there will always be an even number of differences reported, provided everyone responds truthfully. After a coin toss, you can press the first letter of any participants name to have them state the opposite of what they see, producing an odd number of differences without enabling anyone else to learn who the liar is. (If youre new to all this and cant make heads or tails of it, run the program at first with only 3 participants, as described above.)
Objections raised by this simplistic demo can be answered by reading the complete paper, as well as related papers by Dr. Chaum and other mathematicians, including M. Waidner and B. Pfitzmanns papers, The Dining Cryptographers in the Disco: Unconditional Sender and Recipient Untraceability with Computationally Secure Serviceability, Advances in CryptologyEUROCRYPT 89 Proceedings, Springer-Verlag, 1990, and Unconditional Concealment with Cryptographic Ruggedness, VIS 91 Verlassliche Informationsysteme Proceedings, Darmstadt, Germany, March 1991. Consult the bibliography in the paper or a source such as Bruce Schneiers Applied Cryptography for additional information and references.
The paper has sparked discussion on the Internet, where the protocol could be extended to dozens of participants worldwide, each tossing a virtual coini.e., transmitting a single bitmany times a second. Computers typically represent a single character with 8 bits, so Alice could transmit the letter A, whose 8-bit binary code is 01000001, in 8 rounds, by lying about the coin toss in rounds 2 and 8. A few thousand rounds would suffice for Alice (or Aldrich) to transmit a listperhaps encrypted with Bobs (or Boriss) public key, so that only he could read itof double agents to be assassinated. Digitized images and audio could be sent as well. The protocol could also be used in conjunction with a digital cash system, like those designed by Dr. Chaum and his colleague Stefan Brands, for untraceable financial transactions, bringing what novelist Thomas Pynchon called organic markets, carefully styled black by the professionalsor perhaps even the intriguing proposals of Jim Bellto the agora of cyberspace.
An Internet implementation, or DC-Net, would have many advantages. Its topology need not be limited to the circle shown here, and the problem of two or more participants attempting to transmit simultaneously is easily solved with the backoff procedure used by the Ethernet CSMA/CD protocol. Regardless of the number of participants, any pair could privately flip coins and report their results without physically hiding behind menus. Indeed, the paper posits that in each round, every participant shares a private random bit with every other participant, and reports the sum modulo 2 of all the shared bits. (For non-math-mavens, this is equivalent to responding with zero if two bits are identical, or with one if theyre different, then adding up all the ones and dividing this total by two, leaving a remainder of zero or one.) Just as in the demonstration, the final result modulo 2 will always be zero, unless someone inverts a result they witness. Instead of flipping coins, each pair of DC-Net participants could get their sequence of random bits from files (e.g., *.tar.gz archives or other large binaries) retrieved over the Internet.
Sadly, little progress has been made in implementing DC-Nets. However, for years after its publication the paper basically gathered dust on the shelves of academic libraries, whereas its now freely available on the Web, and is often cited when unconditional [...] untraceability is discussed.Acknowledgements: In addition to those mentioned above, thanks to J. Orlin Grabbe, David Friedman, and Tim May.