The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability
📜 Abstract
Keeping confidential who sends which messages, in a world where any physical transmission can be traced to its origin, seems impossible. The solution presented here is unconditionally or cryptographically secure, depending on whether it is based on one-time-use keys or on public keys, respectively. It can be adapted to address efficiently a wide variety of practical considerations.
✨ Summary
Summary
David Chaum introduces the dining cryptographers network, or DC-net, as a method for achieving anonymous communication even when individual physical transmissions could otherwise be traced. In the basic protocol, participants share random secret bits pairwise. Each participant publicly announces the XOR of the secret bits they hold, while a sender inverts their announcement. Because every shared secret contributes twice to the overall XOR, the aggregate output reveals whether an odd or even number of participants transmitted, but does not reveal which participant transmitted. With one-time-use random keys, the sender-untraceability guarantee is unconditional; with keys established or expanded using public-key techniques, the guarantee is computational.
The protocol is generalized from the three-person dinner example to arbitrary connected key-sharing graphs. Participants correspond to vertices and shared keys to edges. An observer’s anonymity sets are the connected components that remain after removing edges known to that observer. Chaum proves, using the incidence matrix of the graph over GF(2), that the observed outputs reveal no more information about the participants in an anonymity set than the parity of their inversions. Thus, within an appropriate connected component, individual senders remain indistinguishable from the observer’s perspective.
The paper analyzes how graph topology affects collusion resistance. Complete graphs provide strong protection against individual observers but require a quadratic number of shared keys. Sparse graphs reduce setup costs but can expose messages when colluders control separating vertices or edges. The paper also discusses hierarchical key-sharing structures, ring and broadcast implementations, message collisions, key establishment, encryption for recipient confidentiality, digital signatures for authentication, and mechanisms for detecting or excluding disruptive participants. Recipient untraceability may require a reliable broadcast mechanism, while sender untraceability follows from the masking properties of the shared keys.
The paper influenced subsequent anonymous-communication research by establishing DC-nets as a foundational construction for anonymous broadcast and by identifying their principal engineering limitations, especially collisions, bandwidth costs, and denial-of-service through disruption. Later systems extended the construction with accountability and verifiability. Dissent uses shuffled-send DC-nets to support anonymous group messaging while making disruptive behavior attributable to a group member. (people.eecs.berkeley.edu) Verdict applies public-key cryptography and zero-knowledge proofs to create proactively verifiable DC-nets that can detect and exclude misbehavior before it disrupts communication. (people.eecs.berkeley.edu) The DC protocol has also been used as a benchmark for formal, machine-assisted proofs of anonymity, and later work has adapted DC-net ideas to applications including secure aggregation. (cl.cam.ac.uk)