Cyphernomicon Top
Cyphernomicon 8.11

Anonymity, Digital Mixes, and Remailers:
Dining Cryptographers


   8.11.1. This is effectively the "ideal digital mix," updated from
            Chaum's original hardware mix form to a purely software-based
            form.
   8.11.2. David Chaum's 1988 paper in Journal of Crypology (Vol 1, No
            1) outlines a way for completely untraceable communication
            using only software (no tamper-resistant modules needed)
           - participants in a ring (hence "dining cryptographers")
           - Chaum imagines that 3 cryptographers are having dinner and
              are informed by their waiter that their dinner has already
              been paid for, perhaps by the NSA, or perhaps by one of
              themselves...they wish to determine which of these is true,
              without revealing which of them paid!
           - everyone flips a coin (H or T) and shows it to his neighbor
              on the left
           + everyone reports whether he sees "same" or "different"
             -  note that with 2 participants, they both already know
                the other's coin (both are to the left!)
           - however, someone wishing to send a message, such as Chaum's
              example of  "I paid for dinner," instead says the opposite
              of what he sees
           + some analysis of this (analyze it from the point of view of
              one of the cryptographers) shows that the 3 cryptographers
              will know that one of them paid (if this protocol is
              executed faithfully), but that the identity can't be
              "localized"
             - a diagram is needed...
           + this can be generalized...
             + longer messages
               - use multiple rounds of the protocol
             + faster than coin-flipping
               - each participant and his left partner share a list of
                  "pre-flipped" coins, such as truly random bits
                  (radioactive decay, noise, etc.) stored on a CD-ROM or
                  whatever
               - they can thus "flip coins" as fast as they can read the
                  disk
             + simultaneous messages (collision)
               - use back-off and retry protocols (like Ethernet uses)
             + collusion of participants
               - an interesting issue...remember that participants are
                  not restricted to the simple ring topology
               - various subgraphs can be formed
               - a participant who fears collusion can pick a subgraph
                  that includes those he doubts will collude (a tricky
                  issue)
             + anonymity of receiver
               - can use P-K to encrypt message to some P-K and then
                  "broadcast" it and force every participant to try to
                  decrypt it (only the anonymous recipient will actually
                  succeed)
           - Chaum's complete 1988 "Journal of Cryptology" article is
              available at the Cypherpunks archive site,
              ftp.soda.csua.edu, in /pub/cypherpunks
   8.11.3. What "DC-Net" Means
           - a system (graph, subgraphs, etc.) of communicating
              participants, who need not be known to each other, can
              communicate information such that neither the sender nor
              the recipient is known
           + unconditional sender untraceability
             - the anonymity of the broadcaster can be information-
                theoretically secure, i.e., truly impossible to break and
                requiring no assumptions about public key systems, the
                difficulty of factoring, etc.
           + receiver untraceability depends on public-key protocols, so
              traceability is computationally-dependent
             - but this is believed to be secure, of course
           + bandwidth can be increased by several means
             - shared keys
             - block transmission by accumulating messages
             - hiearchies of messages, subgraphs, etc.
 

Next Page: 8.12 Future Remailers
Previous Page: 8.10 Cryptanalysis of Remailer Networks

By Tim May, see README

HTML by Jonathan Rochkind