[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] break the entropy walk-throughs into an appendix
Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching
Modified Files:
sync-batching.tex model.tex
Added Files:
model-app.tex
Log Message:
break the entropy walk-throughs into an appendix
--- NEW FILE: model-app.tex ---
\section{Entropy examples for each topology}
\label{sec:walk-through}
\subsection{Cascade.}
Consider a 2x2 cascade network as in fig.~\ref{fig:casc-2x2}. Assume
there are 128 messages in a batch, and that any node has $\frac{1}{4}$
chance of having been compromised. Let $m$ be the targeted message,
and suppose the adversary observed that the sender of $m$ chose $A$
as the first mix. Under the equal loading assumption, there are 63
other messages in addition to $m$ that chose $A$ as the first mix.
Without loss of generality, we may assume that $m$ occupies the first
position in $A$'s input buffer of length 64.
With probability $\frac{1}{4}$, mix $A$ is hostile. In this case,
$m$ remains in the first position after passing through the mix.
With probability $\frac{3}{4}$, mix $A$ is honest. In this case, $m$
appears in any of the 64 output positions of this mix with probability
$\frac{1}{64}$ (note that $m$ may not appear in the output buffer of
mix $B$). The resulting probability distribution for $m$'s position
after passing through $A$ is
\begin{equation}
\label{eq:cascfirst}
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
\underbrace{\frac{67}{256}}_{\frac{1}{4} \cdot 1 +
\frac{3}{4}\cdot\frac{1}{64}}
&
\underbrace{\frac{3}{256}}_{\frac{3}{4}\cdot\frac{1}{64}}\
\ldots
&
0\ 0\ \ldots\ 0
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..64 &
\mbox{positions}\ 65..128
\end{array}
\end{equation}
Next mix $C$ is pre-determined by network topology, and the distribution
it produces on its messages is the same as~(\ref{eq:cascfirst}).
Combining two distributions, we obtain that $m$ appears in the cascade's
output buffer with following probabilities:
\begin{equation}
\label{eq:cascsecond}
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
\underbrace{\frac{5056}{65536}}_{
\frac{67}{256}\cdot\frac{67}{256} +
\frac{3}{256}\cdot(63\cdot\frac{3}{256})}
&
\underbrace{\frac{960}{65536}}_{
\frac{67}{256}\cdot\frac{3}{256} +
\frac{3}{256}\cdot(\frac{67}{256}+62\cdot\frac{3}{256})}\
\ldots
&
0\ 0\ \ldots\ 0
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..64 &
\mbox{positions}\ 65..128
\end{array}
\end{equation}
Entropy of this distribution is approximately $5.9082$. Effective
anonymity set provided by a 2x2 cascade with 25\% density of hostile
nodes and 128 messages per batch is 60 messages.
\subsection{Stratified array.}
The procedure for calculating mixing distribution for a stratified array
is essentially the same as for a cascade, but there is an additional
probabilistic choice. After the message passes through a mix, the next
mix is selected randomly among all mixes in the next layer.
Consider a 2x2 stratified array as in fig.~\ref{fig:sa-2x2}. Again,
assume there are 128 messages in a batch, $\frac{1}{4}$ chance that
a node is hostile, and that $A$ was selected (in a manner visible
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:
\[
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
\underbrace{\frac{2528}{65536}}_{
\frac{1}{2}\cdot\frac{5056}{65536}}
&
\underbrace{\frac{480}{65536}}_{
\frac{1}{2}\cdot\frac{960}{65536}}\
\ldots
&
\underbrace{\frac{1}{128}}_{
\frac{1}{2}\cdot\frac{1}{64}}\
\ldots
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..64 &
\mbox{positions}\ 65..128
\end{array}
\]
Entropy of this distribution is approximately $6.9541$. Effective
anonymity set provided by a 2x2 stratified array with 25\% density of
hostile nodes and 128 messages per batch is 124 messages.
\subsection{Free-route network.}
Probability distribution is computed in exactly the same way for a
free-route network as for a stratified array, except that the entire set
of mixes is treated as a layer. Consider a 4x2 free-route network as in
fig.~\ref{free-4x2}. With 128 messages per batch, the buffer for each
mix is 32 messages. If $A$ is the first mix selected (and is hostile
with probability $\frac{1}{4}$), the probability distribution after the
message passes through $A$ is
\[
\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
\underbrace{\frac{35}{128}}_{\frac{1}{4} \cdot 1 +
\frac{3}{4}\cdot\frac{1}{32}}
&
\underbrace{\frac{3}{128}}_{\frac{3}{4}\cdot\frac{1}{32}}\
\ldots
&
0\ 0\ \ldots\ 0
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..32 &
\mbox{positions}\ 33..128
\end{array}
\]
The next mix is selected from among all four mixes with equal probability,
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{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}))}\
\ldots
&
\underbrace{\frac{1}{128}}_{
\frac{1}{4}\cdot\frac{1}{32}}\
\ldots
\\
\mbox{position}\ 1 &
\mbox{positions}\ 2..32 &
\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.
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.26
retrieving revision 1.27
diff -u -d -r1.26 -r1.27
--- sync-batching.tex 23 Jan 2004 19:38:47 -0000 1.26
+++ sync-batching.tex 23 Jan 2004 19:57:26 -0000 1.27
@@ -861,5 +861,8 @@
\bibliographystyle{plain}
\bibliography{sync-batching}
+\appendix
+\input{model-app}
+
\end{document}
Index: model.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/model.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- model.tex 23 Jan 2004 18:55:37 -0000 1.1
+++ model.tex 23 Jan 2004 19:57:26 -0000 1.2
@@ -15,7 +15,7 @@
and use a fully automated probabilistic model checking techniques to
compute probability distributions for different network topologies and
configurations. We use \emph{entropy} of each topology's respective
-distribution as our comparison metric, in the spirit of~\cite{DS02}.
+distribution as our comparison metric, in the spirit of~\cite{Serj02}.
\subsection{Mixing as permutation}
@@ -49,7 +49,7 @@
In our basic model, we assume that the network doesn't lose messages
(this restriction is not critical and may be relaxed, if necessary).
Therefore, $\sum_{1 \leq i \leq N}\PP_i = 1$, and $\PP_i$ form a proper
-discrete probability distribution. Following~\cite{DS02}, we calculate
+discrete probability distribution. Following~\cite{Serj02}, we calculate
\emph{entropy} of this distribution as
\[
\EE = \sum_{1 \leq i \leq N} \PP_i \log_2(\PP_i)
@@ -165,164 +165,7 @@
determined only by batch size and network topology, and is independent
of the actual random distribution of a given batch through the network.
-
-\subsubsection{Cascade.}
-
-Consider a 2x2 cascade network as in fig.~\ref{fig:casc-2x2}. Assume
-there are 128 messages in a batch, and that any node has $\frac{1}{4}$
-chance of having been compromised. Let $m$ be the targeted message,
-and suppose the adversary observed that the sender of $m$ chose $A$
-as the first mix. Under the equal loading assumption, there are 63
-other messages in addition to $m$ that chose $A$ as the first mix.
-Without loss of generality, we may assume that $m$ occupies the first
-position in $A$'s input buffer of length 64.
-
-With probability $\frac{1}{4}$, mix $A$ is hostile. In this case,
-$m$ remains in the first position after passing through the mix.
-With probability $\frac{3}{4}$, mix $A$ is honest. In this case, $m$
-appears in any of the 64 output positions of this mix with probability
-$\frac{1}{64}$ (note that $m$ may not appear in the output buffer of
-mix $B$). The resulting probability distribution for $m$'s position
-after passing through $A$ is
-\begin{equation}
-\label{eq:cascfirst}
-\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
-\underbrace{\frac{67}{256}}_{\frac{1}{4} \cdot 1 +
- \frac{3}{4}\cdot\frac{1}{64}}
-&
-\underbrace{\frac{3}{256}}_{\frac{3}{4}\cdot\frac{1}{64}}\
-\ldots
-&
-0\ 0\ \ldots\ 0
-\\
-\mbox{position}\ 1 &
-\mbox{positions}\ 2..64 &
-\mbox{positions}\ 65..128
-\end{array}
-\end{equation}
-
-Next mix $C$ is pre-determined by network topology, and the distribution
-it produces on its messages is the same as~(\ref{eq:cascfirst}).
-Combining two distributions, we obtain that $m$ appears in the cascade's
-output buffer with following probabilities:
-\begin{equation}
-\label{eq:cascsecond}
-\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
-\underbrace{\frac{5056}{65536}}_{
- \frac{67}{256}\cdot\frac{67}{256} +
- \frac{3}{256}\cdot(63\cdot\frac{3}{256})}
-&
-\underbrace{\frac{960}{65536}}_{
- \frac{67}{256}\cdot\frac{3}{256} +
- \frac{3}{256}\cdot(\frac{67}{256}+62\cdot\frac{3}{256})}\
-\ldots
-&
-0\ 0\ \ldots\ 0
-\\
-\mbox{position}\ 1 &
-\mbox{positions}\ 2..64 &
-\mbox{positions}\ 65..128
-\end{array}
-\end{equation}
-
-Entropy of this distribution is approximately $5.9082$. Effective
-anonymity set provided by a 2x2 cascade with 25\% density of hostile
-nodes and 128 messages per batch is 60 messages.
-
-
-\subsubsection{Stratified array.}
-
-The procedure for calculating mixing distribution for a stratified array
-is essentially the same as for a cascade, but there is an additional
-probabilistic choice. After the message passes through a mix, the next
-mix is selected randomly among all mixes in the next layer.
-
-Consider a 2x2 stratified array as in fig.~\ref{fig:sa-2x2}. Again,
-assume there are 128 messages in a batch, $\frac{1}{4}$ chance that
-a node is hostile, and that $A$ was selected (in a manner visible
-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:
-\[
-\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
-\underbrace{\frac{2528}{65536}}_{
- \frac{1}{2}\cdot\frac{5056}{65536}}
-&
-\underbrace{\frac{480}{65536}}_{
- \frac{1}{2}\cdot\frac{960}{65536}}\
-\ldots
-&
-\underbrace{\frac{1}{128}}_{
- \frac{1}{2}\cdot\frac{1}{64}}\
-\ldots
-\\
-\mbox{position}\ 1 &
-\mbox{positions}\ 2..64 &
-\mbox{positions}\ 65..128
-\end{array}
-\]
-
-Entropy of this distribution is approximately $6.9541$. Effective
-anonymity set provided by a 2x2 stratified array with 25\% density of
-hostile nodes and 128 messages per batch is 124 messages.
-
-
-\subsubsection{Free-route network.}
-
-Probability distribution is computed in exactly the same way for a
-free-route network as for a stratified array, except that the entire set
-of mixes is treated as a layer. Consider a 4x2 free-route network as in
-fig.~\ref{free-4x2}. With 128 messages per batch, the buffer for each
-mix is 32 messages. If $A$ is the first mix selected (and is hostile
-with probability $\frac{1}{4}$), the probability distribution after the
-message passes through $A$ is
-\[
-\begin{array}{c@{\hspace{1em}}c@{\hspace{1em}}c}
-\underbrace{\frac{35}{128}}_{\frac{1}{4} \cdot 1 +
- \frac{3}{4}\cdot\frac{1}{32}}
-&
-\underbrace{\frac{3}{128}}_{\frac{3}{4}\cdot\frac{1}{32}}\
-\ldots
-&
-0\ 0\ \ldots\ 0
-\\
-\mbox{position}\ 1 &
-\mbox{positions}\ 2..32 &
-\mbox{positions}\ 33..128
-\end{array}
-\]
-
-The next mix is selected from among all four mixes with equal probability,
-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{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}))}\
-\ldots
-&
-\underbrace{\frac{1}{128}}_{
- \frac{1}{4}\cdot\frac{1}{32}}\
-\ldots
-\\
-\mbox{position}\ 1 &
-\mbox{positions}\ 2..32 &
-\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.
+Appendix \ref{sec:walk-through} provides a walk-through of calculating
+entropy for each topology, to help build intuition about our assumptions
+and results.
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/