One-time pads and DC Nets

[nobody@soda.berkeley.edu]

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
74076.1041@compuserve.com