[freehaven-cvs] clarifying anonymity contribution from pool vs batch

[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.pdf taxonomy.tex 
Log Message:
clarifying anonymity contribution from pool vs batch


Index: taxonomy.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.pdf,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
Binary files /tmp/cvsznhakE and /tmp/cvsmdEBVb differ

Index: taxonomy.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.tex,v
retrieving revision 1.30
retrieving revision 1.31
diff -u -d -r1.30 -r1.31
--- taxonomy.tex	9 Sep 2002 21:56:09 -0000	1.30
+++ taxonomy.tex	9 Sep 2002 22:28:53 -0000	1.31
@@ -497,11 +497,6 @@
 history of events that have happened in this mix. Thus, we achieve
 the maximum anonymity $A_{max}$ when all of the messages that have ever
 passed through the mix come from different senders.
-% What about making the threshold a number of distinct senders? Would
-% help against a non-global adversary. Would totally break in a cascade
-% environment. Would have side-effects even in free-route systems, like
-% biasing mixes towards having more traffic from users and less from other
-% mixes? Hrm. Complex. Probably not worth it.
 Serjantov and Danezis carried out this analysis in \cite{Serj02}.
 
 \[
@@ -516,8 +511,10 @@
 $n$, and therefore no worse than that of a corresponding threshold
 mix.  We could assume that all the other messages may have come from
 the same sender and thus provide no anonymity, but this would be
-overly pessimistic -- the entire history of the mix is unlikely to
-consist of messages from just one sender.
+overly pessimistic --- the entire history of the mix is unlikely to
+consist of messages from just one sender. Thus the minimum anonymity of
+a threshold $n$ pool mix is likely higher than that of a simple threshold
+$n$ mix.
 
 \paragraph*{Blending Attack Behaviour:} 
 In general, the blending attack has two phases: flushing the mix so
@@ -618,8 +615,8 @@
 potentially, a whole host of other features). Of course, in practice,
 a record of only the last few rounds gives a good approximation.
 
-The minimum anonymity of a timed pool mix is clearly smaller than that
-of a threshold pool mix (unless the threshold is $1$).  If the pool is
+The minimum anonymity of a timed pool $f$ mix is clearly smaller than that
+of a threshold pool $f$ mix (unless the threshold is $1$).  If the pool is
 small relative to the batch size, then the bulk of the anonymity comes
 from mixing the target message with the batch of incoming messages,
 not from mixing it with the messages in the pool. Because the timed
@@ -627,11 +624,13 @@
 message, its minimum anonymity should be considered to be very much
 worse than that of the threshold pool mix unless a large pool is
 maintained. 
-%As was shown in \cite{Serj02}, the anonymity contribution
-%of pool messages is quantifiably greater than those of batch messages.
-%So a larger pool is always preferable from this perspective. Of course
-%this would have an impact on message delay, reducing one of the
-%potential advantages of having a timed mix.
+
+Assuming reasonable parameters, \cite{Serj02} shows that the anonymity
+contribution of pool messages is quantifiably greater than that of
+messages in a new batch. That is, increasing the pool size has a larger
+effect on anonymity than increasing the batch size. Of course, increasing
+the pool size also increases the message delay --- thus weakening one
+of the potential advantages of having a timed mix.
 
 \paragraph*{Blending Attack Behaviour:}
 Two flavours of blending attack are possible on this mix.  The adversary
@@ -927,8 +926,9 @@
 coordinated network-wide policy that all users and mixes follow.}
 
 This dummy policy still allows an attacker to flush the mix free of
-good messages and be certain about it. However, once the good message
-is inserted into the mix, at every round at least one good message comes
+good messages and be certain about it. However, once the target message
+is inserted into the mix, at every round at least one message unknown to
+the attacker comes
 out. Naturally, when two messages come out, the attacker knows that the
 target message was one of those, but he does not know which one. If the
 attacker finishes here, he has reduced the anonymity of the message to $1$
@@ -1105,6 +1105,10 @@
 
 \end{tabular}
 \end{center}
+
+%\section*{Acknowledgements}
+% Nick Mathewson, Len Sassaman, Peter Palfrader, Adam Shostack
+% others?
 
 \bibliography{taxonomy}
 

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