The Dining Cryptographers Protocol

[tcmay@netcom.com (Timothy C. May)]

Cort mentioned the Dining Cryptographers, and since many of you have joined
the list since I last posted this, I thought I'd post it again. This
article is an informal introduction, written originally for the Extropians
list.

The full version of David Chaum's paper on the Dining Cryptographers is at
the ftp.csua.berkeley.edu site in pub/cypherpunks.

--Tim May



>From: tcmay@netcom.com (Timothy C. May)
>Subject: The Dining Cryptographers Protocol
>To: cypherpunks@toad.com
>Date: Mon, 16 Nov 92 1:10:10 PST
>Cc: tcmay@netcom.com (Timothy C. May)
>X-Mailer: ELM [version 2.3 PL11]
>Status: OR
>
>Fellow Dining Cryptographers (and Cypherpunks),
>
>Hal Finney has been suggesting I forward to this list some articles I
>wrote for another list of like-minded folks, the "Extropians" list. We
>had some fascinating discussions of digital money, DC-nets, digital
>pseudonyms (a la Vernor Vinge's "True Names," as Hal has noted), etc.
>Basically the stuff I put in my .signature, and so on.
>
>These topics are, in my opinion, at the core of what we are doing on
>this list. It is highly gratifying to see the pieces falling into
>place. And at our crypto session  at the Hackers Conference, it became
>clear to many people just how close we are.
>
>So since Hal just forwarded me one of my old postings, how can I
>resist? (I still _have_ my old posts, but no longer on my NETCOM
>system, so reposting them takes a bit of effort. So I'll just forward
>to you the posting Hal just forwarded to me!)
>
>Hal Finney writes:
>
>I was looking through some old Extropians messages and found this
>one which you wrote about DC nets.  I don't know if you archive your
>old messages, but I thought this had some good stuff, especially at the
>end where you talk about the applications of crypto anonymity.  You
>would probably want to change the use of Extropians to Cypherpunks or
>some such, if you wanted to re-post it there.
>
>Hal
>
>
>Return-Path: <uunet!gnu.ai.mit.edu!extropians-request>
>To: Extropians@gnu.ai.mit.edu
>From: uunet!netcom.com!tcmay (Timothy C. May)
>Subject: Dining Cryptographers
>X-Original-To: Extropians@gnu.ai.mit.edu
>Date: Tue, 18 Aug 92 15:45:34 PDT
>X-Extropian-Date: Remailed on August 18, 372 P.N.O. [22:46:47 UTC]
>Reply-To: uunet!gnu.ai.mit.edu!Extropians
>
>Marc R. has opened the door for me to get into some really exciting
>stuff:
>>
>> Tim May mentioned a new method from Chaum for defeating traffic analysis:
>>
>> > Chaum has since improved the tamper-responding "mix" by going to a pure
>> > software scheme which he calls "the Dining Cryptographers Protocol." It's
>> > described in Vol. 1, Number 1 of "Journal of Cryptology," 1988. If there's
>> > interest, I'll summarize it.
>>
>> Yes, please, Tim!
>>
>>
>> M.
>
>Complexity Warning: This stuff (I'm being informal) is easy once you
>get the basic idea. But getting the basic idea usually involves reading
>several articles on what RSA, digital signatures, etc., are all about,
>working out some examples, thinking about it, drawing pictures with
>other folks, and finally having an "Aha!" experience (in Werner Erhard's
>terms, you "get it"). The ASCII nature of the Net is not conducive to learning
>this stuff, despite the excellent summaries of crypto by Marc R. and Perry M.
>
>The almost-latest "Scientific American," August, has an article by David Chaum
>on digital money, and the latest "Spectrum," available at selected newstands,
>has several articles on security and cryptography. Also, there are lots of
>books. Look 'em up in a university library or flip through them at a large
>technical bookstore and pick the one you like the most. (I like a slim
>Springer-Verlag paperback, "Modern Cryptology," by Gilles Brassard, 1988, as
>a good intro to "modern"--as opposed to "classical"--crypto.)
>
>If the stuff in this posting, and on crypto in general, is beyond your
>current understanding, either ignore it, skim it and try to get the gist,
>or dig into the articles and books.
>
>Anyway, back to "The Dining Cryptographers Problem: Unconditional Sender and
>Recipient Untraceability," David Chaum, Journal of Cryptology, I, 1, 1988.
>Since this journal is hard to get, I'll discuss the article in some detail.
>(The techniques have major implications for anarchocapitalism and for
>Extropian ideas.)
>
>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."
>
>A word on terminology: "Unconditionally secure" means what it says: no
>computer will ever crack it. One-time pads are unconditionally secure...no
>code or cipher is involved, except the one-time pad, so the message is
>secure as long as the pad has not been compromised. "Cryptographically
>secure" means secure so long as various crypto ciphers are secure, which
>may be for a very, very long time (e.g., with very large primes, in RSA).
>
>Chaum describes some "dining cryptographers," which I will playfully change
>to "dining Extropians." (The term is of course a variant of the seminal
>"dining logicians problem" in computer science)
>
>Three Extropians are having dinner, perhaps in New York City. Their waiter
>tells them that their bill has already been paid, either by the NSA
>or by one of them. The waiter won't say more.
>
>The Extropians wish to know whether one of them paid, or the NSA paid. But
>they don't want to be impolite and force the Extropina payer to 'fess up,
>so they carry out this protocol (or procedure):
>
>Each Extropian flips a fair coin behind a menu placed upright between himself
>and the Extropian on his right. The coin is visible to himself AND to the
>Extropian on his left. Each Extropian can see his own coin and the coin to his
>right.
>
>STOP RIGHT HERE! Please take the time to make a sketch of the situation I've
>described. If you lost it here, all that follows will be a blur. I'm sparing
>you folks my attempt at an ASCII drawing!
>
>Each Extropians then states out loud whether the two coins he can see are the
>SAME or are DIFFERENT, e.g., "Heads-Tails" means DIFFERENT, and so forth. For
>now, assume the Extropians are truthful.
>
>A little bit of thinking shows that the total number of "DIFFERENCES" must
>be either 0 (the coins all came up the same), or 2. Odd parity is impossible.
>
>Now the Extropians agree that if one of them paid, he or she will SAY THE
>OPPOSITE of what they actually see. Remember, they don't announce what their
>coin turned up as, only whether it was the same or different as their neighbor.
>
>Suppose none of them paid, i.e., the NSA paid. Then they all report the truth
>and the parity is even (either 0 or 2 differences). They then know the NSA
>paid.
>
>Suppose one of them paid the bill. He reports the opposite of what he actually
>sees, and the parity is suddenly odd. That is, there is 1 difference reported.
>The Extropians now know that one of them paid. But can they determine which
>one?
>
>Suppose you are one of the Extropians and you know you didn't pay. One of the
>other two did. You either reported SAME or DIFFERENT, based on what your
>neighbor to the right (whose coin you can see) had. But you can't tell which
>of the other two is lying! (You can see you right-hand neighbor's coin, but
>you can't see the coin he sees to his right!)
>
>This all generalizes to any number of people. If none of them paid, the parity
>is even. If one of them paid, the parity is odd. But which one of them paid
>cannot be deduced. And it should be clear that each round can transmit a bit,
>e.g., "I paid" is a "1". The message "Attack at dawn" could thus be "sent"
>untraceably with multiple rounds of the protocol.
>
>The Crypto Ouija Board: I explain this to people as a kind of ouija board.
>A message, like "I paid" or a more interesting "Transfer funds from.....,"
>just "emerges" out of the group, with no means of knowing where it came
>from. Truly astounding.
>
>Now there are many interesting wrinkles and elaborations to this protocol. I'll
>note just a few.
>
>1. Collusion. Obviously the Extropians can collude to deduce the payer.
>This is best dealt with by creating multiple subcircuits (groups doing the
>protocol amongst themselves). Lots more stuff here. Chaum devotes most of the
>paper to these kind of issues and their solutions.
>
>2. With each round of this protocol, a single bit is transmitted. Sending
>a long message means many coin flips. Instead of coins and menus, the
>neighbors would exchange lists of random numbers (with the right partners,
>as per the protocol above, of course. Details are easy to figure out.)
>
>3. Since the lists are essentially one-time pads, the protocol is
>unconditionally secure, i.e., no assumptions are made about the difficulty
>of factoring large numbers or any other crypto assumptions.
>
>4. Participants in such a "DC-Net" (and here we are coming to the heart
>of the "crypto anarchy" I have mentioned several times, and which is
>perhaps foolishly advertised in my .sig) could exchange CD-ROMs or DATs,
>giving them enough "coin flips" for zillions of messages, all untraceable!
>The logistics are not simple, but one can imagine personal devices, like
>smart card or Apple "Newtons," that can handle these protocols (early
>applications may be for untraceable brainstorming comments, secure
>voting in corportate settings, etc.)
>
>5. The lists of random numbers (coin flips) can be generated with standard
>cryptographic methods, requiring only a key to be exchanged between the
>appropriate participants. This eliminates the need for the one-time pad,
>but means the method is now only cryptographically secure, which is
>often sufficient. (Don't think "only cryptographically secure" means
>insecure....the messages may remain encrypted for the next billion years)
>
>6. Collisions occur when multiple messages are sent at the same time. Various
>schemes can be devised to handle this, like backing off when you detect
>another sender (when even parity is seen instead of odd parity). In large
>systems this is likely to be a problem. Solutions are left as an exercise.
>
>7. Noise. Some participants may try to flood the circuit with spurious
>messages, to defeat the system or for whatever other reasons. This is
>still an issue. (If there's anything to take away from crypto, it's that
>nothing is as simple as it looks, that there are always devious ways to
>spoof, jam, and forge. I expect you've seen this from some of the debate
>on digital voting schemes.)
>
>What Can "DC-Net" Be Used For?:
>
>* Untraceable mail. Useful for avoiding censorship, for avoiding lawsuits,
>and for all kinds of crypto anarchy things.
>
>* Fully anonymous bulletin boards, with no traceability of postings or
>responses. Illegal materials can be offered for sale (my 1987 canonical
>example, which freaked out a few people: "Stealth bomber blueprints for
>sale. Post highest offer and include public key."). Think for a few minutes
>about this and you'll see the profound implications.
>
>* Decentralized nexus of activity. Since messages "emerge" (a la the ouija
>board metaphor), there is no central posting area. Nothing for the government
>to shut down, complete deniability by the participants.
>
>* Only you know who your a partners are....in any given circuit. And you can
>be in as many circuits as you wish. (Payments can be made to others,
>to create a profit motive. I won't deal with this issue, or with the issue
>of how reputations are handled, in this posting.)
>
>* The tamper-responding "digital mixes" can still be useful, and may supplement
>this purely software-based approach.
>
>* Digital money gets involved, too, both for payments in this system, and in
>terms of "alternative currencies." I'm not an economist, so I'll leave this
>for others to go into in more detail.
>
>Enough for now. Chaum's work is just the start. These systems can initially be
>set up for "innocuous" purposes like research into crypto techniques (not yet
>banned in the U.S.), role-playing games, religions, and the like. Once
>they get going, it'll be too late to stop the other things.
>
>Hope you liked this summary. Please read the articles...there's just no way
>my posting can do justice to them (though I admit I've concentrated my efforts
>on the political aspects, which "respectable" crypto researchers rarely
>mention, so perhaps the flavor here is a bit more Extropian than you'll
>find elsewhere.)
>
>--Tim (part of the "Too Many Tims!" Conspiracy)
>
>--
>..........................................................................
>Timothy C. May         | Crypto Anarchy: encryption, digital money,
>tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
>408-688-5409           | knowledge, reputations, information markets,
>W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
>Higher Power: 2^756839 | PGP Public Key: awaiting Macintosh version.
>
>

..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets,
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."