[minion-cvs] Fix definition of ideal anonymity and formula for synch...

[hopwood@seul.org]

Update of /home/minion/cvsroot/doc
In directory moria.seul.org:/tmp/cvs-serv14284

Modified Files:
	minion-design.tex 
Log Message:
Fix definition of ideal anonymity and formula for synchronous batching latency.

Index: minion-design.tex
===================================================================
RCS file: /home/minion/cvsroot/doc/minion-design.tex,v
retrieving revision 1.51
retrieving revision 1.52
diff -u -d -r1.51 -r1.52
--- minion-design.tex	8 May 2002 06:39:32 -0000	1.51
+++ minion-design.tex	8 May 2002 13:34:26 -0000	1.52
@@ -876,7 +876,7 @@
 of opportunity for this attack.
 
 A more complete solution to partitioning attacks may be possible by
-using the ``synchronous batch'' approach described in
+using the ``synchronous batching'' approach described in
 Section \ref{subsec:batching}; this is a subject for future research.
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -1076,18 +1076,23 @@
 %attention to it yet.]
 
 A MIX-net design groups messages into batches and chooses paths; the
-approaches it uses affect the degree of anonymity it can provide. We
-might define ideal anonymity for a MIX-net to be when each message leaving
-(resp. entering) the network could correspond with uniform probability
-to any message entering (resp. leaving) the network, during a period
-approximately equal to the maximum network latency.
+approaches it uses affect the degree of anonymity it can provide
+\cite{batching-taxonomy}.
+We might define ideal anonymity for a MIX-net to be when an attacker can
+gain no information 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.
+
+% Silly newbie mistake: the probability is the same as a priori, not
+% uniform. That's what I get for writing security definitions at 1:00
+% in the morning. -DH
 
 This ideal is not achieved by protocols like Mixmaster that use random
 delays: if the maximum latency of such a network is $t$, then the
 anonymity set of a message leaving the network may be much smaller
 than all messages that entered over a time $t$.
 % This is handwaving, and the problem is more that the distribution
-% isn't uniform rather than the actual size of the anonymity set.
+% isn't right rather than the actual size of the anonymity set.
 % It'll do for the time being. -DH
 
 Also, because Mixmaster is both {\em asynchronous} (messages can enter and
@@ -1095,7 +1100,6 @@
 the attacks described in Section 4 of \cite{disad-free-routes}.
 % Should really summarise them, but I don't have time :-(
 We would like to explore a
-%One possible approach that we want to explore using Mixminion is a
 strategy called {\em synchronous batching}. This approach seems to prevent
 these attacks even when free routes are used, and seems to improve the
 trade-off between latency and anonymity.
@@ -1114,8 +1118,7 @@
 
 The latency is between $\ell t_\mathrm{hop}$ and $t_\mathrm{batch} +
 \ell t_\mathrm{hop}$, depending on when the message was submitted.
-Typically we would have $t_\mathrm{hop} < t_\mathrm{batch}/n$, where
-$n$ is the number of MIXes in the network, so the
+Typically we would have $t_\mathrm{hop} < t_\mathrm{batch}/\ell$, so the
 latency is at most $2t_\mathrm{batch}$ independent of the path length
 $\ell$.