[freehaven-dev] Stop-And-Go MIXes

[dmolnar@belegost.mit.edu]

This paper shows a mixnet which provides what the authors call
"probabilistic anonymity." They apply techniques from queueing theory to
say something about an adversary's probability of correlating two messages
which pass through a mixnet node. 

arma : you should also take another look at that paper Prof Lynch
mentioned...

Stop-and-Go-MIXes Providing Probabilistic Anonymity in an Open System
Dogan Kesdogan, Jan Egner, and Roland Bschkes

1998 Second Annual Workshop on Information Hiding

kesdogan@informatik.rwth-aachen.de 

Abstract. Currently known basic anonymity techniques depend on identity
verification. If verification of user identities is not possible due to
the related management overhead or a general lack of information (e.g. on
the Internet), an adversary can participate several times in a
communication relationship and observe the honest users. In this paper we
focus on the problem of providing anonymity without identity verification.
The notion of probabilistic anonymity is introduced. Probabilistic
anonymity is based on a publicly known security parameter, which
determines the security of the protocol. For probabilistic anonymity the
insecurity, expressed as the probability of having only one honest
participant, approaches 0 at an exponential rate as the security parameter
is changed linearly. Based on our security model we propose a new MIX
variant called ``Stop-and-Go-MIX'' (SG-MIX) which provides anonymity
without identity verification, and prove that it is probabilistically
secure. 

http://link.springer.de/link/service/series/0558/papers/1525/15250083.pdf