\documentclass{llncs}

\usepackage{url}
\usepackage{amsmath}
\usepackage{epsfig}

\renewcommand\url{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
\newcommand\emailaddr{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
\newcommand\XXXX[1]{{\small\bf [XXXX #1]}}
\newcommand{\workingnote}[1]{}        % The version that hides the note.
%\newcommand{\workingnote}[1]{(**#1)}   % The version that makes the note visible.

\hyphenation{mix-net mix-nets}


\newenvironment{tightlist}{\begin{list}{$\bullet$}{
  \setlength{\itemsep}{0mm}
    \setlength{\parsep}{0mm}
    %  \setlength{\labelsep}{0mm}
    %  \setlength{\labelwidth}{0mm}
    %  \setlength{\topsep}{0mm}
}}{\end{list}}


% Cut down on whitespace above and below figures displayed at head/foot of
% page.
%\setlength{\textfloatsep}{3mm}
% Cut down on whitespace above and below figures displayed in middle of page
%\setlength{\intextsep}{3mm}

\begin{document}

\title{Blending different latency traffic\\with alpha-mixing}
%\normalsize{(Pre-proceedings Draft)}}
%\title{Alpha-mixing or Getting Personal with the Adversary}

\author{Roger Dingledine\inst{1} \and Andrei Serjantov\inst{2} \and Paul Syverson\inst{3}}
%\author{Anonymous}

\institute{The Free Haven Project \email{(arma@freehaven.net)} \and
The Free Haven Project \email{(aas23@freehaven.net)} \and
Naval Research Laboratory \email{(syverson@itd.nrl.navy.mil)}}
%\institute{Potential PET author}

\maketitle
\pagestyle{empty}

%======================================================================

\begin{abstract}

Currently fielded anonymous communication systems either introduce too
much delay and thus have few users and little security, or have many
users but too little delay to provide protection against large
attackers. By combining the user bases into the same network, and
ensuring that all traffic is mixed together, we hope to lower delay and
improve anonymity for both sets of users.

Alpha-mixing is an approach that can be added to traditional
batching strategies to let senders specify for each message whether
they prefer security or speed. Here we describe how to add
alpha-mixing to various mix designs, and show that mix networks
with this feature can provide increased anonymity for all senders in
the network. Along the way we encounter subtle issues to do with the
attacker's knowledge of the security parameters of the users.

\end{abstract}

\section{Introduction}
\label{sec:intro}

Anonymous communication systems today don't provide
much protection against a large attacker. Tor~\cite{tor-design} and
JAP~\cite{web-mix} have hundreds of thousands of concurrent users,
but their low latency and low overhead mean they do not defend against
an adversary who observes most of the network.  At the other end of the
spectrum, Mixminion's design~\cite{minion-design} theoretically provides
strong security against a global attacker by adding high variance
in latency, but this latency has crippled adoption --- which in turn
decreases the security that the network can provide, discouraging even
the users who need high security~\cite{econymics,weis06-usability}.

Here we design a hybrid mix batching strategy that combines users with
different anonymity and performance goals into the same network.

In our scheme each sender communicates an $\alpha$ -- a security
parameter -- to each mix along the route of her message. The time the
message spends inside each mix (and hence the anonymity it
accumulates) then depends on the size of this security parameter. The
message's $\alpha$ value at each mix decrements based on certain
events, and when it reaches zero it is reintegrated back into the mix
network.  Our scheme can be combined with any of the standard mix
types such as timed mixes, pool mixes, etc.~\cite{trickle02} to give
each sender more control over the anonymity/performance tradeoff of
her message.
% (Depending on the type of mix used, it can also depend on
%other variables such as the traffic level in the network, the number of
%messages inside the mix, or a random number chosen by the mix.)

%Alice gives each message an alpha (number of rounds) delay to each mix
%in a route. Once a threshold number of messages with alpha 0 enter the
%mix all messages that are alpha 0 get fired off, including any that
%were buffered and decremented to 0 last time decrementing occurred.
%Then all messages in the buffers get alpha decremented by 1. Any
%messages that enter with alpha $>0$ get put into the buffer with alpha
%of that number.

Users that desire better anonymity then have the opportunity to obtain
it by increasing $\alpha$ for their messages. More importantly, there
is a network effect: when the attacker knows little about the security
parameters chosen by individual users, all senders will benefit
% (even those that don't choose a high $\alpha$)
because of the mere \emph{possibility} that they chose a higher
$\alpha$.

%Here we also need to say that the attacker does not have complete
%knowledge of the alphas in the messages, and this is what we are
%relying on, see the analysis section.

In this paper we start by outlining some simple alpha-mix designs
and analysing the anonymity properties they can provide to users with
different security preferences. Next we look at the strategies users
should follow when picking the security parameter for each mix in the
message's path.  In Section~\ref{sec:strategic-choice}, we look at the
incentives users have for
choosing a high security parameter themselves rather than expecting
others to take the latency penalty (and thus provide more anonymity to
everyone). Lastly we consider more sophisticated alpha-mixing
strategies which should provide better properties but are hard to
analyse.

%AAS: this should all hopefully be in the paragraph above.
%\subsection{Outline}
%
%1. Deterministic-alpha mixes\\
%   Prove anonymity against a local passive adversary\\
%
%2. Strategy: (or a subsec of above section)\\
%   How to distributed the $\sum \alpha$ across the path \\
%   Add dummy traffic \\
%   
%3. Game Theory and Free-riding
%
%4. Dynamic-alpha mixing

\section{Deterministic-alpha mix}
\label{sec:deterministic-alpha-mix}

While \emph{threshold mixes} fire only when a sufficient number
of messages have arrived, \emph{timed mixes} simply fire at regular
intervals. Timed mixes may be appropriate for traffic for which timeliness
matters, since with threshold mixes the time until the next firing is
unpredictable without assumptions about the rate of incoming messages. On
the other hand, threshold mixes can provide minimum anonymity properties.

``Deterministic'' here refers to the algorithm by which messages
change $\alpha$ after each mix firing. Later we will consider
algorithms that will change alpha probabilistically, for example based on
the number of messages with certain alpha values in the mix. In this
section, all messages simply drop one alpha level after each mix firing.

\paragraph{Timed deterministic-alpha mix:}
The mix fires every $t$ seconds. All messages for which $\alpha = 0$
are sent out.\footnote{We do not describe the reordering of messages or
changing of their appearance in this paper. We assume that messages
emerging from a mix have an appearance that cannot be correlated with
their appearance upon entering the mix and that the order of all
$\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$ and are placed at the according $\alpha$ level.

\paragraph{Threshold deterministic-alpha mix:}
This is the same as the timed version, except that the
mix fires when at least a threshold $n$ of messages with $\alpha =
0$ are in the mix. Note that since the number of messages with $\alpha
= 1$ may be above the firing threshold, some batches may include
more than $n$ messages.
(When many messages with $\alpha > 0$ are waiting
in a mix before a threshold number of $\alpha = 0$ accumulate, this is
analogous to the situation where many mixes in a free-route threshold-mix
net are waiting and nearly full while messages are being accumulated
at relatively empty mixes.)

As we will see, one of the virtues of alpha mixing is that
the timed/threshold distinction for mixes can blur, and it
becomes more a distinction for firing strategies of individual
messages than of mixes. For our initial analysis we will assume
a steady-state network with constant rate of incoming messages, which
means against a passive adversary the anonymity properties are equivalent.

It is also possible to have a threshold-or-timed alpha mix in which
all messages are decremented in the alpha stack if either $t$ seconds
have passed or $n$ messages have arrived.
Similarly, one can have a threshold-and-timed alpha mix
to reduce the effective rate of flooding attacks~\cite{trickle02}.
Even more complex variants of these designs are discussed in
Section~\ref{sec:beta-alpha}.

\subsection{Deterministic-alpha mix:\\
anonymity against a local passive adversary}
\label{sec:passive-adversary-anonymity}

Here we describe the anonymity for a threshold alpha mix during
steady-state (i.e., messages arrive with various alphas at a regular rate, and
the mix fires at regular intervals).
% In this case the threshold mix is
% indistinguishable by a local observer from a timed mix.
%% XXX Actually, we need another assumption if we want steady-state to
%% still mean that we fire at regular intervals. It seems this assumption
%% is that the alphas we receive are uniformly distributed? -RD

%% XXX Is it the case that assuming some fixed distribution of incoming
%% alphas, timed and threshold alpha mixes are still indistinguishable? -RD

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
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
would correspond to greater anonymity for messages. We now make this
more precise.

\begin{claim}
  Given any set of other messages in a threshold deterministic-alpha
  mix, a message has greater anonymity if it is assigned an alpha from
  a broader range (chosen uniformly) than from a narrower range.
\end{claim}

\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}$ 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}$ 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
  know the strategy, then we cannot put a precise number on his
  uncertainty.  However, the less predictable the range is to the
  adversary, the greater the uncertainty is, even if we cannot say how
  much. She can either guess too small a range and risk not seeing the
  output message at all, or guess too large and include many additional
  batches in the anonymity set for the message. (These points carry
  over mutatis mutandis when we reason probabilistically rather than
  just possibilistically.)
\end{proof}

If the adversary does know the strategy (although still not the actual
$\alpha$) for each incoming message, then the anonymity of $M$ is
less affected by the strategy that other messages use for choosing $\alpha$
in a steady-state network.
%% used to be "is unaffected"
%% XXX I'm not sure I buy this. Compare the situation when other users
%% use high-variance strategies or low-variance strategies. Doesn't Alice
%% get different anonymity in these cases, even if the adversary does know
%% the strategy of alpha distribution for each incoming message? -RD
However, if the strategies are not known,
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$ 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}$ for any message $M$ is chosen uniformly
  at random from the range
  given by $0 \leq \alpha_{M} \leq k_{M}$.
  Then anonymity increases for every message $M$ in the mix if any
  $k_{M'}$ increases.
\end{claim}

The key is not that a high $\alpha$ necessarily provides better security,
but rather that when the variance of our $\alpha$ is high, its value
within the range is hard for the attacker to predict.

In summary, for threshold mixes or steady-state timed mixes, choosing
$\alpha$ from a broader range improves the anonymity for that message
whether the adversary knows one's strategy or not.
Further, if the
adversary knows nothing about the strategies of choosing alphas or
knows simply the distribution of strategies, then increasing the
$\alpha$-range for any message improves anonymity for all messages.

\subsection{Attacker knowledge}
\label{sec:attacker-knowledge}

In the previous section we noted that the anonymity properties
provided by alpha mixes depend on what the attacker knows about the
security parameters of the users. Specifically, while choosing from a wider
range of alphas improves anonymity, an attacker can reduce anonymity
if he has information about which alphas are chosen. We illustrate this
on a simple example.

Consider sender anonymity in the setting of just one mix, illustrated
on two rounds only (equivalently, suppose maximum alpha is 1):

Round 1: $I_1 = i_{1,1} \ldots i_{m,1}$ entered the mix, messages
$o_{1,1} \ldots o_{x,1}$ came out.

Round 2: $I_2 = i_{1,2} \ldots i_{n,2}$ entered, messages $o_{1,2}
\ldots o_{y,2}$ came out.

Let $\alpha(x)$ be 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\}$.

Our target message is $o_{1,2}$. The sender anonymity set (in
messages) is:

\[
\{x | x \in I_1 \wedge 1 \in \alpha(x)\} \cup \{y | y \in I_2 \wedge 0
\in \alpha(y)\}
\]

Hence (almost) any knowledge of alphas by the attacker degrades
anonymity. Note that complete knowledge of alphas by the attacker
\emph{may} leave the message with no anonymity; however, this is
extremely unlikely (or amounts to a rather expensive variant of the
trickle attack).

Indeed, when analysing alpha mixes we need not constrain ourselves to
reasoning about anonymity sets. We now compute the anonymity
probability distribution, but first we need a little more
formalization of the assumptions. Essentially, where we allowed the
attacker possibilistic knowledge about the alphas of the messages, we
now allow him (better) probabilistic knowledge.

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 | 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
more the attacker knows about alpha, the lower the anonymity.

\subsection{Correlating message content with requested security}

Now let us study an interesting example which has long been known
intuitively... Suppose the attacker knows that sender $S$ only sends
with a high security parameter (let's say alpha of 5). He now sees a
message from sender $S$ at round 0, and a message detailing Enron's
finances emerges
at round 5. Suppose further that all other messages have an alpha of
0. Our above definitions give the target message the
anonymity set of all the senders of round 5 union $S$. Nevertheless, we
conjecture the attacker will tend to suspect that $S$ sent the
message. How can we reconcile the intuition of the attacker with our
formalism above and how can we design the system to avoid such a
judgement?

The attacker is likely to be correct --- what we ignore here is the
fact that the choice of the security parameter is likely
\emph{conditional} on the importance of the message and the attacker
has used this fact to form his judgement. In order to avoid this, we
must (paradoxically!) ignore this fact completely and pick alphas from
a distribution which is independent of the receiver and the message's
content. Of course, we cannot defeat this attack entirely because the
sender's distribution will still be conditional on her utility
function: messages from users with higher security needs will in fact
still behave differently.

There are still external factors to consider. We'd like to
go a step further and make the sender's software enforce that she doesn't
vary alpha based on each message's receiver or content. This approach
would best convince the attacker that the sender \emph{could not} have
changed it.
Also, if a given user is the only sender with extremely
high alpha values, then intersection attacks over time (watching the
high-value messages and what senders were active before each) will
reveal her~\cite{statistical-disclosure,e2e-traffic}.
But we will ignore these black-box network attacks since
they are not the focus of this paper.

Below we will see that some strategies for choosing the alpha values are
more effective than others at preventing the attacker from learning the
security preferences of senders.

\section{Allocating $\sum \alpha$ against a distributed adversary}
\label{sec:distributing-alpha}

In the previous section we discussed the fact that an adversary who
can learn about the sender's alphas can weaken her anonymity. For
example, sending only high
value messages and picking high security parameters for them can actually
decrease anonymity.

In this section we examine an attack that a compromised mix can perform
to deduce the sender's alphas, and we deal with the problem of allocating
the overall message's security parameter $\Sigma \alpha$
over the mixes in the message's path.
There are two problems to solve. Firstly, if a bad mix
observes one of the alphas, it should get as little information as
possible about the other alphas of this message.\footnote{Note the
similarity between picking an alpha and message splitting~\cite{SM05}
--- in both cases they are distributions over partitions.}
Secondly, it should be hard for the bad mixes to link any alpha
parameter to a particular sender, i.e. figure out how much any sender
is concerned about security.

One possible solution for picking a sequence of $\alpha^{(i)}$ (where
the ``$(i)$'' represents the $i^{th}$ mix in the route) is simply to
pick from a uniform distribution over the partitions of $\Sigma
\alpha$ into $\ell$ buckets where the buckets themselves are
indistinguishable. The number of such partitions are given by

\[
\sum_{k=1}^\ell Q(\Sigma \alpha, k)
\]

where $Q$ denotes the number of ways of partitioning $\Sigma \alpha$ into
exactly $k$ distinct parts. Generating values from such a distribution
is possible, for instance, using the algorithm described in~\cite{devroye86}.
This seems to deal with the first problem (the
analysis to show this is beyond the scope of this paper). For the
second part, it depends what the sender wants to protect:
does she care about having an estimate of the security parameter
associated with just herself, with herself and the recipient,
or just the recipient? Note that if the first and
the last mixes are bad and can observe a ``higher security'' message
passing through each of them, they can conjecture that it is one
of a relatively small set of sensitive messages.
There are a variety of properties to explore in this
area; we merely observe that by reordering the value that we
obtain from the uniform distribution over partitions, we can make
sure that the minimum values in that partition are sent to the first
and the last mix. For example, if $\Sigma \alpha = 5$, then the
distribution is uniform over:
$\{5,0,0,0\},\{4,1,0,0\},\{3,2,0,0\},\{3,1,1,0\},\{2,1,1,1\}$. Supposing
we draw the partition $\{3,1,1,0\}$, we reorder it into $\{0,3,1,1\}$
and hence obtain a sequence of alphas to insert into the message.

If we wish to guarantee that neither the first nor the last mix can
locally know anything about the sensitivity level of a message, we can
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 a more concentrated set of nodes in the
center learn more
about the sensitivity of messages. Against an adversary who controls
the central
node(s) combined with, e.g., a global passive observer, our protection
is diminished. We can gain advantage against both types of adversaries
by increasing path length, with the usual concomitant risk to
robustness of delivery that comes with increased path length.

%While a rising alpha seems to lift all boats, and one's own against
%even knowledgeable adversaries, it is not unequivocally better to
%simply choose from a higher range of alphas. First, this has a cost in
%message delivery. Since to some extent one's anonymity is improved by
%messages from others chosen with higher alpha, there is some incentive
%to allow others to improve your anonymity for you. We will return to
%this issue below. Second, both theory~\cite{econymics} and experience
%have indicated that lower latency systems like Tor, JAP, and Freedom
%have far more users than higher latency systems like Mixmaster and
%Mixminion. Thus, higher alpha messages will be more rare and will
%stand out more as messages the sender was trying harder to protect.
%This has both the negative effect of being better mixed but in a much
%smaller anonymity set and the negative effect of advertising to
%participating mixes that the message is more sensitive.

%This tradeoff is not entirely avoidable, but it is possible to
%move where the higher alphas occur within a messages path. If the mix
%adjacent to the sender (and receiver if that is also sensitive) is
%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$, 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
%passive observer will still have some difficulty linking endpoints or
%even identifying them as associated with any sensitive message.
 
\section{Dummies}
\label{sec:dummies}

Our focus so far has been on steady-state networks with
passive adversaries. However, we want to provide uncertainty
even in edge cases where there is a momentarily lull in
traffic~\cite{mixmaster-reliable,pet2003-diaz,trickle02}.  An active attacker
can arrange an edge case via blending attacks, but a passive attacker
can also simply wait for an edge case to occur.  For timed mixes there
will be occasions when only a single message enters and leaves the mix in
a given round. Alpha mixes have a clear advantage here since there is
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$ with certainty for all messages he observes.

We provide a very lightweight dummy policy that guarantees that no exact
attack is
possible against an alpha mix, even for active attackers: simply
initialize the mix with a single dummy message set at an arbitrary
alpha. Before firing, always check the mix for the presence of a dummy
somewhere in the alpha-stack. If none is present, add one.

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$. 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
message entering and a single message exiting a timed mix in a single
firing interval are much more likely to be the same message than a
dummy.

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}$ 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 $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
adversary who sends lots of messages with non-standard alphas into a
particular mix to influence its view of a typical value for alpha.

If active attacks are suspected, the amount of dummy traffic added to
the alpha stack can be increased according to the expected duration of
and strength of the blocking (assuming timed deterministic-alpha mixes,
for which there is no point in flooding) and the anonymity one intends to
maintain for messages so attacked.

The easiest way to disguise dummies from others in the network is to
route them in a circuit leading back to the mix that generates
them~\cite{danezis:wpes2003}.
The length of the path should be randomly chosen as suggested
in~\cite{trickle02}. Obviously the alphas chosen for the dummy
message at other mixes in the path should be distributed to minimize
recognition of the message as a dummy; hence some dummies should
follow an alpha pattern as if they had entered the network at that mix
and others should appear to be in mid path as they emerge from the mix
(cf.\ Section~\ref{sec:distributing-alpha}).

\section{Strategic Choice of Alpha}
\label{sec:strategic-choice}

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$ 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 takes the latency hit.

There are two ways to resolve this risk.
First, note that not all users have the same sensitivity level: some
users favor performance and others favor anonymity. Three factors are
most important in characterizing the utility function for our users:
their need for anonymity, their willingness to accept delay, and
their guess at (expectation of) the current alpha levels in the network.
In~\cite{econymics} it was shown that there can be optimal levels of
free riding: more-sensitive users have incentive to provide ``free''
communications service for less-sensitive users by running network
nodes because this will still provide additional value in the form of
better anonymity protection for the more-sensitive users. This can
provide adequate incentive even if there are many others running
nodes.  Similarly, while the existence of higher $\alpha$ traffic may
reduce Alice's incentive to set higher $\alpha$ levels for her own traffic,
it does not eliminate that incentive.

Second, when Alice chooses her alphas' range based on her sensitivity
and timeliness constraints for her own messages, she gets increased
autonomy and control over her own security and utility.
%against \emph{some}
%attackers it is still beneficial to have higher alphas: if an attacker
%watching Alice's traffic guesses that she chose $\alpha = 0$ in hopes that
%other people would improve her anonymity for her, then he can ignore the
%higher-alpha traffic. That is, to get the maximum benefit of blending with
%lots of different traffic, Alice actually does need to choose her alphas
%from a wide range at least sometimes.
Indeed, if an adversary can make reasonable guesses about a choice of
alpha range for a message, then much higher or much lower alphas for
other messages in a mix might actually decrease the anonymity set for
a target message. For example, consider a mix containing a
target message with low alpha and an ancillary message that is either from
about the same alpha range or from a much larger alpha range than the
target message.  If the adversary learns that the second message has a
larger range, then his uncertainty about the target message decreases.

Even more significantly, however, security is hard to get right when it
doesn't depend on the strategic behavior of others. Users of the
system are not likely to have such fine-tuned knowledge of the system,
the behavior of others, and their own needs. Thus if we can prescribe
recommendations for choice of alpha, for example based on analysis and
observed patterns within the network, we can expect most people to
heed them. (On the other hand, they may not --- we can also expect
hyperbolic discounting of risk, disregard of risk for expedience,
etc.~\cite{acquisti04}.)

Alpha mixing itself is likely to affect the applications that can be
securely used and how, so recommendations are likely to evolve.
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?
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.
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}

In the previous sections, we 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 attacks 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 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, this flexibility is also a flaw: an adversary that
is global-passive except for being able to delay messages from a single
sender could 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 he can still learn more than from a stop-and-go mixnet.

We could include timestamps along with the $\alpha$ that each mix
receives, 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)}$ 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)}$ 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 (unless
they're dropped by the attacker).
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}} = 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, messages from 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
than $n$ messages in a given level, but if more than $n$ messages
emerge he can know that the last messages to emerge were considered
more sensitive by their 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. Then,
by flooding first $\alpha = \ell$, then $\alpha = \ell-1$, \ldots, then
$\alpha = 0$, the adversary can guarantee a flush of the mix all the
way up to $\alpha = \ell$ while also learning the alpha level of most of
the messages.

