[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] put graphs side by side, add back in previous edits
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
Log Message:
put graphs side by side, add back in previous edits
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.32
retrieving revision 1.33
diff -u -d -r1.32 -r1.33
--- sync-batching.tex 23 Jan 2004 23:33:44 -0000 1.32
+++ sync-batching.tex 23 Jan 2004 23:49:09 -0000 1.33
@@ -434,34 +434,64 @@
* compare the entropy between 16 nodes: cascade, SA, and free-route
-\begin{figure}[ht]
-\centering
-\mbox{\epsfig{angle=270,figure=badnodes,width=4in}}
-\caption{Entropy vs chance of bad node, for four topologies (16 nodes)}
-\label{fig:badnodes}
-\end{figure}
+%\begin{figure}[ht]
+%\centering
+%\mbox{\epsfig{angle=270,figure=badnodes,width=4in}}
+%\caption{Entropy vs chance of bad node, for three topologies (16 nodes)}
+%\label{fig:badnodes}
+%\end{figure}
-\begin{figure}[ht]
-\centering
-\mbox{\epsfig{angle=270,figure=caschops,width=4in}}
+\begin{figure}
+\begin{minipage}[ht]{6cm}
+\mbox{\epsfig{angle=270,figure=badnodes,width=6cm}}
+\caption{Entropy vs chance of bad node, three topologies (16 nodes)}
+\label{fig:badnodes}
+\end{minipage}
+\hfill
+\begin{minipage}[ht]{6cm}
+\mbox{\epsfig{angle=270,figure=caschops,width=6cm}}
\caption{Entropy vs number of hops, for cascade network (16 nodes)}
\label{fig:caschops}
+\end{minipage}
+\hfill
\end{figure}
-\begin{figure}[ht]
-\centering
-\mbox{\epsfig{angle=270,figure=systhops,width=4in}}
+\begin{figure}
+\begin{minipage}[ht]{6cm}
+\mbox{\epsfig{angle=270,figure=systhops,width=6cm}}
\caption{Entropy vs number of hops, for stratified network (16 nodes)}
\label{fig:systhops}
-\end{figure}
-
-\begin{figure}[ht]
-\centering
-\mbox{\epsfig{angle=270,figure=freehops,width=4in}}
+\end{minipage}
+\hfill
+\begin{minipage}[ht]{6cm}
+\mbox{\epsfig{angle=270,figure=freehops,width=6cm}}
\caption{Entropy vs number of hops, for free-route network (16 nodes)}
\label{fig:freehops}
+\end{minipage}
+\hfill
\end{figure}
+%\begin{figure}[ht]
+%\centering
+%\mbox{\epsfig{angle=270,figure=caschops,width=4in}}
+%\caption{Entropy vs number of hops, for cascade network (16 nodes)}
+%\label{fig:caschops}
+%\end{figure}
+
+%\begin{figure}[ht]
+%\centering
+%\mbox{\epsfig{angle=270,figure=systhops,width=4in}}
+%\caption{Entropy vs number of hops, for stratified network (16 nodes)}
+%\label{fig:systhops}
+%\end{figure}
+
+%\begin{figure}[ht]
+%\centering
+%\mbox{\epsfig{angle=270,figure=freehops,width=4in}}
+%\caption{Entropy vs number of hops, for free-route network (16 nodes)}
+%\label{fig:freehops}
+%\end{figure}
+
\clearpage
\section{Other considerations in the analysis}
@@ -528,6 +558,26 @@
% reduce entropy in scenarios with low adversary density, because he
% knows she doesn't exit from her entry node. Hm. -RD
+\subsection{Reputations and Node Preferences}
+
+Most deployed systems let users choose a preferred entry or exit hop,
+e.g.~based on trust. A skewed distribution of messages only at the entry
+or exit of the network should not impact entropy too much---we see from
+Figures \ref{fig:caschops}-\ref{fig:freehops} that much of each network's
+entropy is achieved after just a few hops.
+
+Reputation systems, on the other hand, encourage users to preferentially
+choose nodes \emph{throughout} the network. Further, reputation
+information can be exploited by an adversary to reduce anonymity,
+for example by predicting the user's behavior based on reputation
+statistics, or by attracting more traffic by building a strong reputation
+or degrading the reputation of others. One approach to working within
+these constraints would be to put like-reputationed nodes in the same
+layer of the stratified network, or in the same row of the cascade
+network \cite{casc-rep}, so reputation distribution (at each hop or
+in each cascade, respectively) will be more uniform. We leave this
+investigation to future work.
+
\subsection{Average Entropy vs Actual Entropy}
\label{subsec:average-actual}
@@ -566,6 +616,8 @@
we change our metric to require at least 2 messages on each link for
$m=128$, then we find that only 1\% of the cases fall outside this value.
+XXXplus think about chance for all layers not just one.
+
Danezis also considers this issue of variance from average entropy for his
mixnet design based on sparse expander graphs~\cite{danezis:pet2003}. He
argues that having at least one message on each link is sufficient for
@@ -862,36 +914,29 @@
late message still arrives. in this system, a late message is lost.
this is not very convenient for the user.
-\section{Extensions and Future Work}
-\label{sec:conclusion}
-
-In practice, several considerations have to be balanced when choosing
-a batching strategy and network structure. These include maximizing
-anonymity sets (both batch sizes through each node and the overall
-anonymity sets of users); bandwidth considerations; reliability;
-enabling users to choose nodes that they trust; and interactions with
-the reputation system.
+\section{Comparison with Asynchronous Batching Designs}
-Further analysis of the trade-offs will be needed before choosing a
-final network structure. Note that a planned structure, where each
-users' software follows the plan consistently when constructing
-routes, will generally be able to achieve stronger and more easily
-analysed security properties than less constrained approaches.
+The next step is to begin comparing synchronous free-routes with the
+more traditional asynchronous free-routes, with the goal of presenting
+a plausible design for a realistic protocol that could provide more
+security than Mixminion. Synchronous batching does away with the need
+for a replay cache (each message is labelled with its batch), removes
+partitioning attacks from key rotation, and generally provides clearer
+anonymity guarantees. On the other hand, our design is less robust to
+transient failures (dropped messages are bad for usability), and because
+the pool batching strategy spreads out the probability distributions,
+our design may fall more quickly to long-term statistical disclosure
+attacks~\cite{statistical-disclosure}.
-Comparison to Mixminion: No need for a replay cache. But less robust to
-transient failures.
+\section{Summary}
+\label{sec:conclusion}
-Reputations and node preference
-Most deployed systems let users choose their preferred entry or exit
-hops, e.g.~based on trust. which will mess with our distribution. but
-this is ok because after just a few hops of mixing, the distribution of
-the incoming batch doesn't matter as much anymore.
-Reputation systems \`{a} la mix-acc and casc-rep make people prefer one node
-over another, \emph{throughout} the mix network, not just at entries or
-exits. but we have to tolerate this sort of thing. one approach would
-be to put like-reputationed nodes in the same column of the SA or in
-the same row of the cascade \cite{casc-rep}, so distribution (at each
-hop or in each cascade, respectively) will be more uniform.
+Previously, only cascade networks were considered secure against very
+powerful adversaries~\cite{disad-free-routes}. In this paper we show that
+other topologies can use the synchronous batching strategy to achieve
+similar protection. Further, we show that free-route topologies with
+synchronous batching compare favorably to cascade networks. We invite
+further analysis of the trade-offs between each topology.
\section*{Acknowledgements}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/