[freehaven-cvs] touch up some more points; lots more to go

[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:
touch up some more points; lots more to go


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- sync-batching.tex	18 Jan 2004 08:41:26 -0000	1.4
+++ sync-batching.tex	20 Jan 2004 09:23:30 -0000	1.5
@@ -17,7 +17,7 @@
     }}{\end{list}}
 
 \begin{document}
-\title{Improved Anonymity via Synchronous Batching}
+\title{Improved Anonymity from Synchronous Batching}
 % need a better title
 
 \author{Roger Dingledine\inst{1} and Vitaly Shmatikov\inst{2} and Paul Syverson\inst{3}}
@@ -127,14 +127,10 @@
 message, once decrypted, specifies the hop period in which it must be
 received, so that it
 cannot be delayed by an attacker.
-%[[Explain why this prevents the attacks in [disad-free-routes], even
-%for free-route networks. Also explain why we need to use a hybrid
-%free-route/cascade approach (otherwise the anonymity set is limited by
-%the bandwidth that can be handled by a single cascade).]]
 
-The set of messages sent to a node in a given hop period is called a
-mini-batch, to distinguish it from the set of messages being sent
-through the network as a whole. % [[need better name?]]
+%The set of messages sent to a node in a given hop period is called a
+%mini-batch, to distinguish it from the set of messages being sent
+%through the network as a whole. % [[need better name?]]
 
 Define the {\em width} $w$ of a mix network using synchronous batching to
 be the number of nodes that simultaneously process messages in each hop
@@ -152,6 +148,10 @@
 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.
 
+[Or for free-route topology, we could let t_hop be t_batch, and now
+it takes \ell batch times to go through, but it mixes with the other
+batches.]
+
 Let $T_\mathrm{batch}$ be the expected throughput in a single batch period,
 i.e.~the number of messages that go through the network in a batch.
 We can give nodes the maximum opportunity to make use of the available
@@ -183,6 +183,8 @@
 explain the current free route node selection. motivation for
 loosely federated network. number of nodes.
 
+\subsection{Danezis's restricted routes paper}
+
 \subsection{S-G mixes}
 
 [the sender chooses to delay at certain nodes, which improves anonymity.
@@ -226,6 +228,18 @@
 paul: can you explain how this approach differs from the robust mix
 designs, and why it's still reasonably practical?
 
+"I'm not sure it's directly
+relevant. Generally I think people do a bunch of shuffle proofs, etc.
+If the answer doesn't come out as desired, the threshold number of
+guys won't decrypt the final set of messages (i.e., the whole batch
+gets dropped). Also, I think this only applies to re-encryption mixes,
+so, e.g.,  current remailer networks couldn't be based on them."
+
+
+\subsection{Reliable mixes}
+
+reputation systems a la mix-acc and casc-rep.
+
 \section{Scenarios}
 
 explain threat model: adversary can see all incoming and outgoing
@@ -257,9 +271,6 @@
 
 \subsection{Scenario 3: free-route}
 walk us through calculating entropy for a 4x2 free-route (4 nodes)
-scenario 3b: practical free-route but message never stays at the same
-hop adjacently. this is better for high-adversary-percentage, worse
-for low-adversary-percentage? or always better?
 point out that we could use 16x4 for a fair comparison, or we could
 use 16x\ell to get more or less anonymity.
 
@@ -285,6 +296,11 @@
 
 \section{Other considerations}
 
+\subsection{
+scenario 3b: practical free-route but message never stays at the same
+hop adjacently. this is better for high-adversary-percentage, worse
+for low-adversary-percentage? or always better?
+
 \subsection{Robustness}
 scenario 4 is clearly least robust. 1-3 are the same,
 maybe 3b is a bit bad.
@@ -303,6 +319,34 @@
 does number of messages influence things? that is, does too few messages
 screw things up more for one topology than for another?
 
+More specifically, show that the influence from the percent of corrupt
+nodes is the critical factor on entropy, and that the influence from the
+random path choices of the other senders doesn't matter much on entropy.
+
+For large batch sizes like n=128, I think we all believe it. Paul and I
+just want to find a principled way of arguing it, so the paper doesn't
+leave the issue open.
+
+And for small batch sizes like n=2, I think it's clear that the other
+path influences Alice's entropy a whole lot.
+
+So where is the break-even point -- the point where the influence
+from corrupt nodes matches the influence from path choices? And is our
+intuition correct that as you move away from the break-even point the
+influence from the other paths goes quickly to 0?
+
+The reason why it matters is because there's a significant camp in the
+anonymity community that believes cascades are the way to go. This paper
+disputes that idea, so they're going to be suspicious of it. And the way
+we're comparing SA's to cascades neglects the issue of entropy loss by
+bad luck in the paths chosen by the other senders. In effect, they might
+argue we're comparing apples to oranges and have no result at all.
+
+I just reread George's paper, particularly section 5.1. I think he has
+the beginnings of a solution there.
+http://freehaven.net/anonbib/#danezis:pet2003
+
+
 \subsection{Blending and flooding attacks}
 active attacks can mess up the calculations? or is the entropy with a
 baseline network plus hostile messages the same as the entropy of the

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