[freehaven-cvs] add back in the 2.2 and other changes and conclusion

[arma@xxxxxxxx]

Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/home/arma/work/freehaven/doc/alpha-mixing

Modified Files:
	alpha-mixing.tex 
Log Message:
add back in the 2.2 and other changes and conclusion


Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -d -r1.18 -r1.19
--- alpha-mixing.tex	11 Mar 2006 00:24:52 -0000	1.18
+++ alpha-mixing.tex	11 Mar 2006 00:31:12 -0000	1.19
@@ -209,7 +209,7 @@
 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.
@@ -270,17 +270,17 @@
 $alpha$-range for any message improves anonymity for all messages.
 
 \subsection{Attacker knowledge}
-\label{Attacker-knowledge}
+\label{sec:attacker-knowledge}
 
 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.
+security parameters of the users. Specifically, while choosing from a wider
+range of alphas improves anonymity, an attacker can reduce anonymity
+if he has information about which alphas are chosen. We illustrate this
+on a simple example.
 
 Consider sender anonymity in the setting of just one mix, illustrated
-on two rounds only (equivalently, suppose maximum alpha is 1)
+on two rounds only (equivalently, suppose maximum alpha is 1):
 
 Round 1: $I_1 = i_{1,1} \ldots i_{n,1}$ entered the mix, messages
 $o_{1,1} \ldots o_{x,1}$ came out.
@@ -302,7 +302,7 @@
 
 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
+\emph{may} leave the message with no anonymity; however, this is
 extremely unlikely (or amounts to a rather expensive variant of the
 trickle attack).
 
@@ -327,30 +327,40 @@
 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}
+\subsection{Correlating message content with requested 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 with a death threat
+message from sender $S$ at round 0, and a message detailing Enron's
+finances emerges
 at round 5. Suppose further that all other messages have an alpha of
-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
+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
 formalism above and how can we design the system to avoid such a
 judgement?
 
-The jury is likely to be correct (though hopefully not beyond a
-reasonable doubt from this description as we argue below) -- what we
+The attacker is likely to be correct --- what we
 ignore here is the fact that the choice of the security parameter is
-likely \emph{conditional} on the offensiveness of the message and the
+likely \emph{conditional} on the importance 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 (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
+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.
+We'd like to go a step further and make the sender's software
+enforce that he doesn't vary alpha based on the receiver or message
+content.
+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
 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
@@ -371,22 +381,22 @@
 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 for the reasons mentioned in the previous
-section.
+is concerned about security. This matters  for the reasons described
+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 $l$ buckets where the buckets themselves are
+\alpha$ into $\ell$ buckets where the buckets themselves are
 indistinguishable. The number of such partitions are given by
 
 \[
-\sum_k=1^l Q(\Sigma \alpha, k)
+\sum_k=1^\ell Q(\Sigma \alpha, k)
 \]
 
 where $Q(n,k)$ denotes the number of ways of partitioning $n$ into
@@ -674,6 +684,24 @@
 
 \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/