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 d’hotel 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 other’s right to make an anonymous payment, but they wonder if NSA is paying. They resolve their uncertainty fairly by carrying out the following protocol:

Each cryptographer flips an unbiased coin behind his menu, between him and the cryptographer on his right, so that only the two of them can see the outcome. Each cryptographer then states aloud whether the two coins he can see—the one he flipped and the one his left-hand neighbor flipped—fell on the same side or on different sides. If one of the cryptographers is the payer, he states the opposite of what he sees. An odd number of differences uttered at the table indicates that a cryptographer is paying; an even number indicates that NSA is paying (assuming that the dinner was paid for only once). Yet if a cryptographer is paying, neither of the other two learns anything from the utterances about which cryptographer it is.

I’ve 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 participant’s 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 you’re new to all this and can’t 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. Pfitzmann’s papers, “The Dining Cryptographers in the Disco: Unconditional Sender and Recipient Untraceability with Computationally Secure Serviceability,” Advances in Cryptology—EUROCRYPT ’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 Schneier’s 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 coin—i.e., transmitting a single bit—many 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 list—perhaps encrypted with Bob’s (or Boris’s) public key, so that only he could read it—of 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 professionals”—or perhaps even the intriguing proposals of Jim Bell—to 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 they’re 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 it’s now freely available on the Web, and is often cited when “unconditional [...] untraceability” is discussed.