[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Spell check and various small edits have no idea wha...
Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/home/aas23/doc/alpha-mixing
Modified Files:
alpha-mixing.tex
Log Message:
Spell check and various small edits have no idea what now
Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- alpha-mixing.tex 10 Mar 2006 23:59:23 -0000 1.16
+++ alpha-mixing.tex 11 Mar 2006 00:13:20 -0000 1.17
@@ -52,7 +52,7 @@
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
-ensring that all traffic is mixed together, we hope to lower delay 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
@@ -61,7 +61,7 @@
$\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 paramaters of the users.
+attacker's knowledge of the security parameters of the users.
\end{abstract}
@@ -104,13 +104,13 @@
%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
+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$.
+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
@@ -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:beta-alpha}.
+Section~\ref{sec:dynamic-alpha}.
\subsection{Deterministic-alpha mix:\\
anonymity against a local passive adversary}
@@ -209,14 +209,13 @@
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{Attacker-knowledge}. What
+examine this issue further in Section \ref{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 determistic-alpha
+ 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}
@@ -270,7 +269,7 @@
knows simply the distribution of strategies, then increasing the
$alpha$-range for any message improves anonymity for all messages.
-\subsection{Attacker Knowledge}
+\subsection{Attacker knowledge}
\label{Attacker-knowledge}
In the previous section we noted that the anonymity properties
@@ -316,7 +315,7 @@
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 $y_{max}$.
+every message $x$ with $a$ ranging from 0 to $a_{max}$.
Now, the anonymity probability distribution:
@@ -328,40 +327,30 @@
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}
+\subsection{Correlating offensiveness with 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
+message from sender $S$ at round 0, and a message with a death threat
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
+0. Our above definitions (naturally) give the offensive message the
+anonymity set of all the sender of round 5 union $S$. Nevertheless, we
+conjecture the jury will tend to suspect that $S$ sent the
+message. How can we reconcile the opinion of the jury with our
formalism above and how can we design the system to avoid such a
judgement?
-The attacker is likely to be correct
-%(though hopefully not beyond a
-%reasonable doubt from this description as we argue below)
---- what we
+The jury is likely to be correct (though hopefully not beyond a
+reasonable doubt from this description as we argue below) -- 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
+likely \emph{conditional} on the offensiveness 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, this
-distribution can still be conditional on the utility
-function.)
-
-Of course, there are still external factors to consider. If
-Indeed, we can go a step further and design the software so that the
-sender can not influence his choice of
-
-one must convince the jury that the sender *could
-not* have picked the alphas any other way (otherwise those with high
+this, we must (paradoxically!!) ignore this fact completely and pick
+alphas from a distribution which is independent of the receiver (this
+distribution, of course, is allowed to be conditional on the utility
+function!). Indeed, one must convince the jury that the sender \emph{could
+not} have picked the alphas any other way (otherwise those with high
latency/security tradeoff will be more likely to be suspected of dodgy
things as is indeed the case in practice as no doubt every anonymity
researcher has experienced. In anonymity language, the attacker will
@@ -374,7 +363,7 @@
In the previous section we discussed the fact that we should pay close
attention to picking the security parameter alpha. Sending only high
-value mesages and picking high security parameters for them actually
+value messages and picking high security parameters for them actually
decreases anonymity.
In this section we deal with the problem of distributing the security
@@ -382,29 +371,30 @@
that the message takes. There are two problems. First, 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.}
+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. This matters for the reasons described in
-the previous section.
+is concerned about security for the reasons mentioned in the previous
+section.
One possible solution for picking a sequence of $\alpha^{(i)}$ (where
the `$(i)$' represents the $i^{th}$ mix in the route) is precisely to
pick from a uniform distribution over the partitions of $\Sigma
-\alpha$ into $\ell$ buckets where the buckets themselves are
+\alpha$ into $l$ buckets where the buckets themselves are
indistinguishable. The number of such partitions are given by
\[
-\sum_k=1^\ell Q(\Sigma \alpha, k)
+\sum_k=1^l Q(\Sigma \alpha, k)
\]
where $Q(n,k)$ denotes the number of ways of partitioning $n$ 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
+second part, we need to decide whether the sender cares
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
@@ -422,7 +412,7 @@
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
+locally know anything 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
@@ -559,7 +549,7 @@
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 finetuned knowledge of the system,
+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, e.g., based on analysis and
observed patterns within the network, we can expect most people to
@@ -574,16 +564,12 @@
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 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}
+We now turn to how to combine these features.
+\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
@@ -601,7 +587,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
@@ -616,36 +602,9 @@
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. 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.
+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.
@@ -679,24 +638,6 @@
\section{Conclusion}
-In this paper we have presented a mix technique that works together
-with traditional batching strategies to allow senders with varying
-anonymity and performance goals to share the same network. 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.
-
-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. Much of the reason for Tor's success
-is not just its low overhead, but rather its 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.
-
-...
%%%% Stuff with 4s is stuff from alpha strategy section
%%%% that I didn't want to toss just yet
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/