The simplest solution is simply to mix all messages that emerge at
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$ messages repeatedly to learn the
sensitivity of that message and its next destination.
Batching all outgoing messages together, combined with the dummy
schemes presented in Section~\ref{sec:dummies}, would substantially reduce
the risk from blending.

%An alternate threshold alpha mixing scheme would only fire when
%$n$ messages of $\alpha = 0$ have arrived. That is, 

We could also use a
threshold-and-timed mix, which would prevent the adversary from triggering
an alpha-stack dump because only messages of one alpha level will
emerge in each time interval. It is unclear what the local advantage is
of this vs.\ the above multilevel-batching threshold mix. In addition,
having threshold-and-timed batching would preclude the predictability
advantages of timed mixes while the multilevel-batching approach could
potentially offer faster performance. The primary risk of not having
timing limitations on mix firing is the end-to-end effects that the
adversary could induce by flooding, which would not be countered by
our dummy scheme. However, that assumes a powerful adversary that can
flood and watch the entire network.  The nice thing about alpha mixing
is that we can still have both good realtime properties and threshold
protections together.

There are various ways to have realtime and threshold properties together
in one mix design. We note two of them next.

\subsection{Dynamic-alpha mixing}

In this design, alphas are assigned to messages as they have been
all along, except instead
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}$. 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 arrived with a non-zero alpha, although this
is not necessary. This effectively puts each message in a dynamic
pool, which could also be timed.

