From: Douglas Sinclair <dsinclai@acs.ucalgary.ca>
Date: Sat, 23 Oct 93 12:33:06 PDT
To: cypherpunks@toad.com
Subject: DC-nets
Message-ID: <9310231931.AA56549@acs1.acs.ucalgary.ca>
MIME-Version: 1.0
Content-Type: text/plain


My thanks to Tim Newsham and Tim May for sending me information
on DC-networks.  It appears the modifications that I had been
thinking about were not discussed by Chaum in his original
paper, which gives me some hope I may have stumbled across
something new.

Chaum proposes the use of public key cryptography for secure
communication between vertices in a DC-net.  This leads to the
problem of secure key exchange, and the possibility that the
public key algorithm is not sound.

Instead, the interference properties of a DC-net may be used
to give unconditional security.  Say Alice wishes to send a message
M to Bob.

1.  Alice computes the hash of M, and appends it to M to
produce a packet P of p bits.

2.  Alice transmits on the net "Message of p bits for Bob"

3.  Bob receives this message, and prepares a packet R composed
    of p random bits.

4.  Alice transmits packet P.  Simultaniously, Bob transmits
    packet R.  The output of the DC­net is now X, where
    X = P XOR R

5.  Bob, computes P = X XOR R.  He verifies that the last bits of
    P are a valid hash for the first portion.  If so, he has
    succesfully recieved M and the transfer is over.  If not,
    there must have been interference from another party.  He
    would then transmit "Alice, resend message", and the
    procedure would be repeated.

All that Carol, another vertex in the net, can see is X.  She
cannot derive P from X as it has been encrypted with the
equivalent of a one-time pad.  Thus, P is unconditionally
secure.

Alice and Bob need no nothing about each other for this transfer
to work.  Indeed, Alice and Bob may well be pseudonyms.  The worst
that can happen is that two sites respond to the pseudonym of Bob,
and the transfer suffers from interference.  Hence the built in
hash.  Note that only Bob can see the valid hash, and only then
if the transfer has worked perfectly.  Thus, the hash need not
be secure.

I have not looked at the efffects of collusion on this protocol.
My gut feeling is that sufficient collusion would bring it down
in flames.  However, this is also true of the basic operation
of a DC-net.

I cannot claim that I came up with this protocol alone.  It was
concieved this summer at a seminar I taught on cryptography.
After sitting around a table and flipping coins to prove that
it actually did work, we started looking at the problems of
un-intentional interference.  This is the result of half an
hour of me trying to remember what little I had read of DC-nets
and the students making me look like a fool for not having
studied as much as I should have.

So, my first question to you is, does it work?  The next
question is has it been thought of before?  And finally,
is it useful?

-- 
PGP 2.3a Key by finger