Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching
Modified Files:
model.tex sync-batching.pdf sync-batching.tex
Log Message:
another round of fixes (plus add page numbers)
Index: model.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/model.tex,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -d -r1.9 -r1.10
--- model.tex 27 Jan 2004 08:58:44 -0000 1.9
+++ model.tex 27 Jan 2004 14:20:30 -0000 1.10
@@ -15,7 +15,7 @@
and use a fully automated probabilistic model checking technique to
compute probability distributions for different network topologies and
configurations. We use \emph{entropy} of each topology's respective
-distribution as our comparison metric, in the spirit of~\cite{Serj02,Diaz02}.
+distribution as our comparison metric, in the spirit of~\cite{Diaz02,Serj02}.
\subsection{Mixing as permutation}
Index: sync-batching.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.pdf,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
Binary files /tmp/cvslg6PIV and /tmp/cvso2DLXO differ
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.49
retrieving revision 1.50
diff -u -d -r1.49 -r1.50
--- sync-batching.tex 27 Jan 2004 08:58:44 -0000 1.49
+++ sync-batching.tex 27 Jan 2004 14:20:30 -0000 1.50
@@ -43,12 +43,13 @@
%but we have been unable to contact
%him since beginning the paper. We'll keep trying.}}
-\author{Roger Dingledine\inst{1} and Vitaly Shmatikov\inst{2} and Paul Syverson\inst{3}}
+\author{Roger Dingledine\inst{1} \and Vitaly Shmatikov\inst{2} \and Paul Syverson\inst{3}}
\institute{The Free Haven Project \email{(arma@freehaven.net)} \and
SRI International \email{(shmat@csl.sri.com)} \and
Naval Research Lab \email{(syverson@itd.nrl.navy.mil)}}
\maketitle
+\pagestyle{plain}
%======================================================================
\begin{abstract}
@@ -80,13 +81,13 @@
\section{Introduction}
\label{sec:intro}
-Modern deployed mix networks, including Mixmaster \cite{mixmaster-spec} and
-its successor Mixminion \cite{minion-design}, are subject to partitioning
+Modern deployed mix networks, including Mixmaster~\cite{mixmaster-spec} and
+its successor Mixminion~\cite{minion-design}, are subject to partitioning
attacks: a passive adversary can observe the network until a target
-message happens to stand out from the others \cite{disad-free-routes},
+message happens to stand out from the others~\cite{disad-free-routes},
and an active adversary can manipulate the network to separate one
-message from the others via blending attacks \cite{trickle02}.
-Berthold et al.~argue \cite{disad-free-routes} that partitioning
+message from the others via blending attacks~\cite{trickle02}.
+Berthold et al.~argue~\cite{disad-free-routes} that partitioning
opportunities arise because the networks use a \emph{free-route}
topology---one where the sender can choose the mixes that make up her
message's path. They suggest instead a \emph{cascade network} topology,
@@ -137,7 +138,7 @@
Chaum proposed hiding the correspondence between sender and recipient
by wrapping messages in layers of public-key cryptography, and relaying
-them through a path composed of \emph{mixes} \cite{chaum-mix}. Each mix
+them through a path composed of \emph{mixes}~\cite{chaum-mix}. Each mix
in turn decrypts, delays, and re-orders messages, before relaying them
toward their destinations.
@@ -159,10 +160,10 @@
in practice: if the probability of a given latency $t$ drops off
exponentially with $t$, then so does the probability that
a message leaving the network could have been sent that long
-ago \cite{Serj02}.)
+ago~\cite{Serj02}.)
Also, because Mixmaster is both {\em asynchronous} (messages can enter
and leave the network at any time) and uses free routes, it is subject
-to the attacks from \cite{disad-free-routes} described in
+to the attacks from~\cite{disad-free-routes} described in
Section~\ref{subsec:disad} below.
A network that uses \emph{synchronous batching}
@@ -197,7 +198,7 @@
\subsection{Sync-batching timing model and protocol}
-Dingledine et al.~present in \cite{mix-acc} a mix network that uses
+Dingledine et al.~present in~\cite{mix-acc} a mix network that uses
synchronous batching. We refer to that paper for a detailed discussion
of the timing model, how to handle loosely synchronized clocks, and the
step-by-step instructions for senders and mixes to use the network and
@@ -214,10 +215,10 @@
% This section is based on notes from David Hopwood. Will the real
% David Hopwood please come forward and become an author?
-Berthold et al.\ argue \cite{disad-free-routes} that cascades are safer
+Berthold et al.\ argue~\cite{disad-free-routes} that cascades are safer
than free-route mix networks against a strong adversary who watches all
links and controls many of the mixes. We consider each of their attacks
-below and find in each case that the arguments of \cite{disad-free-routes}
+below and find in each case that the arguments of~\cite{disad-free-routes}
do not apply if the free-route network is synchronous. Indeed, against
some of the attacks a free-route network is much stronger than
the cascade network.
@@ -276,15 +277,15 @@
nodes.
{\bf{Active Attacks:}} The authors discuss an active attack called a
-trickle attack \cite{babel}, wherein the adversary prevents legitimate
+trickle attack~\cite{babel}, wherein the adversary prevents legitimate
messages from entering the batch, or removes some messages from the
batch, so he can more easily trace Alice's message. To make the attack
less overt, he can send his own messages into the batch, or replace
the messages already in the batch with his own messages. These attacks
where the adversary \emph{blends} his messages with Alice's message
threaten both synchronous-batching and asynchronous-batching networks in
-all topologies, and a complete solution is not known \cite{trickle02}.
-The authors of \cite{disad-free-routes} present some approaches to
+all topologies, and a complete solution is not known~\cite{trickle02}.
+The authors of~\cite{disad-free-routes} present some approaches to
mitigating this attack in a cascade environment, but a variety of other
approaches have been developed that also work in a free-route
environment. We discuss them next. Other active attacks are described
@@ -301,10 +302,10 @@
One prevention technique requires each sender to acquire a \emph{ticket}
for each mix in his path before joining a given batch (the senders
-receive blinded tickets \cite{chaum-blind} so the mixes cannot
+receive blinded tickets~\cite{chaum-blind} so the mixes cannot
trivially link them to their messages). Mixes ensure their messages
come from distinct senders, so Alice can expect good mixing at each
-honest node in her path \cite{web-mix}. For cascades this approach is
+honest node in her path~\cite{web-mix}. For cascades this approach is
clearly efficient, because Alice only needs tickets for her chosen
cascade~\cite{disad-free-routes}, but her anonymity set is still
limited to that one cascade. We conjecture that other topologies
@@ -314,7 +315,7 @@
of requiring all users to register with the mixes: it is hard to
imagine that attackers can be excluded from being registered in an
open network~\cite{sybil}. Other prevention techniques use complex
-cryptography to provide \emph{robustness} \cite{flash-mix} --- messages
+cryptography to provide \emph{robustness}~\cite{flash-mix} --- messages
are only delivered if a threshold of the mixes agree that the batch has
been properly processed.
@@ -324,7 +325,7 @@
the adversary when an outgoing message entered the mix. Mixes `pool'
some messages from previous batches, to try to mix them as far back
as possible. These approaches force the adversary to spend more time
-and messages on the attack \cite{trickle02}. Some designs allow a
+and messages on the attack~\cite{trickle02}. Some designs allow a
pool mix to commit to its choice of randomness to allow verifying
its behavior~\cite{FGJP98}. Link encryption, as well as
% \cite{Jer2000}
@@ -485,7 +486,7 @@
longer an appealing target.
Alternatively, the mixes can periodically generate a communally random
-seed to reorganize the network \cite{casc-rep}. Thus,
+seed to reorganize the network~\cite{casc-rep}. Thus,
being able to control or sign up a node does not allow the adversary to
dictate its position in the topology. This may be a satisfactory solution,
though it is not a complete solution because not all nodes are equal:
@@ -548,9 +549,9 @@
information can be exploited by an adversary to reduce anonymity,
for example by predicting the user's behavior based on reputation
statistics, or by attracting more traffic by building a strong reputation
-or degrading the reputation of others. Placing nodes of similar reputation
+or degrading the reputation of others. Placing nodes with similar reputation
in the same layer of a stratified or cascade network, or placing them
-in the same cascade can complicate these attacks, but employed naively,
+in the same cascade, can complicate these attacks, but employed naively,
this can facilitate other attacks~\cite{casc-rep}. This
topic merits further investigation.
@@ -619,7 +620,7 @@
based on a batch of $k$ messages. That is, the entropy of a baseline
network (all-honest senders) plus hostile messages is at least the entropy
of the baseline network by itself. This is different from the pooling
-batching strategy \cite{trickle02}, where messages from the adversary
+batching strategy~\cite{trickle02}, where messages from the adversary
will influence the behavior (and thus entropy) of Alice's message.
On the other hand, directed floods can overflow node capacity. We
@@ -724,7 +725,7 @@
%It may also attract attackers to such cabals so that the net anonymity
%does not increase.
-Like stop-and-go mixes \cite{stop-and-go}, we may be able to get improved
+Like stop-and-go mixes~\cite{stop-and-go}, we may be able to get improved
anonymity by allowing Alice to choose to delay her message at a given
hop until the next batch. That is, the node would delay her message by
$t_\mathrm{batch}$ and re-introduce it at the same point in the path.
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/