[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Section 2.3 + reference
Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/home/aas23/doc/alpha-mixing
Modified Files:
alpha-mixing.bib alpha-mixing.tex
Log Message:
Section 2.3 + reference
Index: alpha-mixing.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.bib,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- alpha-mixing.bib 10 Mar 2006 22:01:49 -0000 1.4
+++ alpha-mixing.bib 10 Mar 2006 23:20:30 -0000 1.5
@@ -1,3 +1,24 @@
+%Non-Uniform Random Variate Generation
+%(originally published with Springer-Verlag, New York, 1986)
+%Luc Devroye
+
+@Book{devroye86,
+ author = {Luc Devroye},
+ ALTeditor = {},
+ title = {Non-Uniform Random Variate Generation},
+ publisher = {Springer-Verlag},
+ year = {1986},
+ OPTkey = {},
+ OPTvolume = {},
+ OPTnumber = {},
+ OPTseries = {},
+ OPTaddress = {},
+ OPTedition = {},
+ OPTmonth = {},
+ note = {Available from: \url{http://cgm.cs.mcgill.ca/~luc/rnbookindex.html}},
+ OPTannote = {}
+}
+
@inproceedings{Acquisti04,
author = {Alessandro Acquisti},
title = {Privacy in electronic commerce and the economics of immediate
Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -d -r1.11 -r1.12
--- alpha-mixing.tex 10 Mar 2006 23:04:17 -0000 1.11
+++ alpha-mixing.tex 10 Mar 2006 23:20:30 -0000 1.12
@@ -207,7 +207,8 @@
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. What
+adversary might know the strategy by which alpha was chosen; we
+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.
@@ -269,28 +270,30 @@
$alpha$-range for any message improves anonymity for all messages.
\subsection{Attacker Knowledge}
+\def{Attacker-knowldge}
-AAS: not entirely sure what to do with this thing quite yet, but I
-think it should go here and complement Paul's claim: proof: paragraphs
-
-
-The anonymity properties, of course, depend on what the attacker knows
-about the security parameter of the users.
+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. Indeed, while choosing from a wider
+range of alphas improves anonymity, if the attacker having information
+about which alphas are chosen, reduces it. We illustrate this on a
+simple example.
-Sender anonymity, one mix, illustrated on two rounds only (equivalently,
-suppose maximum alpha is 1 just to illustrate the idea)
+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_{n,1}$ came in, messages $o_{1,1} \ldots
-o_{x,1}$ came out.
+Round 1: $I_1 = i_{1,1} \ldots i_{n,1}$ entered the mix, messages
+$o_{1,1} \ldots o_{x,1}$ came out.
-Round 2: $I_2 = i_{1,2} \ldots i_{m,2}$ came in, messages $o_{1,2} \ldots
-o_{y,2}$ came out.
+Round 2: $I_2 = i_{1,2} \ldots i_{m,2}$ entered, messages $o_{1,2}
+\ldots o_{y,2}$ came out.
$\alpha(x)$ is the set of possible alphas of message $x$ as known by
the attacker. Note that if the attacker knows nothing, then $\forall x
\alpha(x) = {0,1}$
-Our target message is $o_{1,2}$. Anonymity set (in messages):
+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
@@ -300,28 +303,29 @@
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 variant of the trickle attack, a
-rather stupid one when you come to think of it).
+extremely unlikely (or amounts to a rather expensive variant of the
+trickle attack).
-Now, the anonymity probability distribution is also an easy thing to
-work out, 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.
+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 $x_{\alpha}$ the alpha in message $x$. Hence the
-attacker knows the probability distributions $P(x_{\alpha}=y)$ for
-every message $x$, y ranging from 0 to $y_max$, [PFS: huh?] in our case 1.
+attacker knows the probability distributions $P(x_{\alpha}=a)$ for
+every message $x$ with $a$ ranging from 0 to $y_{max}$.
-Now, the anonymity probability distribution in the case above is:
+Now, the anonymity probability distribution:
\[
\mbox{Normalise}(\{p | x \in I_1 \wedge p = P(x_{\alpha}=0)\} \cup
\{p | x \in I_2 \wedge p = P(x_{\alpha}=1))
\]
-AAS: Paul, what's the notation for a finite probability distribuiton
-like this??? Can't think off hand.
+and the anonymity is the entropy of this distribution. Clearly, the
+more the attacker knows about alpha, the lower the anonymity.
\subsection{Correlating Offensiveness with Security}
@@ -330,8 +334,8 @@
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 with a death threat
at round 5. Suppose further that all other messages have an alpha of
-0. Our definitions (naturally) give the offensive message the
-anonymity set of all the sender of round 5 union S. Nevertheless, we
+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
@@ -388,7 +392,7 @@
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{Devroye}. This seems to deal with the first problem (the
+\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, we need to decide whether the sender cares
about having an estimate of the security parameter
@@ -421,10 +425,6 @@
by increasing path length, with the usual concomitant risk to
robustness of delivery that comes with increased path length.
-%Non-Uniform Random Variate Generation
-%(originally published with Springer-Verlag, New York, 1986)
-%Luc Devroye
-
%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
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/