Re: Here it is; bi-directional dining cryptographers

[stewarts@ix.netcom.com (Bill Stewart)]

Context: Bidirectional DCnets, Alice and Bob simultaneously transmitting
to each other.  Interesting approach, though you do have to schedule it
somehow.  It's a different take on the uses of DCnets - the original
was for an anonymous-1 to many rather than a 1 to 1 with only the two
participants
knowing, though in the first case the recipient can be known only to the sender
if they want to arrange things that way through shared secrets or whatever.

At 01:31 PM 7/17/95 +0100, Rev. Mark Grant wrote:
>Yes, but presumably it's expected that they would be using secure
>encryption on the messages that they're sending. That might still provide
>some information about the message for traffic analysis, e.g. if you send
>a PGP message you have your key-id at the beginning, and if you knew the 
>keys of all members of the DC-net you could XOR them and see who's 
>talking to who.

Presumably people will use multiple key-ids on the net as well - Alice may
have a general-use "Alice" key, and maybe also a general-use "Medusa" key,
but Alice or Medusa may have also arranged with Bob to use a different key
for traffic where he doesn't mind if she knows he sent it and he doesn't want
anyone else knowing it's being sent to her.  Also, he can do this anonymously,
so she doesn't know either:

        Alice posts Plaintext("Hi, I'm Alice, key AAAA")
        Bob   posts Encrypt(AAAA, "Hi, Alice, I'm Dr. X, Key XXXX, please
                        post a key I can use to talk to you")
        Alice posts Encrypt(XXXX, Signed(AAAA, "Hi, Dr. X, use key AXAX"))

Bob's message lets him send stuff to Alice without anyone, including her,
knowing it's from him, since the name X and key XXXX are new randoms.
Alice signs her response so Dr. X knows that key AXAX will really go to
Alice and
not to Mallet who's impersonating Alice; she doesn't really care who X is.
If traffic analysis is a concern (Alice noticing, for instance, that she's
getting a _lot_ of requests from key AXAX for her remailer to send stuff
to destination ZZZZ), Bob can keep sending her new requests for keys and ids,
and not reuse them more than he thinks is safe.

>I'd have thought the most significant problem would be reserving the
>blocks in an anonymous fashion while not allowing denial-of-service
>attacks. 

Since anybody can send bits at any time, and nobody can tell who without
lots of collusion, you can't prevent denial-of-service (well, I assume not,
unless there's something rather non-obvious in the literature.)
The Bad Guy can decide if it's more fun to jam the reservations or the messages.
What reservation does for you is gives a short inefficient period (with
possible collisions, backoff-and-retry, etc., depending on algorithm) that
you can use to 
reserve a longer one-user period for message traffic, so you can spend most
of your time talking instead of haggling over interruptions.

One way to do reservations is to use some variant on Slotted Aloha for the
reservation period - for example, everybody picks a random id number for the
session,
(with odd parity or odd high-bit to make collision detection easier),
waits a random number of slots, and then sends their id number.
If there's a collision, wait and retry, maybe with exponential backoff.
After the first slot that's got data and looks like it doesn't have a collision,
anybody who thinks that it was their number picks a different number,
waits a short random number of slots and posts; first one wins.
(If you're using 32-bit randoms and have fewer than a million players, 
the chances of two undetected collisions in a row are really small,
even if people cheat a bit on their backoffs.)  Winner announces how many
slots he's going to use up for his message, so you know when to start again.
#                                Thanks;  Bill
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com