a simple explanation of DC-Net
-----BEGIN PGP SIGNED MESSAGE----- The DC-Net is not very easy to understand. I'll try to explain the most important parts of the concept as simply as I can. Let's say there are a number of participants in a DC-Net. Each participant shares a different one-time pad with each of several other participants. At most one participant can send one bit through the DC-Net per "round". How does this work? For each round i, a participant takes the i-th bit of all the one-time pads that he has and XORs them together. If he doesn't want to send a bit, he just broadcasts the resulting bit to every other participant. If he DOES want to send a bit, then he broadcasts the XOR of that resulting bit and the bit he wants to send. When everyone has done this, each participant takes all of the bits that has been broadcasted, and XORs them together. This last action produces the output of the DC-Net for the i-th round. Suppose for the first round nobody wants to send a bit. Since each one- time pad is known by 2 participants, the first bit of each pad has been XORed into the final output twice. Since anything XORed by anything twice equals itself, these two XORs cancel each other out. And since nothing else has been XORed into the output, the output must equal 0. If one participant wanted to send a bit, however, then something else HAS been XORed into the output. Since all the bits from the one-time pads cancel out, the output equals the bit he wanted to send. Wei Dai P.S. I realize someone has probably written something like this already, but I hope this explanation helps someone who is still puzzled. If nothing else, it serves as a sanity check on my own understanding. -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBLzbKfTl0sXKgdnV5AQGTpwQAtGe5zl91MgA/ayzBGo/DLXh7NyTDSw00 h/qZZxh2U9HoNFLHMMiHV64PYE8poJlCH8kLDY+XZlv1phoiBtMnc2AehN5XVJmr YCQ77rH9vp6yk6SZ5F7HV/UNIIQj6TkW806OZP7LlgUrXWPZdCSYGPh7n60J4TkD RaspzTgFcUk= =ml6y -----END PGP SIGNATURE----- E-mail: Wei Dai <weidai@eskimo.com> URL: "http://www.eskimo.com/~weidai" =================== Exponential Increase of Complexity =================== --> singularity --> atoms --> macromolecules --> biological evolution --> central nervous systems --> symbolic communication --> homo sapiens --> digital computers --> internetworking --> close-coupled automation --> broadband brain-to-net connections --> artificial intelligence --> distributed consciousness --> group minds --> ? ? ?
On Mon, 6 Feb 1995, Wei Dai wrote:
P.S. I realize someone has probably written something like this already, but I hope this explanation helps someone who is still puzzled.
I've written a test-bed IRC client which uses DC Nets to allow multiple people to talk on an IRC channel anonymously. It operates in a ring, with every participant showing his/her random bit stream with the neighbor to the "left." Participants compare their bit stream with the one their neighbor shares with them, and broadcasts the differences (with lies indicating xmitted "1" bite) to all participants. The difference bits for each round are totalled together modulo 2 by each participant, and any anonymous broadcasts can be determined from those totals. My implementation was a quick project for a class and lacks some really important features: 1) used built-in PRNG 2) does not encrypt private messages for bit stream sharing between neighbors 3) no ALOHA or similar protocol for dealing with message collisions 4) ring could be expanded to more complex graph to increase number of colluding participants needed to break anonymity. BTW - There have been a few other papers on DC-Nets since Chaum including detections of DC-Net disrupters, and protection against a group of active attacks. I include a report with my code now available at ftp://ftp.csua.berkeley.edu/pub/cypherpunks/applications/dc-irc.alpha.tar.gz which goes into more details on these matters and has references. -Thomas
Wei Dai wrote:
The DC-Net is not very easy to understand. I'll try to explain the most important parts of the concept as simply as I can. ...nice explanation elided...
P.S. I realize someone has probably written something like this already, but I hope this explanation helps someone who is still puzzled. If nothing else, it serves as a sanity check on my own understanding.
Yes, I wrote up a similar explanation for the Extropians list, in mid-1992, before our list existed. (It's been redistributed here a couple of times, and is in some of the CP archives an/or URLs reported here.) Eric Hughes and I did a anthropomorphic demo of DC-Nets a couple of years ago, at the first CP meeting. That is, we got up in front of folks and literally acted-out a simple transmission (and even this took some minutes, to make clear the protocols, etc.). My estimate is that the averagely bright Cypherpunk (which is to say, _very_ bright person) can get the key ideas of DC-Nets in a few hours of careful thinking and diagramming of the ideas in the paper, which is of course archived at the Cypherpunks site (and probably readily accessible in several URLs). By "key ideas" I mean the first 3-4 pages of the paper, whjere the ideas are laid out. Issues of collusion and disruption are what Chaum spends most of his 1988 paper on, and start after the first introductory pages. Sub-nets, to reduce collusion, for example. Later papers, such as those by the Pfitzmanns and by Jurgen Bos, deal in much more detail with disruption. (By the way, I mentioned to Chaum, in Monte Carlo last week, our continuing fascination with DC-Nets, despite the difficulties in fully implementing/using them. Chaum was aware of the efforts by the Austin group, and was pleased to hear that several parallel are continuing. I got the impression that we are the only people in the world still looking at this stuff, which is not as bad as it sounds. You see, those writing papers have moved on to other things, whereas Cypherpunks is a list devoted to practical implementations and demonstrations, and few others are, so we have a continuing interest. Chaum was very complimentary about the Cypherpunks.) --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero | 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. Cypherpunks list: majordomo@toad.com with body message of only: subscribe cypherpunks. FAQ available at ftp.netcom.com in pub/tc/tcmay
participants (3)
-
tcmay＠netcom.com -
Thomas Grant Edwards -
Wei Dai