[freehaven-cvs] Section 2.3 + reference

[aas23@xxxxxxxx]

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/