[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Corrected walk-through calculations for 4-node confi...
Update of /home2/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home/shmat/paper/doc/sync-batching
Modified Files:
model-app.tex model.tex sync-batching.bib
Log Message:
Corrected walk-through calculations for 4-node configs, added bib
references for my stuff.
Index: model-app.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/sync-batching/model-app.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- model-app.tex 23 Jan 2004 22:52:22 -0000 1.2
+++ model-app.tex 24 Jan 2004 04:52:08 -0000 1.3
@@ -79,22 +79,28 @@
to the adversary) as the first mix. The mixing performed by any
single mix is exactly the same as in the cascade case, thus mixing
distribution~(\ref{eq:cascfirst}) after the first hop is the same in a
-stratified array as in a cascade. After the first hop, however, mix $C$
-is selected only with probability $\frac{1}{2}$, while $D$ may also be
-selected with probability $\frac{1}{2}$ (by contrast, in a cascade $C$
-is selected with probability $1$). Distribution~(\ref{eq:cascsecond})
-has to be adjusted accordingly:
+stratified array as in a cascade.
+
+After the first hop, however, mix $C$ is selected only with probability
+$\frac{1}{2}$, while $D$ may also be selected with probability
+$\frac{1}{2}$ (by contrast, in a cascade $C$ is selected with probability
+$1$). Distribution~(\ref{eq:cascsecond}) has to be adjusted to take into
+account the fact that mix $D$, selected with probability $\frac{1}{2}$,
+has a $\frac{1}{4}$ chance of being hostile and thus leaving each
+received message in the same position.
\[
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
-\underbrace{\frac{2528}{65536}}_{
- \frac{1}{2}\cdot\frac{5056}{65536}}
+\underbrace{\frac{4672}{65536}}_{
+ \frac{1}{2}\cdot\frac{5056}{65536} +
+ \frac{1}{2}\cdot\frac{1}{4}\cdot\frac{67}{256}}
&
-\underbrace{\frac{480}{65536}}_{
- \frac{1}{2}\cdot\frac{960}{65536}}\
+\underbrace{\frac{576}{65536}}_{
+ \frac{1}{2}\cdot\frac{960}{65536} +
+ \frac{1}{2}\cdot\frac{1}{4}\cdot\frac{3}{256}}\
\ldots
&
-\underbrace{\frac{1}{128}}_{
- \frac{1}{2}\cdot\frac{1}{64}}\
+\underbrace{\frac{3}{512}}_{
+ \frac{1}{2}\cdot\frac{3}{4}\cdot\frac{1}{64}}\
\ldots
\\
\mbox{position}\ 1 &
@@ -103,9 +109,9 @@
\end{array}
\]
-Entropy of this distribution is approximately $6.9541$. Effective
+Entropy of this distribution is approximately $6.8342$. Effective
anonymity set provided by a 2x2 stratified array with 25\% density of
-hostile nodes and 128 messages per batch is 124 messages.
+hostile nodes and 128 messages per batch is 114 messages.
\subsection{Free-route network.}
@@ -133,23 +139,35 @@
\end{array}
\]
-The next mix is selected from among all four mixes with equal probability,
-producing the following probability distribution:
+The next mix is selected from among all four mixes with equal probability.
+A mix other than $A$ is selected with probability $\frac{3}{4}$, and
+has $\frac{1}{4}$ chance of being hostile, producing the following
+probability distribution:
\[
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
-\underbrace{\frac{376}{16384}}_{
- \frac{1}{4}\cdot(
- \frac{35}{128}\cdot\frac{35}{128} +
- \frac{3}{128}\cdot(31\cdot\frac{3}{128}))}
+\underbrace{\frac{1216}{16384}}_{
+ \begin{array}{rl}
+ \frac{1}{4}\cdot( &
+ \frac{35}{128}\cdot\frac{35}{128} + \\ [1ex] &
+ \frac{3}{128}\cdot(31\cdot\frac{3}{128})) + \\ [1ex]
+ \multicolumn{2}{l}{
+ \frac{3}{4}\cdot\frac{1}{4}\cdot\frac{35}{128}}
+ \end{array}}
&
-\underbrace{\frac{120}{16384}}_{
- \frac{1}{4}\cdot(
- \frac{35}{128}\cdot\frac{3}{128} +
- \frac{3}{128}\cdot(\frac{35}{128}+30\cdot\frac{3}{128}))}\
+\underbrace{\frac{192}{16384}}_{
+ \begin{array}{rl}
+ \frac{1}{4}\cdot( &
+ \frac{35}{128}\cdot\frac{3}{128} + \\ [1ex] &
+ \frac{3}{128}\cdot(\frac{35}{128}+30\cdot\frac{3}{128})) + \\ [1ex]
+ \multicolumn{2}{l}{
+ \frac{3}{4}\cdot\frac{1}{4}\cdot\frac{3}{128}}
+ \end{array}}\
\ldots
&
-\underbrace{\frac{1}{128}}_{
- \frac{1}{4}\cdot\frac{1}{32}}\
+\underbrace{\frac{3}{512}}_{
+ \begin{array}{l}
+ \frac{1}{4}\cdot\frac{3}{4}\cdot\frac{1}{32}
+ \end{array}}\
\ldots
\\
\mbox{position}\ 1 &
@@ -157,8 +175,7 @@
\mbox{positions}\ 33..128
\end{array}
\]
-
-Entropy of this distribution is approximately $6.9855$ and effective
-anonymity set is 127 messages~--- very close to that provided by a
-perfect mix network.
+Entropy of this distribution is approximately $6.7799$ and effective
+anonymity set is 110 messages~--- slightly lower than in a stratified
+2x2 array.
Index: model.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/sync-batching/model.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- model.tex 23 Jan 2004 22:52:22 -0000 1.3
+++ model.tex 24 Jan 2004 04:52:08 -0000 1.4
@@ -148,13 +148,16 @@
given a particular network topology. This assumption is approximated
with very high probability when the number of messages in a single batch
is significantly higher than the number of network nodes, and randomness
-involved in message routing is obtained from unbiased coin tosses in the
-same way for all messages. Intuitively, suppose there are four mixes in
-the first layer of the network, and batch size is 128. We will analyze
-the average-case behavior of the network, \ie, we will assume that each
-of the mixes receives exactly 32 messages, even though it is possible
-(albeit highly improbable) that in some batch all 128 senders will
-randomly choose the same entry mix.
+involved in message routing is obtained from unbiased coin tosses in
+the same way for all messages (see section \ref{subsec:average-actual}
+for a detailed discussion).
+
+Intuitively, suppose there are four mixes in the first layer of the
+network, and batch size is 128. We will analyze the average-case
+behavior of the network, \ie, we will assume that each of the mixes
+receives exactly 32 messages, even though it is possible (albeit highly
+improbable) that in some batch all 128 senders will randomly choose the
+same entry mix.
% An alternative to this is to assume instead that the adversary cannot
% observe communication between nodes that he does not control. Under
Index: sync-batching.bib
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/sync-batching/sync-batching.bib,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- sync-batching.bib 23 Jan 2004 23:33:44 -0000 1.5
+++ sync-batching.bib 24 Jan 2004 04:52:08 -0000 1.6
@@ -245,6 +245,19 @@
www_pdf_url = {http://avirubin.com/crowds.pdf},
}
+ @article(
+S04, author="V.~Shmatikov",
+ title="Probabilistic Model Checking of an Anonymity System",
+ journal="Journal of Computer Security (selected papers of CSFW-15)",
+ year="2004 (to appear)")
+
+@Unpublished{Pri,
+title={{PRISM} Web page},
+author={M.~Kwiatkowska~\emph{et al.}},
+year={},
+note={{\sf http://www.cs.bham.ac.uk/\~{}dxp/prism/}}
+}
+
@inproceedings{disad-free-routes,
title = {The disadvantages of free {MIX} routes and how to overcome them},
author = {Oliver Berthold and Andreas Pfitzmann and Ronny Standtke},
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/