RfC: Taxonomy of mix batching approaches (draft)

[Roger Dingledine <arma@mit.edu>]

http://freehaven.net/doc/batching-taxonomy/taxonomy.pdf
(or http://freehaven.net/doc/batching-taxonomy/taxonomy.ps)

"From a Trickle to a Flood: Active Attacks on Several Mix Types"
Andrei Serjantov, Roger Dingledine, and Paul Syverson

Abstract:
The literature contains a variety of different mixes, some of which have
been used in deployed anonymity systems. We explore their anonymity and
message delay properties, and show how to mount active attacks against
them by altering the traffic between the mixes. We show that if certain
mixes are used, such attacks cannot destroy the anonymity of a particular
message completely. We work out the cost of these attacks in terms of
the number of messages the attacker must insert into the network and the
time he must spend. We discuss advantages and disadvantages of these
mixes and the settings in which their use is appropriate. Finally, we
look at dummy traffic and SG mixes as other promising ways of protecting
against the attacks, point out potential weaknesses in existing designs,
and suggest improvements.


Please try to rip apart (and otherwise comment on) our ideas. The writing
isn't very tight.. but I'm ok with that at this point. The paper was
accepted to Info Hiding 2002, and we'll be submitting the preproceedings
snapshot on 8 Sept.

Thanks,
--Roger