Douglas Sinclair asks about DC-Nets. I'm not sure if he's read the Chaum paper yet, but in any case there are probably others who would profit from seeing some introductory material on DC-Nets. Several folks are looking into this, including Henry Strickland (Strick) and several folks in the Austin group. Several others have tried to get something going in the past (Yanek Martinson, Marc Ringuette, etc.), but so far no one has produced a working DC-Net. I don't know if even Chaum has, and the several papers (Jurgen Bos, Pfaltzman, etc.) indicate the theory needs more work (especially on disruption by malicious attackers). Anyway, here's what Doug asked:
Can anyone point me to a detailed description of the dining cryptographers' protocol? I've had some thoughts on how to modify it, and I want to know if I'm just re-inventing the wheel. Please reply via e-mail. Thanks. -- PGP 2.3a Key by finger
So here's an essay, a rather informal essay, I've posted a couple of times. As the essay notes, a full copy of the 1988 paper by David Chaum was also posted to the list by The Information Liberation Front. If there's interest in DC-Nets this time around, perhaps one of us who kept copies of it can post it again. <grin> Enjoy it! It is truly an astounding concept. Simple, too, once you get the idea. -Tim Date: Tue, 23 Feb 93 10:08:34 -0800 To: cypherpunks@toad.com From: tcmay@netcom.com (Timothy C. May) Subject: Dining Cryptographers Nets--An Introduction Nickey MacDonald writes:
Also, I have seen a number of references to DC nets... I must confess I have never heard of the term before... can someone enlighten me?
Here's a summary of the "dining cryptographers net" I wrote back in the pre-Cypherpunks days (which I later posted to the nascent Cypherpunks list). I'm posting it here because of the question just asked, thinking that others may be similary confused. (A "Glossary" also exists, and is in the "soda" archive site.) (I could apologize for the volume, but cyherpunks ought to be able to handle a few measly kilobytes of stuff. Besides, at least this won't go out multiple times to the list!) Understand that DC-Nets are further off in the future than the Cypherpunks-PAX-PENET-style remailers being discussed these last few months. Chaum-style mixes, based on his 1981 CACM letter, have yet to be implemented, let alone the more advanced DC-Net-style systems. Hal Finney, Marc Ringuette, and Yanek Martinson are some of the folks on this list who are interested in working on DC-Nets....Yanek even claims to have a primitive one running on his local machine and is interested in volunteers to test it on a larger basis. The "Information Liberation Front" also posted Chaum's entire 1988 paper, "The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability." I suppose you could ask them to repost the article or forward it to you. Hope the newcomers enjoy this. To: Extropians@gnu.ai.mit.edu From: uunet!netcom.com!tcmay (Timothy C. May) Subject: Dining Cryptographers Date: Tue, 18 Aug 92 15:45:34 PDT 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 | RSA MailSafe Public Key: by arrangement