\subsection{Tau mixing}

We have been describing alpha all along as a level which determines a
batch of messages that a given message will be sent with, after (or
possibly also together with) the messages in the alpha levels that are
below it in the stack. This lends itself naturally to the batching
concept familiar in the mix literature. Intuitively, threshold batching
implies unpredictable delays since we don't know how long it will
take for a threshold number of messages to accumulate at $\alpha = 0$.
Timed mixing on the other hand will allow a predictable delay by providing
an upper bound on latency.
But because timed mixing also provides a \emph{lower} bound on latency,
threshold batching can be faster because it can allow messages to be
processed as quickly as they arrive, provided the batch size does not
get in the way.

This is the idea behind tau mixing: a message $M$ arrives at a mix
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 = 2$ are sent
together. Messages that are to be sent as quickly as possible are
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$ 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 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}$ from a private distribution on a range that
increases with sensitivity. Many of the same features of alpha mixing
apply, including the dummy strategy discussion, the techniques for
allocating $\sum \tau$ across
the mixes in the path, and so on.

If taus are purely threshold values, then an adversary that is powerful
enough to perform a sustained flush of the entire network will be able
to conduct end-to-end timing correlations on more sensitive messages
(assuming we stick to a purely internally routed dummy scheme). To
address this attack, both a threshold and a
random minimum delay at each mix can be given as security parameter.
This will prevent effective flushing unless the adversary can also
perform sustained blocking of all inputs to the mixnet, and even then
the attack will be substantially slowed.

