[freehaven-cvs] change all the notation at the last moment.

[arma@xxxxxxxx]

Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/home/arma/work/freehaven/doc/alpha-mixing

Modified Files:
	alpha-mixing.tex 
Log Message:
change all the notation at the last moment.
ha ha, that will teach them to leave me alone with the paper.


Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.30
retrieving revision 1.31
diff -u -d -r1.30 -r1.31
--- alpha-mixing.tex	11 Mar 2006 03:43:52 -0000	1.30
+++ alpha-mixing.tex	11 Mar 2006 05:01:17 -0000	1.31
@@ -173,7 +173,7 @@
 $\alpha=0$ messages is randomly permuted before they are sent.}  All
 remaining messages have their $\alpha$ decremented by one. New
 messages that arrive before the next firing are buffered based on
-their initial $\alpha_0$ and are placed at the according $\alpha$ level.
+their initial $\alpha$ and are placed at the according $\alpha$ level.
 
 \paragraph{Threshold deterministic-alpha mix:}
 This is the same as the timed version, except that the
@@ -207,7 +207,7 @@
 
 We assume the adversary does not know the specific alpha of any
 message entering the mix, e.g., that this is provided to the mix
-encrypted together with the message. However we do allow that the
+encrypted together with the message. However, we do allow that the
 adversary might know the strategy by which alpha was chosen; we
 examine this issue further in Section~\ref{sec:attacker-knowledge}. What
 should that strategy be? It would seem that choosing higher alphas
@@ -223,10 +223,10 @@
 \begin{proof}
   Suppose messages occur with some distribution of alphas in a mix
   with firing threshold $n$.  A sender will assign to message $M$ an
-  initial $\alpha_{M,0}$ for a particular mix in a given position in the
+  initial $\alpha_{M}$ for a particular mix in a given position in the
   message's path.  Suppose the adversary knows the strategy chosen by
   the sender.  Assume the choice of strategies are between choosing
-  $\alpha_{M,0}$ from either a range of $0$ to $j$ or a range of
+  $\alpha_{M}$ from either a range of $0$ to $j$ or a range of
   $0$ to $k > j$. The anonymity set size increases by $n(k-j)$ if the
   broader range is chosen. (In information-theoretic terms, the
   entropy has increased by $\log(n(k-j)$.) If the adversary does not
@@ -241,29 +241,29 @@
 \end{proof}
 
 If the adversary does know the strategy (although still not the actual
-$\alpha_0$) for each message, then the anonymity of $M$ is
-unaffected by the strategy that other messages use for choosing $\alpha_0$
+initial $\alpha$) for each message, then the anonymity of $M$ is
+unaffected by the strategy that other messages use for choosing $\alpha$
 in a steady-state network. However, if the strategies are not known,
-then choosing $\alpha_0$ from a broader range increases the anonymity
+then choosing $\alpha$ from a broader range increases the anonymity
 for other messages in the mix as well, although it is difficult to say
 by how much. If the distribution of strategies across all
 messages in the mix at any time is known to the adversary, however,
-then it is clear that increasing the range from which $\alpha_0$ is
+then it is clear that increasing the range from which $\alpha$ is
 chosen for any unknown one of those messages increases the uncertainty
 about the future batch in which any of the messages still in the mix
 will emerge. Thus,
 
 \begin{claim}
   Assume a set of messages in a steady-state deterministic-alpha mix.
-  Assume the $\alpha_{M,0}$ for any message $M$ is chosen uniformly
+  Assume the $\alpha_{M}$ for any message $M$ is chosen uniformly
   at random from the range
-  given by $0 \leq \alpha_{M,0} \leq k_{M,0}$.
+  given by $0 \leq \alpha_{M} \leq k_{M}$.
   Then anonymity increases for every message $M$ in the mix if any
