Re: DC-Net proposal, comments requested

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

Doug Barnes writes about Tim Newsham's work on DC-Nets:

> I've been looking at this problem as well, Tim, and it doesn't seem to 
> me that you have to output a bit at a time. In fact, the DC net machines
> should probably be operating on blocks that fit nicely into single IP
> packets. Just consider the blocks to be the result of N coin tosses.

Exactly. The "coin tosses" can be arranged far in advance and shared
on CD-ROM (for example) or whatever's convenient. Chaum, Bos,
Pfaltzman (I think...I don't have my paper handy) consider even using
ciphers to generate the tosses, though then the DC-Net ceases to be
information theoretically secure and is no more secure than the cipher
itself.

To see this in a simple way, forget about the "classical" DC-Net
situation of n participants in a ring or other graph. Instead,
consider only 2 participants, Alice and Bob.

Alice and Bob share a sequence of random numbers, essentially a
one-time pad. The sequence they share is, as an example:

1 0 1 1 0 1 1 0 0 0 1 0 1 0 .....

As a pair they can send 1s or 0s by the one of them sending the
message XORing his message with the sequence and then both of them
output the sequence.

Let us imagine Bob wished to send the "message": 1 1 0 0 1 1 0 1 0 1
1...

Alice: 1 0 1 1 0 1 1 0 0 0 1 0 1 0 .....

Bob:   1 1 0 0 1 1 0 1 0 1 1 ....   (his message, before he sends it)

XOR:   0 1 1 1 1 0 1 1 0 1 0..... (this is what Bob sends out)

The outside world sees two different bit streams and recovers the
message by XORing the streams put out by Alice and Bob:

XOR:   1 1 0 0 1 1 0 1 0 1 1....

Thus, Bob's "message" has been sent out, but since the outside world
does not the original one time pad Alice and Bob were using, it cannot
know which of Bob or Alice was sending the pad and which was "lying,"
that is, XORing the message with the pad and outputting that.

Of course, Alice knows it was Bob who sent the message (becuase she
knows she didn't). Extending the protocol to the ring
Alice-Bob-Charles in the classical DC-Net way completes the picture.

But you can see how precomputed, preexchanged pads--or a very secure
cipher (a good pseudorandom number generator, really)--would be used
in practice to eliminate coin tosses, real or simulated. No DC-Nets
would do things one bit a time, that I can see.

> Also, I have thought of some ways of dealing with "slacker" processes
> or folks who suddenly drop out that work better with a broadcast approach,
> but there's probably a way to deal with them in the token-based scheme.

"Disruption" by sending of spurious messages, to deny service by
flooding the DC-net, seems to be the biggest problem, and Chaum and
Bos devote most of their papers to schemes for handling this.

I have some of these papers--let me know if you don' yet have them,
especially the hard to find Jurgen Bos Ph.D. thesis.

Great to see work on DC-Nets again! Yanek Martinson, who I've not seen
on the list in many months, was working on an implementation, and at
today's Cypherpunks meeting, Strick expressed interest in implementing
DC-nets in his TCL-based crypto toolkit.


--Tim May


-- 
..........................................................................
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 | Public Key: PGP and MailSafe available.
Note: I put time and money into writing this posting. I hope you enjoy it.