[freehaven-cvs] Variants on thresholds and remove some minor conflic...

[syverson@xxxxxxxx]

Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/tmp/cvs-serv14743

Modified Files:
	alpha-mixing.bib alpha-mixing.tex 
Log Message:

Variants on thresholds and remove some minor conflicts with what Roger
just checked in.

Index: alpha-mixing.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.bib,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- alpha-mixing.bib	10 Mar 2006 23:20:30 -0000	1.5
+++ alpha-mixing.bib	10 Mar 2006 23:59:23 -0000	1.6
@@ -4,19 +4,10 @@
 
 @Book{devroye86,
   author = 	 {Luc Devroye},
-  ALTeditor = 	 {},
   title = 	 {Non-Uniform Random Variate Generation},
   publisher = 	 {Springer-Verlag},
-  year = 	 {1986},
-  OPTkey = 	 {},
-  OPTvolume = 	 {},
-  OPTnumber = 	 {},
-  OPTseries = 	 {},
-  OPTaddress = 	 {},
-  OPTedition = 	 {},
-  OPTmonth = 	 {},
-  note = 	 {Available from: \url{http://cgm.cs.mcgill.ca/~luc/rnbookindex.html}},
-  OPTannote = 	 {}
+  year = 	 1986,
+  note = 	 {Available from: \url{http://cgm.cs.mcgill.ca/~luc/rnbookindex.html}}
 }
 
 @inproceedings{Acquisti04,

Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -d -r1.15 -r1.16
--- alpha-mixing.tex	10 Mar 2006 23:51:32 -0000	1.15
+++ alpha-mixing.tex	10 Mar 2006 23:59:23 -0000	1.16
@@ -193,7 +193,7 @@
 Similarly, one can have a threshold-and-timed mix
 to reduce the effective rate of flooding attacks~\cite{trickle02}.
 Even more complex variants of these designs are discussed in
-Section~\ref{sec:dynamic-alpha}.
+Section~\ref{sec:beta-alpha}.
 
 \subsection{Deterministic-alpha mix:\\
 anonymity against a local passive adversary}
@@ -574,12 +574,16 @@
 0$.  For more sensitive traffic, we might initially try to follow
 networks such as Mixminion and Mixmaster. But how can we do that? 
 These use a dynamic batching strategy in which messages are chosen
-for the current batch randomly by the mix from a collective pool
+for the current batch randomly by the mix from a collective pool,
 while alpha mixing is based on individual choices made by the sender.
-We now turn to how to combine these features.
+We now turn to various generalizations on the basic deterministic-alpha
+mix design, including ways to combine these features.
+
+\section{Beta Alpha: Variations on Alpha Mixing}
+\label{sec:beta-alpha}
+
+\subsection{Preventing end-to-end timing on alpha mixnets}
 
-\section{Dynamic-Alpha Mixing and Other Variations}
-\label{sec:dynamic-alpha}
 The prior work that is probably most similar to alpha mixing is
 stop-and-go mixing~\cite{stop-and-go}. In stop-and-go mixing, the sender
 gives to each mix in the path a time interval. If the message arrives
@@ -597,7 +601,7 @@
 
 We could include timestamps along with the $\alpha_0$ that each mix
 receives with a message and require that the message be dropped if it
-arrives more than some delta from the timestamp.  This would make
+arrives more than some delta from the timestamp. This would make
 timed alpha mixes essentially equivalent to stop-and-go mixes, which
 might prove useful against timing correlations by such an adversary.
 For example, Alice might send one hundred messages to Bob that are
@@ -612,9 +616,36 @@
 necessarily including $0$). This would (1) prevent such an attack if
 the adversary cannot predict her distribution, (2) still have as much
 predictability on delivery time as stop-and-go mixes, and (3) unlike
-stop-and-go still allow eventual delivery of all messages not
-completely blocked. Our focus in this paper, however, is not
-end-to-end timing attacks, and we will say no more about them.
+stop-and-go, still allow eventual delivery of all messages not
+completely blocked. We are not primarily focused in this paper
+on end-to-end timing attacks, and we will say no more about them.
+
+\subsection{Variations on deterministic-alpha mixing}
+
+In the basic threshold deterministic-alpha mix, if there are
+$\mbox{\emph{threshold}} = t$ messages in alpha levels $0$ through
+$n$, all of the messages in levels $0$ through $n$ will be sent at
+once; however, they will not be mixed. The mix will send all messages
+with $\alpha = 0$, lower the stack, send the next batch of messages
+that now have $\alpha = 0$, etc. An adversary may not know exactly
+where level $i$ ends and level $i+1$ begins because there may be more
+than $t$ messages in a given level, but if more than $t$ messages
+emerge he can know that the last messages to emerge were considered
+more sensitive by there senders than the first, in a stepped linear
+order of sensitivity. And by sending in messages of his own at known
+alpha levels above $0$ the adversary can learn the exact levels of the
+messages that emerge between his messages at that alpha level. Then,
+by flooding first $\alpha = n$, then $\alpha = n-1$, \ldots, then
+$\alpha = 0$, the adversary can guarantee a flush of the mix all the
+way up to $\alpha = n$ with a knowledge of the alpha level of most of
+the messages.
+
+The simplest solution is to simply mix all messages that
+
+We could require that the firing of the mix be threshold-and-timed.
+This would prevent the adversary from triggering a
+stack dump by only allowing messages of one alpha level to emerge
+in one time interval.
 
 
 

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