[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: One-time pads and DC Nets*From*: [email protected]*Date*: Tue, 27 Oct 92 18:11:03 -0800*Remailed-By*: Eric Hughes <[email protected]>

Regarding the previous discussion about one-time pads, there is another use for disks full of random numbers. They can be used to implement Chaum's DC-nets. For the degenerate case of just two people communicating, the DC-net is similar to using a one-time pad. However, what you are hiding is not _what_ you are sending, but _who_ is sending it. DC-nets ("DC" stands for "Dining Cryptographers", the example Chaum used to introduce the idea) are designed to hide message sources among some group of people. The people have to be fairly well connected, with near-real-time communications capability. It won't really work for people exchanging email. For the simple two-person case, suppose as in the case of the one-time pad that each person has an identical CD-ROM filled with random bits. What they do is, at some predetermined rate, each person just transmits the bits off his pad. Both people are sending the same bits. When one wants to send a message, he starts toggling certain of his bits. To send a "1" he sends the opposite of the next bit from the one-time pad; to send a zero he sends the correct version of the next bit from the one-time pad. Assuming they don't start transmitting at the same time, what an outside observer will see is that, where before they were both producing exactly the same bits, now they are producing a certain number of opposite bits. Interpreting each opposite bit as a 1, and each case of same bits as a 0, produces a recognizable message. But, the outside observer can't tell which person is sending that message. All he sees is two totally random streams of bits, which disagree at certain spots. Without access to the one-time pads, there is no way for him to tell who is sending. (Of course, the two people involved know who is sending, since one of them is and one of them isn't.) Generalizing to larger numbers of people, you need to have a separate one-time pad shared with each other person in the group. In other words, for a group of N people there has to be a total of N(N-1)/2 one-time pads; each person has N-1 of them. That is, for each pair of people in the group, there is a unique and secret one-time pad which they share. (This is for maximal security - you can get by with fewer pads if you trust each other some.) Now, they all send all the time. What they send is the "XOR" of the next bits of all their N-1 one-time pads. It turns out that if you then "XOR" everybody's output bits, you'll get nothing but zeros as a result. When someone wants to send, he sends the opposite of what he normally would for a "1", and he sends just what he normally would for a "0". Collisions can be handled like ethernet - back off and retransmit. (Chaum had another way involving reserving future blocks of transmit time.) With N people sharing N-1 one-time pads per person, nobody can tell who is transmitting. All anyone knows is whether he himself is transmitting or not; all an outside observer knows is that someone in the group is transmitting. DC-Nets eat up one-time pads even worse than using them for message secrecy does. But, with CD's, you can put a lot of data on a pad. And the system is fairly robust against pads being stolen. If one person's one-time pads are all secretly copied by a spy, then he can tell if that person is sending. But he learns absolutely nothing about which other people are sending. I wonder if it would be possible to experiment with a DC-Net system in the Internet environment. I recently acquired an account on a system with Internet connectivity (I know because I can telnet and ftp from it). I've done considerable programming with Unix socket communication in systems connected by ethernet, and I think the Internet provides a very similar programming interface. It shouldn't be that hard to create a very simple "chat" program in which message sources are strictly anonymous (assuming the existance of the required one-time pad random-number files - for testing, they could be created by random number generators at each end, started with identical seeds). I'll try some experiments along these lines over the next few days. Hal [email protected]

- Prev by Date:
**Re: D-H telnet protocol** - Next by Date:
**re: Hackers Conference--Crypto Session** - Prev by thread:
**Threat to our privacy** - Next by thread:
**One-time pads and DC Nets** - Index(es):