[freehaven-cvs] some patches toward a final draft of sync-batching

[arma@seul.org (Roger Dingledine)]

Update of /home2/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/tmp/cvs-serv28977

Modified Files:
	sync-batching.tex 
Log Message:
some patches toward a final draft of sync-batching
still need to argue that a single cascade may be inadequate


Index: sync-batching.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.55
retrieving revision 1.56
diff -u -d -r1.55 -r1.56
--- sync-batching.tex	3 May 2004 05:42:33 -0000	1.55
+++ sync-batching.tex	24 Jun 2004 21:20:09 -0000	1.56
@@ -30,16 +30,16 @@
 \begin{document}
 %\title{The Disadvantages of Cascade Mix Networks and How to Overcome Them}
 %\title{Synchronous Batching:\\From Cascade Networks to Free Routes
-\title{Synchronous Batching:\\From Cascades to Free Routes
+\title{Synchronous Batching:\\From Cascades to Free Routes}
 %\title{Mixing in Step:\\Synchronous Batching from Cascade Networks to
 %  Free Routes
 %\title{Groove Mixing:\\Synchronous Batching from Cascade Networks to Free Routes
 %\title{Synchronous Batching:\\Beat Mixing from Cascade Networks to Free Routes
 %\title{Heartbeat Mixing: Synchronous Batching from Cascade Networks to Free Routes
 %\title{Synchronous Mixnets: From Cascades to Free Routes
-\thanks{Portions of this paper were inspired by discussions with David
-Hopwood. We invite him to be an author, but we have not been able
-to contact him. We'll keep trying.}}
+%\thanks{Portions of this paper were inspired by discussions with David
+%Hopwood. We invite him to be an author, but we have not been able
+%to contact him. We'll keep trying.}}
 %but we have been unable to contact
 %him since beginning the paper. We'll keep trying.}}
 
@@ -146,7 +146,8 @@
 its design choices affect the degree of anonymity it can provide
 \cite{trickle02}.
 We might define ideal anonymity for a mixnet to be when an attacker can
-gain no information about the linkage between messages entering and
+gain no information (beyond prior knowledge) about the linkage between
+messages entering and
 leaving the network, other than that the maximum time between them is
 equal to the maximum network latency.
 
@@ -180,12 +181,13 @@
 received, so that it cannot be delayed by an attacker.
 
 The {\em width} $w$ of a mixnet using synchronous batching
-is the number of nodes that simultaneously process messages in each hop
+is the number of nodes that simultaneously process messages from a given
+batch in each hop
 period. (If this is not constant, we can still talk about the maximum,
 minimum, and mean width.) When $w=1$, we have a cascade.
 The latency is between $\ell t_\mathrm{hop}$ and $t_\mathrm{batch} +
 \ell t_\mathrm{hop}$, depending on when the message is submitted.
-Typically we would have $t_\mathrm{hop} < t_\mathrm{batch}/\ell$,
+We might set $t_\mathrm{hop} < t_\mathrm{batch}/\ell$,
 so the latency is at most $2t_\mathrm{batch}$, independent of the
 path length.  Thus the entire batch is processed and delivered before
 the next batch enters the network. Under this constraint, we can give
@@ -232,14 +234,13 @@
 \emph{Eventually, a message is only unobservable in that group of messages
 which have this mix on the same routing position.} But in the synchronous
 design, that's not a problem because this group is large (if only one
-mix is trustworthy, $1/w$ of all messages in the batch---which is what
-it would be in a cascade network too). They conclude: \emph{If only one
-mix of a route is
+mix is trustworthy, $1/w$ of all messages in the batch). They conclude:
+\emph{If only one mix of a route is
 trustworthy, then the achievable anonymity is distinctly lower in a mix
 network compared to a synchronously working mix cascade.} The actual
 conclusion should be: If only one mix of a route is trustworthy, then
-the achievable anonymity is distinctly lower in an asynchronous mixnet
-than in a synchronous mixnet (whether it uses free routes or cascades).
+the achievable anonymity for a given topology is distinctly lower in an
+asynchronous mixnet than in a synchronous mixnet.
 
 {\bf{Determining the next mix:}} An adversary owning most nodes
 in the network can attack the honest mixes: he can link senders
@@ -269,7 +270,8 @@
 the cascade provides complete protection, a user choosing four
 nodes in the free-route network has a non-trivial chance of picking an
 entirely compromised path. But this is a false comparison. A better
-comparison would consider a network of five $\ell=4$ cascades---thus
+comparison would consider either a free-route mix network with 4 nodes,
+or a network of five $\ell=4$ cascades---so
 the cascade network also has a chance of fully-compromised paths.
 In Section~\ref{sec:graphs} we show that while each cascade in a cascade
 network of width $w$ only mixes $1/w$ of the messages from the batch,
@@ -285,7 +287,8 @@
 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}.
+all topologies, and a complete solution that is practical 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
@@ -360,9 +363,10 @@
 its input-output relationships, while the mix network as a whole still
 protects linkability with high probability.
 
-Clearly much work has been done to address blending attacks; the
-solutions apply to synchronous free-route networks
-as well as cascade networks.
+Clearly much work has been done to address blending attacks; each
+topology seems to have some plausible partial solutions.
+%solutions apply to synchronous free-route networks
+%as well as cascade networks.
 
 \section{Threat model and mixnet topologies}
 \label{sec:scenarios}
@@ -374,12 +378,13 @@
 Section~\ref{subsec:random-adversary} for more discussion on this point).
 Along with being able to control some of the nodes, our adversary can
 observe messages from senders to the mixnet and from the mixnet to
-receivers, but he cannot observe the links between honest nodes in
+receivers, but for our initial analysis we assume he cannot observe the
+links between honest nodes in
 the mixnet (in Section~\ref{subsec:average-actual} we argue that
 with high probability, observing these links will not yield much
 new information anyway).
 This paper only examines sender anonymity, though many of the advantages
-of synchronous batching carry over to receiver anonymity.
+of synchronous batching may carry over to receiver anonymity.
 
 %An adversary is assumed to only watch messages entering and leaving
 %the mixnet. This is admittedly weaker than an adversary that can
@@ -618,7 +623,8 @@
 
 It turns out that as long as $k$ of the $n$ input messages come from
 honest senders, Alice will still be assured that she can expect entropy
-based on a batch of $k$ messages. That is, the entropy of a baseline
+based on a batch of $k$ messages. That is, assuming uniform distribution
+of messages over mixes, 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
@@ -746,7 +752,7 @@
 is even worse: a single node crash blocks all message delivery.
 (We might take advantage of schemes to bypass a single failed node
 \cite{pfitzmann85}, but it's not clear how this works with the synchronous
-approach.)
+approach in all topologies.)
 Parallel cascades can be added to the network, but unlike the
 free-route, they will \emph{a priori} reduce the entropy of an input
 message for a given size mixnet batch. We must be sure to consider
@@ -916,7 +922,7 @@
 to transient failures: a late Mixminion message still arrives, whereas
 in our system a node that is down throughout $t_\mathrm{hop}$ loses all
 messages going through it. (Stratified and cascade networks have the
-the lowest chance of being down in a hop period they are needed, but
+lowest chance of being down in a hop period they are needed, but
 free-route networks lose proportionally fewer messages from a single
 down node.)  But our design can tell the user for sure whether his mail
 was delivered in the batch (and he can resend if not), whereas Mixminion's
@@ -947,9 +953,10 @@
 further analysis of the trade-offs between each topology.
 
 \section*{Acknowledgments}
-We acknowledge David Hopwood for the initial impetus and ideas; and
-we thank LiWu Chang, Camilla Fox, Rachel Greenstadt, Chris Laas, Ira
-Moskowitz, and Itamar Shtull-Trauring for probability discussions.
+We acknowledge David Hopwood for the ideas and arguments behind Sections
+2 and 3; and we thank LiWu Chang, Camilla Fox, Rachel Greenstadt,
+Chris Laas, Ira Moskowitz, and Itamar Shtull-Trauring for probability
+discussions.
 
 %======================================================================
 

***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/