The Dining Cryptographers Protocol

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

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.