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.