Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/tmp/cvs-serv28349
Modified Files:
alpha-mixing.tex
Log Message:
Mostly changes to strategic alpha stuff
Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- alpha-mixing.tex 9 Mar 2006 13:20:20 -0000 1.2
+++ alpha-mixing.tex 9 Mar 2006 18:49:15 -0000 1.3
@@ -109,6 +109,7 @@
\section{Deterministic-alpha mix}
+\label{sec:deterministic-alpha-mix}
Perhaps the simplest version of alpha mixing is one in which mixes
fire at regular intervals. This is also most naturally in keeping with
@@ -142,7 +143,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 labeled with some
-$\alpha$ and are placed at the according $\alpha$ level.
+initial $\alpha_0$ and are placed at the according $\alpha$ level.
\paragraph{Threshold deterministic-alpha mix:}
@@ -153,12 +154,12 @@
= 1$ may be above the firing threshold, there may be more than the
threshold number of messages in a batch. Also we assume that the input
buffer of the mix is read after the alpha stack is decremented but
-always before firing, so the received $\alpha = 0$ messages and the
-decremented to $\alpha = 0$ messages are all sent together even if
+always before firing, so the received messages with $\alpha_0 = 0$ and the
+decremented-to-($\alpha = 0$) messages are all sent together even if
there were more than the threshold of messages already in the stack at
$\alpha = 1$. Note that many messages with $\alpha > 0$ may be waiting
in a mix before a threshold number of $\alpha = 0$ arrive. This is
-akin to the fact that many mixes in a free-route batch mix net may be
+akin to the fact that many mixes in a free-route threshold-mix net may be
waiting and nearly full while messages are being accumulated at
relatively empty mixes.
@@ -171,6 +172,7 @@
\subsection{Deterministic-alpha mix:\\
anonymity against a local passive adversary}
+\label{sec:passive-adversary-anonymity}
We will describe anonymity for a threshold mix. As we have already
noted, we assume a steady-state network in which messages arrive at
@@ -205,9 +207,9 @@
entropy has increased by $\log(n(k-j)$.) If the adversary does not
know the strategy, then we cannot put a precise number on the
uncertainty. However, the less predictable the range is to the
- adversary, the greater the uncertainty is even if we cannot say how
+ 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 other
+ 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.)
@@ -236,7 +238,7 @@
\end{claim}
In sum, for threshold mixes or steady-state timed mixes, choosing
-$\alpha$ from a broader range improves the anonymity for a message
+$\alpha_0$ from a broader range improves the anonymity for a 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
@@ -267,7 +269,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$, a path with alpha distribution given by
+cumulative $A = \sum \alpha_0$, 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
@@ -286,7 +288,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 a given message.
+range of $\alpha_0$ with certainty for all messages he observes.
A very lightweight dummy policy can guarantee that no exact attack is
possible against an alpha mix, even for active attackers. Simply
@@ -311,10 +313,11 @@
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, a uniform strategy (as above), or better a weighted
+is uninitialized, individual mixes can be initialized with
+a uniform strategy (as above), or better a weighted
one, e.g., add a dummy at level $\alpha$ with probability
-$1/2^{\alpha+1}$, and then periodically shifted to reflect the
-distribution alphas for actual traffic through the mix.
+$1/2^{\alpha+1}$. Dummy policy can then be periodically shifted
+to reflect the distribution of alphas for actual traffic through the mix.
If active attacks are suspected, the amount of dummy traffic added to
the alpha stack can be increased according to the expected duration of
@@ -579,43 +582,86 @@
Performance is a function of network load. No guaranteed minimum delays --
but guaranteed minimum anonymity sets, assuming no blending attacks?
-\section{Dummies}
-
-Just as with batching-taxonomy and generalized-batching, we want to
-provide uncertainty even in edge cases.
-
-The active attacker can arrange an edge case via blending attacks, but
-a passive attacker can also simply wait for an edge case to occur.
-
-We need to always apply the dummy strategy because we can't know
-if we're under attack. Dummies should be routed back to ourselves,
-a la heartbeat-traffic.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+% Following section is now all in rewritten
+% Dummies section above, no? -PFS
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+%\section{Dummies}
+%
+%Just as with batching-taxonomy and generalized-batching, we want to
+%provide uncertainty even in edge cases.
+%
+%The active attacker can arrange an edge case via blending attacks, but
+%a passive attacker can also simply wait for an edge case to occur.
+%
+%We need to always apply the dummy strategy because we can't know
+%if we're under attack. Dummies should be routed back to ourselves,
+%a la heartbeat-traffic.
+%
+%
+%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)
+%
+%Note that we can achieve Andrei's goal of strict uncertainty with
+%way more efficiency just by having a single dummy anywhere in the
+%buckets.
+%\section{Game Theory}
+\section{Strategic Choice of Alpha}
-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)
+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
+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.
-Note that we can achieve Andrei's goal of strict uncertainty with
-way more efficiency just by having a single dummy anywhere in the
-buckets.
+Not all users have the same sensitivity level, however. In fact users
+will have different sensitivity levels for different communications.
+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
+my incentive to set higher $\alpha$ levels for my own traffic, it
+does not eliminate that incentive.
-\section{Game theory}
+Choosing alpha range based on the sensitivity and timeliness
+constraints of one's own messages increases the autonomy and control
+over one's own security and utility. Indeed, if an adversary can make
+reasonable guesses about a choice of alpha range for a message, then
+increased alpha for other messages in a mix might not increase
+anonymity for a target message, e.g., if that increased alpha would
+only vary the range that is after the target message is expected to
+have left the mix.
-Since Alice benefits from the fact that other people might choose non-zero
-$\alpha$, she has an incentive to take advantage of this by choosing a
-lower $\alpha$ to get better performance but still have good security. In
-the limit, it's a commons: everybody will hope that somebody else takes
-the latency hit.
+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 finetuned knowledge of the system,
+the behavior of others, and their own needs. Thus if we can
+prescribe recommendations for choice of alpha, e.g., based on
+analysis and observed patterns within the network, we can expect
+most people to heed them. (Although they may not follow them. We
+can expect hyperbolic discounting of risk, disregard of risk
+for expedience, etc.~\cite{acquisti04}.)
-Did our equations in sec-analysis show that Alice gets better anonymity
-if she's the one who chooses the higher alpha? If so then we're more ok.
+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 obiously must have $\sum \alpha = 0$.
+For more sensitive traffic, we might initially try to follow
+networks such as Mixminion. But how to do that since mixing*****
-Mixminion and Tor are in some sense the two extremes of the goal spectrum.
-More generally, the senders in our mixnet have utility functions U that
-describe what $\Sigma\alpha$ they will pick. Our whole design works because
some of the users favor performance and some favor anonymity. Three
factors are most important here:
@@ -653,6 +699,11 @@
\section{Distributing your alphas over the path}
+******************************************\\
+Presumably Andrei will incorporate this with the section above
+(\label{sec:distributing-alpha}) when he picks it up later today.\\
+******************************************\\
+
The first node (or second, or...) can learn about Alice's paranoia
level. So given $\Sigma \alpha$ which represents Alice's concern for
this message's anonymity, we need an algorithm for allocating which
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/