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