[freehaven-cvs] show another of the disad-free-routes arguments to b...

[arma@seul.org (Roger Dingledine)]

Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching

Modified Files:
	sync-batching.tex 
Log Message:
show another of the disad-free-routes arguments to be wrong.
somebody should verify this one.


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -d -r1.15 -r1.16
--- sync-batching.tex	21 Jan 2004 23:08:24 -0000	1.15
+++ sync-batching.tex	21 Jan 2004 23:47:11 -0000	1.16
@@ -208,7 +208,7 @@
 
 Berthold et al.~argue \cite{disad-free-routes} that cascades are safer
 than free-route mix networks against a strong adversary who watches all
-links and controls many of the mixes. We address each of their attacks
+links and controls many of the mixes. We refute each of their attacks
 below with respect to a free-route mix network that uses synchronous
 batching.
 
@@ -247,18 +247,19 @@
 as they use synchronous batching, they are not vulnerable to this
 particular attack.
 
-{\bf{Probability of Unobservability:}} The authors show that the cascade
-topology optimizes for the case that only one mix node is honest. They
-give an equation to calculate the chance that a user in a free-route
-system with 75\% compromised nodes will pick a length-4 path of only
-compromised mixes.
-
-[I'm not sure what to do with this one. It's clear that we're looking at
-things as "for each node, 75\% chance compromised, and they're looking at
-it as "we know 3 of the 4 are bad". Also, I feel that comparing a 16-node
-free-route with 12 nodes bad to a 16-node cascade network with 12 nodes
-bad is more fair, and maybe also more revealing. Thoughts? This is perhaps
-a form of anonymity-robustness that Paul has been thinking about. -RD]
+{\bf{Probability of Unobservability:}} The authors explain that the
+cascade topology optimizes for the case that only one mix node is
+honest. They compare a 4-node cascade with 3 compromised nodes to a
+20-node free-route mix network with 75\% compromised nodes, and find that
+whereas 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 cascade network with 20 nodes---thus
+the cascade network also has a chance of fully-compromised paths. In
+Section~\ref{sec:graphs} we show that whereas the cascade network only
+mixes $1/w$ of the messages in each cascade, a free-route network can
+mix all the messages from the batch and thus achieves significantly
+stronger anonymity even with 75\% compromised nodes.
 
 {\bf{Active Attacks:}}
 
@@ -361,6 +362,7 @@
 the reliability issues aren't bad.
 
 \section{Graphs and Analysis}
+\label{sec:graphs}
 
 show entropy graphs. talk a bit about which one's best for which
 situation.

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