[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freehaven-cvs] next patches, now it includes fewer wrong things

To: freehaven-cvs@freehaven.net
Subject: [freehaven-cvs] next patches, now it includes fewer wrong things
From: arma@seul.org (Roger Dingledine)
Date: Sat, 31 Aug 2002 06:23:26 -0400 (EDT)
Delivered-To: archiver@seul.org
Delivered-To: freehaven-cvs-outgoing@seul.org
Delivered-To: freehaven-cvs@seul.org
Delivery-Date: Sat, 31 Aug 2002 06:23:27 -0400
Reply-To: freehaven-dev@freehaven.net
Sender: owner-freehaven-cvs@freehaven.net
Update of /home/freehaven/cvsroot/doc/batching-taxonomy
In directory moria.seul.org:/home/arma/work/freehaven/doc/batching-taxonomy

Modified Files:
	taxonomy.bib taxonomy.tex 
Log Message:
next patches, now it includes fewer wrong things

still not happy with it, but getting closer.


Index: taxonomy.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.bib,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- taxonomy.bib	31 Aug 2002 02:12:02 -0000	1.5
+++ taxonomy.bib	31 Aug 2002 10:23:24 -0000	1.6
@@ -270,7 +270,7 @@
 @InProceedings{Serj02,
   author = 	 {Andrei Serjantov and George Danezis},
   title = 	 {Towards an Information Theoretic Metric for Anonymity},
-  booktitle =    {Privacy Enhacing Technologies},
+  booktitle =    {Privacy Enhancing Technologies},
   year = 	 2002,
   editor =	 {Paul Syverson and Roger Dingledine},
   series = 	 {LNCS},

Index: taxonomy.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.tex,v
retrieving revision 1.20
retrieving revision 1.21
diff -u -d -r1.20 -r1.21
--- taxonomy.tex	31 Aug 2002 02:12:02 -0000	1.20
+++ taxonomy.tex	31 Aug 2002 10:23:24 -0000	1.21
@@ -137,7 +137,7 @@
 the case of a single threshold $n$ mix\footnote{The same attack can be
   used against a mix cascade by mounting it against the first mix, or
   against a mix network by repeating it $l$ (the number of mixes in
-  the route of the message) times.}.  The attack, commonly referred to
+  the path) times.}.  The attack, commonly referred to
 as the $n-1$ attack, proceeds as follows: The attacker observes the
 target message leaving the sender heading towards the mix and delays
 it.  He now starts sending messages into the mix until it fires. As
@@ -549,19 +549,22 @@
 %and/or send messages at very high rates.
 
 \paragraph*{Analysis:} 
-Flushing out the mix: after $k$ rounds, the probability that a
+Flushing out the mix: after $r$ rounds, the probability that a
 particular message that was in the mix at round $0$ is still in the
-mix by round $k$ is
+mix by round $r$ is
 
 \[
-\left(\frac{f}{n+f}\right)^k
+\left(\frac{f}{n+f}\right)^r
 \]
 
-Equivalently, if there were $N$ good messages in the mix initially,
-the expected number left after $k$ flushes is
+If there were $N$ good messages in the mix initially,
+the expected number left after $r$ flushes is $N$ times the above.
+
+Alternately, we might consider the chance that all $N$ good messages
+have left the mix by round $r$:
 
 \[
-N\left(\frac{f}{n+f}\right)^k
+\left(1-\left(\frac{f}{n+f}\right)^r\right)^N
 \]
 
 The number of good messages in the mix at the beginning of the attack
@@ -572,7 +575,9 @@
 The average delay of a message through this mix is 1.6
 rounds. Assuming the attacker targets a mix with 60 messages,
 the expected number of good messages remaining in the mix falls below
-1 after 5 rounds or 500 attacker messages.
+1 after 5 rounds or 500 attacker messages. Similarly, the chance that
+all 60 messages have left the pool goes above 50\% after 5 rounds,
+and reaches 99\% after 9 rounds.
 \end{exa}
 
 Thus, the use of a pool mix in an anonymity system not only makes the
@@ -671,24 +676,25 @@
 $t$, period; $\minf$ minimum pool; $\piece$, fraction of messages to be
 sent; ($n$, threshold)
 
-
 \paragraph*{Flushing Algorithm:} 
 The mix fires every $t$ seconds, provided there are $n+\minf$ messages
 in the mix; however, instead of sending $n$ messages (as in a
 timed-and-threshold constant-pool mix), the mix sends the greater of
 $1$ and $\lfloor m*\piece \rfloor$ messages, and retains the rest in
 the pool, where $m+\minf$ is the number of messages in the mix ($m
-\geq n$). If $n=1$, this is the mix that has been used in MixMaster
-remailer system for years. We will continue to use the term `Cottrell
+\geq n$). If $n=1$, this is the mix that has been used in the Mixmaster
+remailer system for years. We use the term `Cottrell
 mix' for $n=1$ and `timed dynamic-pool mix' for the more general case
