[freehaven-cvs] patches suggested by adam shostack

[arma@seul.org (Roger Dingledine)]

Update of /home/freehaven/cvsroot/doc/batching-taxonomy
In directory moria.seul.org:/home/arma/work/freehaven/doc/batching-taxonomy

Modified Files:
	taxonomy.tex 
Log Message:
patches suggested by adam shostack


Index: taxonomy.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.tex,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -d -r1.24 -r1.25
--- taxonomy.tex	6 Sep 2002 18:51:34 -0000	1.24
+++ taxonomy.tex	6 Sep 2002 20:56:50 -0000	1.25
@@ -227,7 +227,8 @@
 \item The mixes take a constant time to fire (send messages out).
 
 \item The mixes have limited physical memory and so can only contain a
-finite number of messages.
+finite number of messages. Further, they have finite bandwidth, so can
+only receive a certain number of messages in a given amount of time.
 
 \item Mixes prevent message replays.
 
@@ -257,7 +258,7 @@
 \paragraph*{Parameters:} $n$, threshold.
 
 \paragraph*{Flushing Algorithm:} 
-When the mix collects $n$ messages, it fires.
+When the mix collects $n$ messages, it fires (delivers all $n$).
 
 \paragraph*{Message Delay:} 
 The minimum delay is $\epsilon$ (the target message arrives when there
@@ -590,7 +591,8 @@
 
 \paragraph*{Anonymity:}
 The timed nature of this mix allows an arbitrarily large number (only
-limited by the memory capacity of the mix) of messages to be mixed
+limited by the memory and bandwidth capacity of the mix) of messages to
+be mixed
 together.  If we assume a constant rate $r$ of message arrival, the
 anonymity provided by this mix can be calculated in just the same way
 as for the threshold case; but we leave this calculation for future
@@ -632,7 +634,8 @@
 ($b$) since the probability of flushing the mix by this method is
 $\frac{f^2}{b+f}$ (supposing there were $f$ good messages in the mix
 initially).\footnote{As previously mentioned, in practice there is an
-upper limit on $b$ due to the finite memory capacity of the mix.}
+upper limit on $b$ due to the finite memory capacity and/or bandwidth
+of the mix.}
 However, this aims to flush the good messages out of the mix in one
 round, and therefore a maximum of $t$ seconds. Thus the entire attack
 can be executed in less than $2t$ seconds with an arbitrarily high
@@ -818,7 +821,7 @@
 good messages in the mix initially, and he can never be exactly
 sure of that figure (unless he has the whole history).
 
-While introducing randomness is a promising direction, note that it would
+While introducing randomness appears to be a promising direction, note that it would
 not increase the cost of the attack significantly (if at all). Thus,
 we shall not pursue it further.
 
@@ -932,22 +935,12 @@
 adversary can distinguish with better than even probability between a
 dummy and a legitimate message.
 
-%if a mix doesn't
-%know about even a single user when it generates a dummy, an adversary
-%can be sure that messages arriving at that user are not dummies.
-
 Note that constant rate dummy policies do not affect the blending
 attack properties provided by the mixes themselves. Constant dummies
 simply magnify the scale of the attack without changing the
 properties. For example, even with the Mixmaster cover traffic policy,
 a threshold mix network can be attacked in $\epsilon$ time (but a very
 large number of messages).
-% What if we always filled the outgoing batch up to some threshold?
-% Then the issue wouldn't be orthogonal, right? Hrm. Padding question;
-% hard. But I still don't buy that dummies are completely orthogonal
-% to the blending attack properties, since mixes can generate dummies
-% and thus make it harder to attack them (and it's easier to generate
-% dummies in some mix models than others).
 
 \subsection{Making Messages Unrecognizable}
 
@@ -965,7 +958,8 @@
 nodes can choose to rewrap a message and send it through a few randomly
 chosen new hops --- so even the sender cannot be sure of recognizing
 his message as it leaves the mix. This approach could help complicate
-blending attacks; we leave its analysis for future work.
+blending attacks, but also introduces reliability risks; we leave its
+analysis for future work.
 
 
 \section{Limitations of Stop-and-Go Mixes}

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