\section{Conclusion}

In this paper we have presented a mixing technique that works together
with traditional batching strategies to allow senders with varying
anonymity and performance goals to share the same network and have
their traffic mixed. Aside from simply letting high-sensitivity users
choose to get higher anonymity for their messages, the key property it
provides is a network effect: when \emph{some} users ask for higher
anonymity, \emph{all} users can benefit.

While we proved anonymity properties for the simplest versions of
alpha mixing,
we have only begun to explore the possibilities and analysis of this
design. Future work includes:

\paragraph{Multiple messages and stream-based communication:} This paper
has assumed the \emph{single-message model}, where each sender produces
individual uncorrelated messages. We did describe countermeasures to
end-to-end timing correlations in Section~\ref{sec:beta-alpha}; however,
we have not carefully examined the implications of stream-based communication.
Much of the reason for the success of Tor and JAP
is not just the low overhead, but rather their support for bidirectional
streams. But the \emph{stream model} introduces many end-to-end anonymity
attacks that seem hard to resolve simply with better batching strategies.

\paragraph{A full analysis of the alpha mix design:} In this paper we
have added to mixes an additional user-defined security parameter and explored
some scenarios of attacker's knowledge about it. However, the more
complex dynamic-alpha mixes and tau mixes are yet to be analysed; this seems
difficult as we need to make some assumptions both about how users
choose their security parameters and what the attacker knows about them.

