[freehaven-cvs] Stop-and-go vs. alpha

[syverson@xxxxxxxx]

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

Modified Files:
	alpha-mixing.tex 
Log Message:

Stop-and-go vs. alpha

Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- alpha-mixing.tex	10 Mar 2006 22:01:49 -0000	1.10
+++ alpha-mixing.tex	10 Mar 2006 23:04:17 -0000	1.11
@@ -568,10 +568,10 @@
 while alpha mixing is based on individual choices made by the sender.
 We now turn to how to combine these features.
 
-\section{Dynamic-Alpha Mixes}
+\section{Dynamic-Alpha Mixing and Other Variations}
 
 The prior work that is probably most similar to alpha mixing is
-stop-and-go mixing~\cite{stop-and-go}. In stop-and-go mixes, the sender
+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
 within the interval, it is sent at the end of the interval, otherwise
 it is discarded. This is similar to the timed deterministic-alpha mix
@@ -579,6 +579,37 @@
 mixnet depends on it being entirely synchronized. Alpha mixes offer
 predictable delivery times, but will still mix and deliver messages
 even if some nodes in the path are not adequately synchronized.
+On the other hand, an adversary that is global-passive except for being able
+to delay messages from a single sender could, e.g., batch these up and
+send them through an alpha mixnet all at once. Unless they all have
+$\sum \alpha = 0$ the adversary will gain limited information from this,
+but can in principle still learn more than from a stop-and-go mixnet.
+
+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
+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
+sensitive so each has $\sum \alpha^{(i)}_0$ chosen uniformly at random
+from a range of $0$ to $10$. An adversary that can block all messages
+from Alice during this period and send them into the network will see
+approximately ten messages delivered to Bob immediately followed by
+approximately ten messages in each of the next nine time intervals.
+However, we need not resort to assuming a synchronized network.
+Instead of including any timestamps, Alice could choose $\sum
+\alpha^{(i)}_0$ from some private distribution on a private range (not
+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.
+
+
+
+it may be possible to conduct active attacks
+on a message in an alpha mixnet by
 
 Both timed deterministic-alpha mixes and stop-and-go mixes have the
 vulnerability of all purely timed mixes: they provide no anonymity

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