[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] touch up some more points; lots more to go
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/