-when $n$ might be greater than one. Although the Cottrell mix has been
-used in Mixmaster, it has never been previously described or
-analyzed.\footnote{This is the Mixmaster mix design as given in
-  personal communication from Lance Cottrell, the original designer
-  and implementer of MixMaster.  It is also the one used in the
-  current MixMaster network.  \cite{Jer2000} describes a different mix
-  that is called ``Mixmaster'' therein.} We believe this paper is the
-first place that more general dynamic-pool mixes have been introduced.
+when $n$ might be greater than one.
+% Although the Cottrell mix is
+%used in Mixmaster, it has never been previously described or
+%analyzed.\footnote{This is the Mixmaster mix design as given in
+%  personal communication from Lance Cottrell, the original designer
+%  and implementer of Mixmaster.  It is also the one used in the
+%  current Mixmaster network.  \cite{Jer2000} describes a different mix
+%  that is called ``Mixmaster'' therein.} We believe this paper is the
+%first place that more general dynamic-pool mixes have been introduced.
+
 We have called constant-pool mixes simply `pool mix' up to now for
 consistency with the previous literature. Hereafter, `pool mix' will
 refer to either constant or dynamic pool mixes.
@@ -696,7 +702,7 @@
 When messages arrive at a constant rate of $1$ per period, Cottrell
 mixes are equivalent to both timed mixes and threshold-$1$
 constant-pool mixes.  Specifically, if the rate $r$ of message arrival
-is $1/t$, then the mix will forward $1$ message in every period and
+is $1/t$, the mix will forward $1$ message in every period and
 retain $\minf$ in the pool. For a general Cottrell mix, if the
 messages arrive at a constant rate of $n*\piece/t$ and $\lceil
 n*\piece \rceil = n*\piece$, then this is equivalent to a
@@ -726,7 +732,7 @@
 constant, whereas it decreases in the case of the timed constant-pool
 mix.  While the chance of a message remaining in a threshold
 constant-pool mix is also constant for each flush, increased
-message rate causes increased flushing, thus reducing the chance of a
+message rate means more frequent flushing, thus reducing the chance of a
 message remaining in the constant-pool threshold mix per unit time.
 
 \paragraph*{Blending Attack Behaviour:}
@@ -737,9 +743,9 @@
 in one flush is $\piece$. Therefore there is no possibility of
 flushing the mix with high probability in one flush: the first of the
 two blending attacks on timed constant-pool mixes is blocked.  As
-already noted, it is similarly more resistant to flooding than is a
-constant-pool threshold mix. Indeed, this greater resistance to
-blending attacks is the motivation for that design feature.
+already noted, it is similarly more resistant to flooding than a
+constant-pool threshold mix.% Indeed, this greater resistance to
+%blending attacks is the motivation for that design feature.
 
 Secondly, the attacker has to find out how many messages are in the
 mix.  Of course, the number of good messages in the mix is easy to
@@ -752,7 +758,6 @@
 %messages remaining %(trivial, think about it!) 
 %or just let the mix alone for a while until it outputs nothing 
 %in which case $min$ messages remain. 
-%
 
 Finally, the number of messages inside the pool mix may be arbitrarily
 high and cannot be reduced to below $\minf$ in one round.  Therefore,
@@ -767,7 +772,7 @@
 %will require either more time or more messages from the attacker.}.
 %
 
-Thus timed dynamic-pool mixes requires the attacker to be able to
+Thus timed dynamic-pool mixes require the attacker to
 delay all the traffic to the mix for a substantial number of rounds,
 and therefore for a substantial time.
 
@@ -776,8 +781,7 @@
 $\frac{6}{10}$ requires 5 rounds for the expected number of good
 messages remaining in the mix to fall below 1. If the period is 5
 minutes, the overall flushing time is 25 mins. 500 messages will be
-used in the first part of the attack. % and how many to flush the
-% target message out?
+used in the first part of the attack.
 \end{exa}
 
 This example shows that the protection this mix provides against
@@ -801,10 +805,8 @@
 We note that the minimum anonymity of the Cottrell mix is still very
 much worse than that of the threshold constant-pool mix (where the
 threshold size is much larger than the pool size). Therefore, we
-propose a larger threshold timed dynamic-pool mix will have better
-minimum anonymity properties. We believe
-%We shall not go into any more detail other than to say
-%that it is intuitively clear that 
+propose a larger threshold for the timed dynamic-pool mix, to improve
+its minimum anonymity properties. We believe
 this modification will not have
 adverse effects on the blending attack properties, although will
 slightly decrease the efficiency of this mix.
@@ -906,13 +908,13 @@
 messages. At the other extreme, in a cascade topology, a single
 compromised mix has absolute control over the downstream message
 batch. In this case verification of correct processing is critical, to
-prevent wholescale (unobservable!)  anonymity compromise. Methods to
+prevent wholescale (unobservable!) anonymity compromise. Methods to
 detect an attack afterwards, e.g. by checking for successful delivery
 of test messages at the end of the cascade \cite{casc-rep}, can help
-detect misbehaving mixes --- but this only works for cascades, and it
-assumes that which messages are test messages can be hidden from the
-cascade head.  As we design new protocols and batching approaches, we
-must consider this tradeoff between protection from blending attacks
+detect misbehaving mixes --- but this technique only works for cascade
+topologies, and it assumes that the cascade head cannot distinguish
+test messages. As we design new protocols and batching approaches,
+we must consider this tradeoff between protection from blending attacks
 and verifiability.
 
 \subsection{Cover Traffic}

***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/
Prev by Date: [freehaven-cvs] checkpointing patches from paul, modulo patches from...
Prev by thread: [freehaven-cvs] checkpointing patches from paul, modulo patches from...
Index(es):
- Date
- Thread