[freehaven-cvs] clean up and rearrange, still can"t address hard que...

[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:
clean up and rearrange, still can't address hard questions


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- sync-batching.tex	13 Jan 2004 15:03:14 -0000	1.3
+++ sync-batching.tex	18 Jan 2004 08:41:26 -0000	1.4
@@ -23,9 +23,9 @@
 \author{Roger Dingledine\inst{1} and Vitaly Shmatikov\inst{2} and Paul Syverson\inst{3}}
 % XXX add a footnote here about David Hopwood, how he should be an
 %     author, but we can't find him (but we'll keep trying).
-\institute{The Free Haven Project, \email{arma@freehaven.net} \and
+\institute{The Free Haven Project \email{(arma@freehaven.net)} \and
 Vitaly's affiliation \and
-Naval Research Lab, \email{syverson@itd.nrl.navy.mil}}
+Naval Research Lab \email{(syverson@itd.nrl.navy.mil)}}
 
 \maketitle
 \centerline{\LARGE\bf *DRAFT* --- not for publication}
@@ -43,21 +43,20 @@
 message happens to stand out from the others \cite{disad-free-routes},
 and an active adversary can manipulate the network to separate one
 message from the others via blending attacks \cite{trickle02}.
-
 Berthold et al argue in \cite{disad-free-routes} that partitioning
-opportunities arise because the networks use a \emph{free-route} topology:
-one where the sender can choose the mixes that make up her message's
-path. They suggest instead a \emph{cascade} topology, where all senders
-use the same fixed path through the mix network.
+opportunities arise because the networks use a \emph{free-route}
+topology---one where the sender can choose the mixes that make up her
+message's path. They suggest instead a \emph{cascade} topology, where
+all senders use the same fixed path through the mix network.
 
 Here we argue that the cascade design resolves the attacks not because
-of the network topology but because of a property of its batching
+of its network topology but because of a property of its batching
 strategy. We investigate this \emph{synchronous batching} approach in a
-variety of topologies, and find that it provides the following advantages
-over Mixminion:
+variety of topologies, and find that it provides the following properties:
+%over Mixminion:
 
 \begin{tightlist}
-\item It prevents the attacks in \cite{disad-free-routes} even when free
+\item It prevents the attacks in \cite{disad-free-routes}, even when free
 routes are used.
 \item It provides comparable latency to a cascade topology, even when free
 routes are used.
@@ -73,9 +72,9 @@
 
 \end{tightlist}
 
-We investigate using synchronous batching in three topologies: cascade,
-restricted-route matrix, and free-route. We find that the restricted-route
-matrix topology provides the highest expected anonymity of these three.
+We investigate synchronous batching in three topologies: cascade,
+systolic array (restricted route), and free-route. We find that the foo
+topology provides the highest expected anonymity of these three.
 
 %Specifically, whereas
 %with \emph{asynchronous batching} strategies each message is forwarded
@@ -99,13 +98,14 @@
 %then the anonymity set of a message leaving the network may be much
 %smaller than all messages that entered over a time $t$.
 %More precisely, 
-the probability that a message leaving the network corresponds to a given
+the probability that an output message corresponds to a particular
 input message might be considerably higher than for other messages that
 have entered over a time $t$.
-(In principle, the maximum latency for a message that has just been
+(In principle, because of its pool mode, the maximum latency for a
+message that has just been
 sent could be infinite, but that's not a significant improvement
 in practice: if the probability of a given latency $t$ drops off
-exponentially with $t$, for example, then so does the probability that
+exponentially with $t$, then so does the probability that
 a message that is leaving the network could have been sent that long
 ago \cite{Diaz02,Serj02}.)
 
@@ -126,7 +126,7 @@
 to their final destinations $\ell$ hop periods later. Each layer of a
 message, once decrypted, specifies the hop period in which it must be
 received, so that it
-cannot be delayed by an attacker. % (which would be fatal for this design).
+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
@@ -185,8 +185,8 @@
 
 \subsection{S-G mixes}
 
-[they do delays, which improve anonymity. no reason why we couldn't
-too, really.]
+[the sender chooses to delay at certain nodes, which improves anonymity.
+no reason why we couldn't too, really.]
 
 Possible extension: for the purpose of discussion, let's use
 t_batch = 3 hours and t_hop = 1 hour / n. Then the latency is between
@@ -238,37 +238,42 @@
 ok with it, so compromising the ones that are ok with it will give you
 a better shot at owning an exit node in the resulting topology.)
 
-assume we have 16 or so nodes, each of which can comfortably handle
+assume we have 16 nodes, each of which can comfortably handle
 1/4 of the traffic, but none of which can comfortably handle all of the
 traffic. so what topology is best?
 
-We use the entropy-based approach from \cite{Diaz02,Serj02}.
+We use the information theory approach from \cite{Diaz02,Serj02} to
+measure expected entropy for each scenario.
 
-scenario 1: cascade network (network of cascades)
+\subsection{Scenario 1: network of cascades}
 walk us through calculating entropy for a 2x2 cascade network.
 
-scenario 2: matrix
+give us a figure of this topology.
+
+\subsection{Scenario 2: systolic array}
 walk us through calculating entropy for a 2x2 matrix (4 nodes)
 
-scenario 3: practical free-route
-walk us through calculating entropy for a 4x4 free-route (4 nodes)
+give us a figure of this topology.
+
+\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.
 
-scenario 4: latin square free-route
-
-discuss robustness: scenario 4 is clearly least robust. 1-3 are the same,
-maybe 3b is a bit bad.
+give us a figure of this topology.
 
-also discuss how scenarios 3-4 make a different assumption about the
+\subsection{further Assumptions}
+also discuss how scenario 3 makes a different assumption about the
 adversary, since watching all the nodes requires more power than just
 watching the entry and exit columns.
 
 also, notice that since the batch period is large and the hop period is
 short, most of the nodes will be idle nearly all the time in scenarios
 1 and 2, whereas they get used at every hop in scenarios 3 and 4. so
-scenario 4 is not so farfetched, if we can convincing ourselves that
+scenario 4 is not so farfetched, if we can convince ourselves that
 the reliability issues aren't bad.
 
 \section{Graphs and Analysis}
@@ -276,9 +281,29 @@
 show entropy graphs. talk a bit about which one's best for which
 situation.
 
+* compare the entropy between 16 nodes: cascade, SA, and free-route
+
+\section{Other considerations}
+
+\subsection{Robustness}
+scenario 4 is clearly least robust. 1-3 are the same,
+maybe 3b is a bit bad.
+
+Two issues: one is robustness with respect to a single message
+going through. How likely is it to arrive on time?
+But there's a deeper issue: in asynchronous-batching designs, a
+late message still arrives. in this system, a late message is lost.
+this is not very convenient for the user.
+
+\subsection{Mixing with previous and future batches}
+The free-route topology can add a new batch at every hop,
+increasing the anonymity everybody gets. maybe.
+
+\subsection{Not enough input messages}
 does number of messages influence things? that is, does too few messages
 screw things up more for one topology than for another?
 
+\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
 baseline network by itself? that would be neat.
@@ -288,6 +313,8 @@
 talk about the possible uses of some minimum level of padding on each
 link.
 
+\subsection{
+
 \section{Extensions and Future Work}
 
 In practice, several considerations have to be balanced when choosing

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