[freehaven-dev] DC-nets

[dmolnar@belegost.mit.edu]

first draft, 

\section{Dining Cryptographers as an Anonymous Channel}

The Dining Cryptographers protocol was introduced by David Chaum as a
means of guaranteeing untraceability for the sender and receiver of a
message, even against a computationally all-powerful adversary\cite{}. The
original protocol assumes a reliable broadcast channel; the protocol
consists of a series of "superimposed sendings" in which a total of $n$
participants send messages which eventually "add up" to give the final
message, which seems to appear out of thin air for the final receiver.
Chaum was able to prove that an eavesdropper could not reconstruct the
original sender or receiver of the
message, even given access to all public broadcasts and passive control of
up to $n-2$ participants \cite{}. 

Because this protocol needs no computational assumptions, at first glance
it seems preferable to a MIX for providing an anonymous channel.
Unfortunately, Chaum's original protocol is based on two assumptions which
make it impractical. First, the broadcast channel
must be reliable. An active adversary who can delay or drop messages can
at least disrupt communications and perhaps gain information. Second, the
communication is very ``fragile," in the sense that a single malicious
participant can stop other participants from sending any messages by
spewing junk onto the broadcast channel. In addition, the protocol
requires several rounds of communication to send a single message.

The first two problems were addressed by Waidner and Pfitzmann\cite{}.
Their protocol maintains the unconditional sender and recipient
untraceability of Chaum's protocol, but removes the need for a reliable
broadcast channel by implementing reliability via Byzantine Agreement. 
Here they must work around a slight problem, as Byzantine Agreement
 was proved by Dolev and Strong to be impossible as soon as the number of
evil nodes becomes greater than $n/3$ \cite{}. The trick here is that the
Dolev and Strong model does not allow for authentication of any kind
between nodes; once a primitive like digital signatures is added, the
impossibility result no longer applies and in fact up to $n - 2$ evil
processors can be tolerated.

Using digital signatures requires adding a computational assumption,
however, in that they require the existence of one-way functions. There
are at least two ways to work around this problem. The first is to use a
``fail-stop" signature: a signature scheme which can detect forgeries by
an unexpectedly powerful adversary \cite{}. It does so by ensuring that
each message has many different signatures; if an adversary signs with
one, and the legitimate user signs with a different one, this is proof
forgery has occured, and the protocol can be shut down. The second is the
use of ``pseudosignatures" -- generalized message authentication codes
which have some of the properties of signatures but are
information-theoretically secure against forgery. 

To catch malicious participants, Waidner and Pfitzmann add a new property
of ``serviceability." This property means that disruptive participants can
be identified and shut out of future rounds of communication. Their
protocol acheives serviceability in the face of computationally bounded
adversaries by allowing participants to set ``traps" which reveal a bad
player if disturbed. 

These improvements remove the most significant theoretical objections to
the dining cryptographers protocol. In the context of Free Haven,
unfortunately, we have a problem : the protocol assumes the existence of
a non-anonymous phase in which participants can discuss whether or not the
``traps" were disturbed and prepare for the next message. The participants
in the protocol are identified, even though the sender and receiver of any
given message is not. If the only long-term participants in the protocol
are likely to be Free Haven servnet nodes, then we do not acheive the
server-anonymity we desire. 

Less serious, but still important, problems are the efficiency of the
protocol and the difficulty of correct implementation.
 
%% I haven't analysed how efficient this all is yet. My guess is not very.

Therefore we have not seriously considered using the dining cryptographers
protocol to provide Free Haven's anonymous channel. If we were to do so,
we might consider running a dining cryptographer protocol using MIXes to
hide the legal identity, or True Name, or each participant. In that case,
while a failure of the MIX would reveal a participant's identity, it would
not be possible to link the participant to a message without seizing his
or her computer.