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

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
+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
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$.