[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] clean up the first few pages more
Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/home/arma/work/freehaven/doc/alpha-mixing
Modified Files:
alpha-mixing.bib alpha-mixing.tex
Log Message:
clean up the first few pages more
Index: alpha-mixing.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.bib,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- alpha-mixing.bib 10 Mar 2006 21:54:13 -0000 1.3
+++ alpha-mixing.bib 10 Mar 2006 22:01:49 -0000 1.4
@@ -1,3 +1,21 @@
+@inproceedings{Acquisti04,
+ author = {Alessandro Acquisti},
+ title = {Privacy in electronic commerce and the economics of immediate
+ gratification.},
+ booktitle = {ACM Conference on Electronic Commerce},
+ year = {2004},
+ pages = {21-29},
+}
+
+@phdthesis{DiazThesis05,
+ title = {Anonymity and Privacy in Electronic Services},
+ author = {Claudia D\'{\i}az},
+ school = {Katholieke Universiteit Leuven},
+ year = {2005},
+ month = {December},
+ address = {Leuven, Belgium},
+}
+
@inproceedings{tor-design,
author = "Roger Dingledine and Nick Mathewson and Paul Syverson",
title = {{Tor: The Second-Generation Onion Router}},
Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -d -r1.9 -r1.10
--- alpha-mixing.tex 10 Mar 2006 21:54:13 -0000 1.9
+++ alpha-mixing.tex 10 Mar 2006 22:01:49 -0000 1.10
@@ -50,7 +50,9 @@
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,
+attackers. By combining the user bases into the same network, we can
+make it possible to have enough users that anonymous high-latency
+traffic becomes feasible.
$\alpha$-mixing is an approach that can be added to traditional
batching strategies to let senders specify for each message whether they
@@ -60,11 +62,10 @@
\end{abstract}
-
\section{Introduction}
\label{sec:intro}
-Currently fielded anonymous communication systems don't provide
+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
@@ -82,7 +83,10 @@
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 the security
-parameter. Our scheme works with any of the standard mix types
+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.
@@ -98,8 +102,9 @@
%messages that enter with alpha $>0$ get put into the buffer with alpha
%of that number.
-Users that desire better anonymity have the opportunity to obtain it
-by increasing $\alpha$. More importantly, there is a network effect:
+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$)
@@ -110,14 +115,15 @@
%relying on, see the analysis section.
In this paper we start by outlining some simple
-alpha mix designs and analyse what anonymity properties they can
+$\alpha$-mix designs and analyse what anonymity properties they can
provide to users with different security preferences. Next we
-look at what strategies users should follow when picking their
-security parameters (recall that one is needed for each mix in the
-route of the message). Thirdly, we look at the incentives users have
-for choosing a high security parameter vs.~expecting others to do so
-(which provides more anonymity to everyone). Last we consider more
-sophisticated alpha mixing strategies which should provide better
+look at what strategies users should follow when picking the
+security parameter for each mix in the message's path.
+Thirdly, 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.
@@ -137,73 +143,64 @@
\section{Deterministic-alpha mix}
\label{sec:deterministic-alpha-mix}
-The simplest version of alpha mixing uses \emph{timed mixes}:
-the mixes
-fire at regular intervals. This is also most naturally in keeping with
-the motivation to include traffic for which timeliness matters, since
-this cannot be satisfied for threshold mixes (mixes that fire only
-when a sufficient number of messages have arrived) without assumptions
-about the rate of incoming messages. On the other hand, minimum
-anonymity properties that threshold mixes have may not be satisfied
-for timed mixes (without assumptions about the rate of incoming
-messages).
+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.
-As we will eventually see, one of the virtues of alpha mixing is that
+As we will see, one of the virtues of alpha mixing is that
the timed/threshold distinction for mixes can somewhat break down, and it
becomes more a distinction for firing strategies of individual
-messages than of mixes. Also, for our initial analysis we can assume
-a steady-state network for which the timed/threshold distinction will be
-moot for a passive adversary.
+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.
``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, possibly based on
-the number of messages at certain alphas in the mix. For now we expect
-all messages to simply drop one alpha level after each mix firing.
+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. (We do not describe the reordering of messages or
+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
+$\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
-initial $\alpha_0$ and are placed at the according $\alpha$ level.
-
+messages that arrive before the next firing are buffered based on
+their initial $\alpha_0$ and are placed at the according $\alpha$ level.
\paragraph{Threshold deterministic-alpha mix:}
-
-This is the same as the timed version just described, except that the
-mix fires when at least a threshold number of messages with $\alpha =
+This is the same as the timed version, except that the
+mix fires when at least a threshold $n$ messages with $\alpha =
0$ are in the mix. Note that since the number of messages with $\alpha
-= 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 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$ accumulate. This is
-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.
+= 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.)
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 a threshold number of messages have arrived. (Messages
-are actually sent only when the $\alpha = 0$ messages attain a
-threshold however.) Similarly, one can have a threshold-and-timed mix
+have passed or $n$ messages have arrived.
+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:dynamic-alpha}.
\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
-the different alphas for the mix at a regular rate, and the mix fires
+noted, we assume a steady-state network in which messages arrive with
+various alphas at a regular rate, and the mix fires
at regular intervals. Thus the threshold mix is indistinguishable by a
local external passive adversary from a timed mix.
@@ -232,7 +229,7 @@
$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 the
+ 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
@@ -242,9 +239,9 @@
just possibilistically.)
\end{proof}
-If the adversary knows the strategy (although not the actual
-$\alpha_0$) for each message, then the anonymity of a message is
-unaffected by the strategy for choosing $\alpha_0$ for other messages
+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$
in a steady-state network. However, if the strategies are not known,
then choosing $\alpha_0$ from a broader range increases the anonymity
for other messages in the mix as well, although it is difficult to say
@@ -260,13 +257,12 @@
Assume the $\alpha_{M,0}$ for any message $M$ is chosen uniformly
at random from the range
given by $0 \leq \alpha_{M,0} \leq k_{M,0}$.
- Then anonymity increases for any message $M$ in the mix if any
-% don't we mean 'for every message $M$'? -RD
+ Then anonymity increases for every message $M$ in the mix if any
$k_{M',0}$ increases.
\end{claim}
In summary, for threshold mixes or steady-state timed mixes, choosing
-$\alpha_0$ from a broader range improves the anonymity for a message
+$\alpha_0$ 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
@@ -461,7 +457,7 @@
Our focus so far has been on steady-state networks with passive
adversaries. However, we want to provide uncertainty even in edge
-cases~\cite{trickle02,generalized-mixes}. An active attacker
+cases~\cite{trickle02,pet2003-diaz}. 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 single messages enter and leave the mix in
@@ -518,7 +514,7 @@
\section{Strategic Choice of Alpha}
-As observed in section~\ref{sec:passive-adversary-anonymity}, the
+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
@@ -836,7 +832,7 @@
If the attacker's knowledge about the users' security parameters is
limited, the alpha mix closely resembles pool mixes
-\cite{SD01,SDS02}. For instance, if the users draw $\alpha$ from a
+\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
@@ -845,7 +841,7 @@
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{Diaz_thesis}, Chapter 4.6)
+see~\cite{DiazThesis05}, Chapter 4.6)
%---------------------------
%
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/