[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Variants on thresholds and remove some minor conflic...
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/