\paragraph{User behavior:} However much we postulate about how users
behave, there is no substitute for actually getting user profiles
and learning how to create incentives for secure behavior. We expect that
unless we protect our users, they will try to condition their security
parameter on the threat level of the message; as we have seen above
this reduces rather than increases anonymity.

%%%% Stuff with 4s is stuff from alpha strategy section
%%%% that I didn't want to toss just yet

%4 C.f. Andrei's complaints about stop-and-go -- in that design you had
%4 to anticipate the network load to get good anonymity, and in this
%4 design you need to anticipate the other users' anonymity/latency
%4 requirements to get what you want.
%4 
%4 Speaking of which, how does the network bootstrap? See the econymics
%4 paper where we argue that people who don't care about anonymity will
%4 be the early adopters, since the people who do care won't be willing
%4 to use it with no cover users. Similarly the first users will all
%4 choose $\alpha$ of 0, and then sometime later the users willing to try
%4 a non-zero $\alpha$ will arrive?
%4 
%4 The attacker's a priori expectation of Alice's paranoia improves his
%4 attack.
%4 

%\section{Assumptions}
%
%Assume that in most cases we are analyzing a steady-state network.
%(Our benefits are most easily seen in this light.) In section
%\ref{sec-defense-against-blending-attacks} we discuss relaxing this
%assumption and our how well we resist blending attacks.
%
%Assume the single-message model. There are two pieces to this
%assumption.  First, we want to know about the level of protection we
%can provide to one message from Alice to Bob. We acknowledge that in
%reality there are probably long-term trends that make us vulnerable to
%statistical disclosure attacks, regardless of how good our batching
%strategy is. So we're not paying attention to that here. Second, we
%assume a message-based protocol rather than stream-based. This has bad
%implications on our user base, but hey, low-latency stream-based
%anonymity is hard, so one step at a time.
%
%Also state some assumptions about practical attackers and all the
%things they can do. We can't solve all of them but we are at least a
%step forward.
%
%Assume users with differing goals. See section
%\ref{sec-economic-model} for more discussion.
%
%AAS: Perhaps this goes into the analysis section and we want to just
%give a flavour?

