Re: Here it is; bi-directional dining cryptographers

[Bryce Wilcox <wilcoxb@nagina.cs.colorado.edu>]

-----BEGIN PGP SIGNED MESSAGE-----

> 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.)


Chaum discusses it a lot in his original DC paper.  In the limit, any
disrupter can be ousted from the Net.  What you do is "trap" the disrupter
by getting all ready to speak and then not saying anything.  (The only reason
that you do not say anything is that you are about to reveal your secret
bits, and anything you say will be traceable to you.  If you don't mind 
getting identified with your words this once then go ahead.)  The disrupter
foolishly blurts out some garbage at that instant and then everyone holds
up their secret bits to see who "lied" about their XOR (who inverted their
output when they weren't supposed to.)
  Of course if all but one or two participants are colluding disrupters
then it will probably be the one or two who are ousted instead of the
disrupters!  But this is sort of the same effect, no?


This presupposes a block-scheduling algorithm, or at least a set-up in which
the disrupter is committed to his output *before* he realizes that his
intended victim is not transmitting.


Are you familiar with the topology of DC-nets-- how anonymity is preserved
relative to two participants as long as there is a "path" of shared bits
between them?  (That is, A shares with B who shares with C, now A and C are
anonymous relative to each other.  Of course if B decides to out them, 
then they are high and dry.  The interesting thing is that if A and C both
start sharing with D, then C is no longer capable of outting them unless he
collaborates with D.)  The result is that each individual participant in a
DC net can increase their level of security just by sharing with a new
partner.  (Of course, if that new guy is a tentacle of the "anti-anon" 
colluders, then the individual has not actually increased their security.
But they have not decreased it either.)

I really like that about DC-net topology--  any two participants can elect
to boost their anonymity-level without needing the other participants'
permission and without increasing the workload on the other participants.


Bryce
signatures follow
    /=============------------        Our e-mail should be
     Bryce Wilcox,  Programmer          Between you and me
     bryce.wilcox@colorado.edu            For "pretty good privacy"
     ------------=============/             Use PGP!

-----BEGIN PGP SIGNATURE-----
Version: 2.6.1

iQCVAwUBMAvVWJCUT4gUihHlAQGsyQP+IgY/hHMGtj7kYj3eiIVSoSaAkDOPeNYS
YnPLSahNfGPKtd8cOyX4QXlrBKVSUgJS3hrAFxSGspIl36YOFSLloFNK73lk7DaU
JJmfISWJg8nYWzURpNc/VJkcI9u5u30izD5VVUOFXX0jRohBYxjdUFmaLOlY1vu7
1/xVNHCVhZo=
=FIjz
-----END PGP SIGNATURE-----