-  $k_{M',0}$ increases.
+  $k_{M'}$ increases.
 \end{claim}
 
 In summary, for threshold mixes or steady-state timed mixes, choosing
-$\alpha_0$ from a broader range improves the anonymity for that message
+$\alpha$ from a broader range improves the anonymity for that message
 whether the adversary knows one's strategy or not.  And, if the
 adversary knows nothing about the strategies of choosing alphas or
 knows simply the distribution of strategies, then increasing the
@@ -289,8 +289,8 @@
 \ldots o_{y,2}$ came out.
 
 $\alpha(x)$ is the set of possible alphas of message $x$ as known by
-the attacker. Note that if the attacker knows nothing, then $\forall x
-\alpha(x) = {0,1}$
+the attacker. Note that if the attacker knows nothing, then $\forall x,\ 
+\alpha(x) = \{0,1\}$
 
 Our target message is $o_{1,2}$. The sender anonymity set (in
 messages) is:
@@ -313,15 +313,15 @@
 attacker possibilistic knowledge about the alphas of the messages, we
 now allow him (better) probabilistic knowledge.
 
-Notation: call $x_{\alpha}$ the alpha in message $x$. Hence the
-attacker knows the probability distributions $P(x_{\alpha}=a)$ for
-every message $x$ with $a$ ranging from 0 to $a_{max}$. 
+Notation: call $\alpha_M$ the alpha in message $M$. Hence the
+attacker knows the probability distributions $P(\alpha_M=a)$ for
+every message $M$ with $a$ ranging from 0 to $a_{max}$.
 
 Now, the anonymity probability distribution:
 
 \[
-\mbox{Normalise}(\{p | x \in I_1 \wedge p = P(x_{\alpha}=0)\} \cup 
-\{p | x \in I_2 \wedge p = P(x_{\alpha}=1)\})
+\mbox{Normalise}(\{p | M \in I_1 \wedge p = P(\alpha_M=0)\} \cup 
+\{p | M \in I_2 \wedge p = P(\alpha_M=1)\})
 \]
 
 and the anonymity is the entropy of this distribution. Clearly, the
@@ -425,9 +425,9 @@
 
 If we wish to guarantee that neither the first nor the last mix can
 locally know anything the about sensitivity level of a message, we can
-simply stipulate for message $M$ that $\alpha^{(0)}_{M,0} =
-\alpha^{(n)}_{M,0} = 0$ (for a path length of $n+1$). Similarly we
-could stipulate that $\alpha^{(1)}_{M,0} = \alpha^{(n-1)}_{M,0} \leq
+simply stipulate for message $M$ that $\alpha^{(0)}_{M} =
+\alpha^{(n)}_{M} = 0$ (for a path length of $n+1$). Similarly we
+could stipulate that $\alpha^{(1)}_{M} = \alpha^{(n-1)}_{M} \leq
 1$, etc.  The tradeoff is that with each such move we are reducing
 what an adversary observing just the endpoints can learn about
 sensitivity of messages, but fewer nodes in the center learn more
@@ -459,7 +459,7 @@
 %always given relatively low alpha messages, then the mixes that can
 %tell a message is more sensitive will not be the ones knowing the
 %ultimate source or destination. For example, given a message with a
-%cumulative $A = \sum \alpha_0$, a path with alpha distribution given by
+%cumulative $A = \sum \alpha$, a path with alpha distribution given by
 %$0$, $1$, $\lceil A/2 -2 \rceil$, $\lceil A/2 -2 \rceil$, $1$, $0$
 %should both hide the sensitivity of the endpoints and diffuse the
 %trust so that an adversary comprising a single bad mix and a global
@@ -480,7 +480,7 @@
 no guarantee that the message that exited the mix is the same message
 that entered. The attack is never exact (guaranteed to recognize a
 target message as it exits the mix) unless the adversary can bound the
-range of $\alpha_0$ with certainty for all messages he observes.
+range of $\alpha$ with certainty for all messages he observes.
 
 We provide a very lightweight dummy policy that guarantees that no exact
 attack is
@@ -491,8 +491,8 @@
 
 But what do we mean by ``arbitrary alpha''? Obviously it must occur within
 some finite range. It could be uniformly chosen between $0$ and the
-maximum expected $\alpha_0$. If a message is ever received with a
-higher $\alpha_0$, then the maximum should be raised to this level.
+maximum expected $\alpha$. If a message is ever received with a
+higher $\alpha$, then the maximum should be raised to this level.
 Such a strategy will prevent any exact attack, but it will still allow
 most practical attacks that dummies are intended to counter (active or
 passive) because most traffic will not have high alpha. Thus, a single
@@ -502,13 +502,13 @@
 
 A strategy that should maximize uncertainty at least in the edge cases
 would be to insert dummies according to the expected distribution of
-$\alpha_{M,0}$ for messages $M$ entering the mix. The expected
+$\alpha_{M}$ for messages $M$ entering the mix. The expected
 distribution can be determined by observation. Mixes joining the
 network can be initialized with a default expected distribution
 averaged from one or more mixes already in the network. If the network
 is uninitialized, individual mixes can be initialized with a uniform
 strategy (as above), or better a geometric one, e.g., add a dummy at
-level $\alpha$ with probability $1/2^{\alpha+1}$. Dummy policy can
+level $\alpha$ with probability $2^{-(\alpha+1)}$. Dummy policy can
 then be periodically shifted to reflect the distribution of alphas for
 actual traffic through the mix.
 More research remains here to make this dummy approach resistant to an
@@ -537,7 +537,7 @@
 As observed in Section~\ref{sec:passive-adversary-anonymity}, the
 anonymity of any message can be improved by greater uncertainty about
 the alpha level of \emph{other} messages.  Since Alice benefits from
-the fact that other people might choose non-zero $\alpha_0$ for their
+the fact that other people might choose non-zero $\alpha$ for their
 messages, she has an incentive to take advantage of this by choosing a
 lower $\alpha$ to get better performance but still have good security.
 This can be viewed as a commons: everybody will hope that somebody
@@ -581,7 +581,7 @@
 Initial recommendations can be guided by existing anonymity networks.
 Traffic that must arrive in realtime obviously must have $\sum \alpha =
 0$.  For more sensitive traffic, we might initially try to follow
-networks such as Mixminion and Mixmaster. But how can we do that? 
+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,
 while alpha mixing is based on individual choices made by the sender.
@@ -591,37 +591,45 @@
 \section{Beta Alpha: Variations on Alpha Mixing}
 \label{sec:beta-alpha}
 
+In the previous sections, we have investigated and analysed some basic
+alpha mixing designs and the incentive questions and attacks that arise
+from them. In this section we introduce and briefly discuss some more
+complex designs that are harder to analyse fully but may provide better
+protection against stronger attacks.
+
 \subsection{Preventing end-to-end timing on alpha mixnets}
 
 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
 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
-described above. One important difference is that delivery through the
-mixnet depends on it being entirely synchronized. Alpha mixes offer
+it is discarded. This approach is similar to the timed deterministic-alpha mix
+described above, but an important difference is that a stop-and-go
+mixnet must be entirely synchronized to prevent losing messages.
+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,
+On the other hand, this flexibility is also a flaw: an adversary that
+is global-passive except for being able to delay messages from a single
+sender could, e.g., batch up a victim's messages and
+send them through an alpha mixnet all at once. Unless all the messages have
+$\sum \alpha = 0$ the adversary will gain limited information from this attack,
 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
+We could include timestamps along with the $\alpha$ 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
+sensitive so each has $\sum \alpha^{(i)}$ 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
+\alpha^{(i)}$ 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
@@ -636,7 +644,8 @@
 In the basic threshold deterministic-alpha mix, if there are
 $\mbox{\emph{threshold}} = n$ messages in each of alpha levels $0$ through
 $\ell$, all of the messages in levels $0$ through $\ell$ will be sent at
-once; however, they will not be mixed. The mix will send all messages
+once; however, the different levels will not be mixed together.
+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
@@ -652,15 +661,16 @@
 the messages.
 
 The simplest solution is to simply mix all messages that emerge at
-once. This will prevent an adversary from observing when the messages
-exit during a flush and thus learning about their sensitivity.
-This together with the minimal dummy scheme presented in
-Section~\ref{sec:dummies} would substantially reduce the effect of
-blending: an adversary emptying the mix of all messages up to the
+once. This will prevent an adversary from watching the order in which
+messages exit during a flush and thus learning about their sensitivity.
+The stronger attack we worry about is the blending attack:
+an adversary emptying the mix of all messages up to the
 highest reasonably expected level, trickling in a message, then
-flooding with $\alpha_0 = 0$ messages repeatedly to learn the
+flooding with $\alpha = 0$ messages repeatedly to learn the
 sensitivity of that message and its next destination.
-%XXX not a sentence
+Batching all outgoing messages together, combined with the minimal dummy
+scheme presented in Section~\ref{sec:dummies}, would substantially reduce
+the risk from blending.
 
 We could also require that the firing of the mix be
 threshold-and-timed, which would prevent the adversary from triggering
@@ -687,18 +697,18 @@
 of deterministically decreasing by one after each mix firing, there is
 a probabilistic function $f$ that dictates how they decrement:\\
 $\alpha_{M,i+1} = f(\alpha_{M,i}, \mathit{Pool}(\alpha_{M,i}))$
-
+where
 $\mathit{Pool}(\alpha_{M,i}) = | \{M' : 1 \leq \alpha_{M',i-1} \leq
 \alpha_{M',i-1} \} | $
 
 We believe that $f$ would typically be monotonically nonincreasing.
-The sender gives $f_M$ to a mix along with $\alpha_{M,0}$. We would
+The sender gives $f_M$ to a mix along with $\alpha_{M}$. We would
 expect that there be some small number of easy-to-compute $f$s that
 can be chosen. The
 idea is that alphas decrease but only as a function of the
 current alpha level of the message and how many messages
 are in the pool below it. We have also limited the input of
-$f$ to messages that were given an $\alpha_0 > 0$, although this
+$f$ to messages that were given an $\alpha > 0$, although this
 is not necessary. This effectively puts each message in a dynamic
 pool, which could also be timed.
 
@@ -718,20 +728,20 @@
 get in the way. 
 
 This is the idea behind tau mixing: a message $M$ arrives at a mix
-with an associated threshold $\tau_{M,0}$ of how many other messages
+with an associated threshold $\tau_{M}$ of how many other messages
 must be sent by the mix between the arrival and sending of $M$.
 Multiple messages that have the same tau can be sent together after
-mixing, e.g., three messages that arrive with $\tau_0 = 2$ are sent
+mixing, e.g., three messages that arrive with $\tau = 2$ are sent
 together. Messages that are to be sent as quickly as possible are
-assigned $\tau_{M,0} = 0$.  This can provide realtime properties
+assigned $\tau_{M} = 0$.  This can provide realtime properties
 limited only by the processing speed of the network components. For
-example, if a message with $\tau_0 = 0$ arrives at a mix containing
+example, if a message with $\tau = 0$ arrives at a mix containing
 messages with current $\tau = 1$, $\tau = 2$, and $\tau = 3$, the
 latter three should be mixed and sent together after sending the
-former. (We assume messages with $\tau_0 = 0$ should always be sent as
+former. (We assume messages with initial $\tau = 0$ should always be sent as
 quickly as they arrive without the delay associated with mixing.)
 Messages that are more sensitive should be assigned a $\sum
-\tau^{(i)}_{M,0}$ from a private distribution on a range that
+\tau^{(i)}_{M}$ from a private distribution on a range that
 increases with sensitivity. Many of the same features of alpha mixing
 apply, e.g., the dummy strategy, how to distribute $\sum \tau$ across
 the mixes in the path, etc. If taus are purely threshold values, then
@@ -1078,7 +1088,7 @@
 %As observed in section~\ref{passive-adversary-anonymity}, the
 %anonymity of any message can be improved by greater uncertainty about
 %the alpha level of \emph{other} messages.  Since Alice benefits from
-%the fact that other people might choose non-zero $\alpha_0$ for their
+%the fact that other people might choose non-zero $\alpha$ for their
 %messages, she has an incentive to take advantage of this by choosing a
 %lower $\alpha$ to get better performance but still have good security.
 %This can be viewed as a commons: everybody will hope that somebody else

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