%The key difference of this model to the more traditional anonymity
%schemes (which is actually an additional but, we argue, realistic
%assumption) is that the users have an additional security parameter
%which is \emph{not known} to the attacker. As expected, we expect the
%attacker to have some knowledge of the overall distribution of the
%security parameter (can try to figure out the users' utility function,
%etc, etc), but no more than that for any particular attack he is
%trying to mount. If he does, the additional properties of the
%``alpha'' mixing collapse and we get back to a timed/threshold mix
%scenario, which, note, is worse than the pool/dynamic pool/generalised
%mix, so we are relying on the fact that the attacker does not know
%alpha. On the other hand, in practice even relatively few dummy
%messages fix this problem. We will illustrate this better in the
%analysis section.
%
%PFS: It doesn't have to collapse to something weaker than pool. there
%is no reason that we couldn't have alpha pools that one stipulates.
%
%Here's a design. Assign alphas as we have been thinking, except instead
%of them deterministically decreasing one after each firing, there is
%a probabilistic function.\\
%$x_{\alpha,i+1} = f(x_{\alpha,i}, \mathit{Pool}(x_{\alpha,i}))$ where
%$\mathit{Pool}(x_{\alpha,i}) = | \{x : 1 \leq x_{\alpha ',i-1} \leq
%x_{\alpha,i-1} \} | $
%
%My assumption is that f is monotonically nonincreasing, but maybe not.
%This should get us something like generalized mixes only a bit more
%general because, like the alphas, the $f$ is not set by the mix but by
%the individuals. (This is maybe where you were trying to go when
%observing that you couldn't add timestamps in the generalized mix
%paper?) Idea is that alphas decrease but only as a function of where
%they are and how many messages are in the pool below them (and were
%above 0 at some point, since I figured those messages shouldn't
%count). This gives
%us a dynamic alpha pool (either timed or threshold depending).\\
%By the way, I'm following the subsequent notation of $x_\alpha$ but I
%think it is exactly backwards. It should be $\alpha_x$.
%
%Note that the most important thing is that we can have timed $\alpha = 0$
%messages, higher alpha messages, and dynamic pool messages all living
%in the same mix.

%\section{Analysis}
%
%In this section we look at the two mixes in more detail, their
%properties and compare them against existing designs.
%
%Description of the operation of the timed alpha mix: 
%
%Alice gives each message an alpha (number of rounds) delay to each mix
%in a route. Once $t$ seconds have passed, all messages that are alpha
%0 get fired off, including any that were buffered and decremented to 0
%last time decrementing occurred.  Then all messages in the buffers get
%alpha decremented by 1. Any messages that enter with alpha $>0$ get
%put into the buffer with alpha of that number.
%
%The \emph{possibility} of setting $\alpha > 0$ improves anonymity in
%all cases (under the assumptions in Section \ref{sec-assumptions}),
%both for the sender \emph{and} for others.
%
%AAS: Improves anonymity compared to what? Threshold mix? That's really
%easy to show!
%
%PFS: Yes but significant (and we were thinking timed, but in steady
%state what's the diff). The point is that this little change is a win
%all around.
%
%--------------------------------- AAS: Not quite sure where this fits
%in, but it is quite good.
%
%If the attacker's knowledge about the users' security parameters is
%limited, the alpha mix closely resembles pool mixes
%\cite{Serj02,trickle02}. For instance, if the users draw $\alpha$ from a
%geometric distribution and this is known to the attacker, with
%parameter $p$ (i.e. the probability of $\alpha=0,1,2,\ldots$ is $q,
%pq, ppq, \ldots$), then the anonymity of the threshold alpha mix is
%simply equivalent to a threshold pool mix with a pool/(threshold +
%pool) = $p$. Curiously, if the attacker knows nothing about the
%distribution of $\alpha$, he may still perform a similar analysis
%based on the number of incoming and outgoing messages from a mix. The
%anonymity derived in this way is an easy exercise for the reader (or
%see~\cite{DiazThesis05}, Chapter 4.6)
%
%---------------------------
%
%
%AAS curious aside:
%
%
%--------------------------------------
%
%We also need to convince the reader than larger values of 1 are even
%better. The key is that raising $\alpha$ is increasing the variance.
%This matches the intuition described in \cite{e2e-traffic}.
%
%A timed alpha mix is also equivalent to the hint in sync-batching that
%you can get better anonymity by "hopping" batches.
%
%Flooding does not work against timed alpha mixes, but trickling still
%does.
%
%Next, let's look at threshold alpha mixes. The same reasoning as above
%still applies about how the possibility of a non-zero $\alpha$ improves
%anonymity all-around. Flooding works now, and trickling doesn't.
%
%Performance is a function of network load. No guaranteed minimum delays --
%but guaranteed minimum anonymity sets, assuming no blending attacks?
%
%\section{Dummies}
%
%What fraction of the traffic is dummies, then? We can graph this for
%various strategies. Paul says (for timed): always send out at least
%2 messages, and always add at least one dummy. In this case the dummy
%overhead is bounded: between NL and 2NL for N mixes. (This sounds
%suspicious now that I see it again -- is it wrong? -RD)
%
%\section{Strategic Choice of Alpha}
%
%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$ 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
%takes the latency hit.
%
%C.f. Andrei's complaints about stop-and-go -- in that design you had
%to anticipate the network load to get good anonymity, and in this
%design you need to anticipate the other users' anonymity/latency
%requirements to get what you want.
%
%Speaking of which, how does the network bootstrap? See the econymics
%paper where we argue that people who don't care about anonymity will
%be the early adopters, since the people who do care won't be willing
%to use it with no cover users. Similarly the first users will all
%choose $\alpha$ of 0, and then sometime later the users willing to try
%a non-zero $\alpha$ will arrive?
%
%The attacker's a priori expectation of Alice's paranoia improves his
%attack.
%
%\section{Example scenarios}
%
%Work a couple of examples scenarios with sample numbers of types of
%users, etc. Show that users with different utility functions all
%benefit.
%
%======================================================================

\bibliographystyle{plain}
\bibliography{alpha-mixing}
\end{document}