[freehaven-cvs] Andrei"s changes from last night (this AM to Andrei).

[syverson@xxxxxxxx]

Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/tmp/cvs-serv8416

Modified Files:
	alpha-mixing.tex 
Log Message:

Andrei's changes from last night (this AM to Andrei).

Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- alpha-mixing.tex	9 Mar 2006 01:57:17 -0000	1.1
+++ alpha-mixing.tex	9 Mar 2006 13:20:20 -0000	1.2
@@ -53,29 +53,47 @@
 \section{Introduction}
 \label{sec:intro}
 
-Motivation:
-
 Tor exists with its low latency, but not very good security.
+Mixminion exists with its high latency, but very few users. Here we
+design a hybrid batching strategy that tries to put both user bases
+into the same network but still let them achieve their goals.
 
-Mixminion exists with its high latency, but no users.
+The basic concept of the scheme is as follows: The sender communicates
+an alpha -- a security parameter -- to each mix along the route of the
+message. The time the message spends inside each mix and hence the
+anonymity it accumulates then depends on the size of the security
+parameter and, optionally on a few other key variables such as the
+traffic level in the network, (the number of messages inside the mix)
+or a random number chosen by the mix.
 
-Here we design a hybrid batching strategy that tries to put both user
-bases into the same network but still let them achieve their goals.
+%Alice gives each message an alpha (number of rounds) delay to each mix
+%in a route. Once a threshold number of messages with alpha 0 enter the
+%mix all messages that are alpha 0 get fired off, including any that
+%were buffered and decremented to 0 last time decrementing occurred.
+%Then all messages in the buffers get alpha decremented by 1. Any
+%messages that enter with alpha $>0$ get put into the buffer with alpha
+%of that number.
 
-Overview (the new mixes).
+The key observation is that since we assume that the attacker knows
+little about the security parameters chosen by the individual users,
+everyone can benefit from the mere possibility of doing so, and indeed
+any users which desire better anonymity have the opportunity to obtain
+it by increasing alpha.
 
-Alice gives each message an alpha (number of rounds) delay to each mix
-in a route. Once a threshold number of messages with alpha 0 enter the
-mix all messages that are alpha 0 get fired off, including any that
-were buffered and decremented to 0 last time decrementing occurred.
-Then all messages in the buffers get alpha decremented by 1. Any
-messages that enter with alpha $>0$ get put into the buffer with alpha
-of that number.
+%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
+%relying on, see the analysis section.
 
-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
-relying on, see the analysis section.
+In this paper we proceed as follows: first, we outline the very simple
+alpha mixes and analyse the anonymity properties which they can
+provide to users with different security preferences. Secondly, we
+look at the strategies the 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 more sophisticated alpha
+mixing strategies which should provide better properties but are hard
+to analyse. Finally we conclude.
 
+AAS: this should all hopefully be in the paragraph above.
 \subsection{Outline}
 
 1. Deterministic-alpha mixes\\
@@ -95,11 +113,12 @@
 Perhaps the simplest version of alpha mixing is one in which 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.
+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.
 
 As we will eventually see, one of the virtues of alpha mixing is that
 the timed/threshold distinction for mixes can somewhat break down, and it
@@ -224,7 +243,7 @@
 $alpha$-range for any message improves anonymity for all messages.
 
 
-\subsection{Distributing $\sum \alpha$ against a distributed adversary}
+\section{Distributing $\sum \alpha$ against a distributed adversary}
 \label{sec:distributing-alpha}
 
 While a rising alpha seems to lift all boats, and one's own against
@@ -255,7 +274,7 @@
 passive observer will still have some difficulty linking endpoints or
 even identifying them as associated with any sensitive message.
  
-\subsection{Dummies}
+\section{Dummies}
 
 Our focus so far has been on steady-state networks with passive
 adversaries. However, we want to provide uncertainty even in edge
@@ -265,9 +284,9 @@
 will be occasions when only single messages enter and leave the mix in
 a single round. Alpha mixes have a clear advantage here since there is
 no guarantee that the message that exited the mix is the same message
-that entered. The attack is never exact (guaranteed to recognize
-a target message as it exits the mix) unless the adversary can
-bound the range of $\alpha_0$ with certainty for a given message.
+that entered. The attack is never exact (guaranteed to recognize a
+target message as it exits the mix) unless the adversary can bound the
+range of $\alpha_0$ with certainty for a given message.
 
 A very lightweight dummy policy can guarantee that no exact attack is
 possible against an alpha mix, even for active attackers. Simply
@@ -313,10 +332,40 @@
 and others should appear to be in mid path as they emerge from the mix
 (cf.\ Section~\ref{sec:distributing-alpha}).
 
-***************\\
-Where Paul stopped on Wednesday. Below is unchanged from before today.
-***************\\
+%***************\\
+%Where Paul stopped on Wednesday. Below is unchanged from before today.
+%***************\\
+
+\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 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
+conjecture the jury (AAS: can we cite a case???) 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 jury is, of course, 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 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 *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 dobt every anonymity
+researcher has experienced.
+
+%***************\\
+%Where Andrei stopped on Thursday. Below is unchanged from before.
+%***************\\
 
 \section{Assumptions}
 
@@ -510,32 +559,6 @@
 
 AAS curious aside:
 
-\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 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
-conjecture the jury (AAS: can we cite a case???) 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 jury is, of course, 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 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 *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 dobt every anonymity
-researcher has experienced :)
 
 --------------------------------------
 
@@ -668,3 +691,4 @@
 \bibliographystyle{plain}
 \bibliography{alpha-mixing}
 \end{document}
+

***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/