[freehaven-cvs] Adding Claudia"s first draft.

[rabbi@seul.org]

Update of /home2/freehaven/cvsroot/doc/mixmaster-vs-reliable
In directory moria.mit.edu:/tmp/cvs-serv31220

Added Files:
	mixvreliable.tex 
Log Message:
Adding Claudia's first draft.


--- NEW FILE: mixvreliable.tex ---
\documentclass{article}
\usepackage{usenix}
\usepackage{amsmath, amssymb}
\usepackage{epsfig}
\usepackage{latexsym}
\usepackage{psfrag}
\usepackage{amsfonts}

\title{Comparison between two practical mix designs}  

\author{Claudia D\'{\i}az \and Len Sassaman \and Evelyne Dewitte}

\bibliographystyle{alpha}

\date{}

\begin{document}

\maketitle

\begin{abstract}


\end{abstract}


\section{Introduction}


The Internet was initially perceived as a rather anonymous
environment. Nowadays, we know that it is a powerful surveillance tool:
anyone willing to listen to the communication links can spy
on you, and search engines and data mining techniques are becoming
increasingly powerful.  
Privacy does not only mean confidentiality of the information;
it also means not revealing information about who is communicating
with whom. Anonymous remailers (also called \emph{mixes}) allow us to
send emails without disclosing the identity of the recipient to a
third party. They also allow the sender of a message to stay anonymous 
towards the recipient. 

The objective of this work was to have quantitative results on the
anonymity actually provided by two practical mixes, in order to test
the actual anonymity provided to the users of the remailer sevice, and
to compare the two different designs. We have used as input real-life
data, and simulated the behaviour of the mix.

% Summary of what we have done

% Roadmap of the paper

\section{Mixes}
\label{mixes}

Mixes are the essential building block to provide anonymous email
services. A mix is a router that hides the correspondence between
incoming and outgoing messages. The mix changes the appearance and the
flow of the messages. In order to change the appearance of the
messages, the mix uses some techniques, such as padding and
encryption, thus providing bitwise unlinkability between inputs and
outputs. Techniques like reordering and delaying messages, and
generating dummy traffic are used to modify the flow of messages. This
modification of the traffic flow is needed to prevent timing
attacks that could disclose the relationship between an input and an
output messages by looking at the time the message arrived to and left
from the mix.

The idea of mixes was introduced by Chaum \cite{chaum81untraceable}.  
This first design was a \emph{threshold mix}, a mix that
collects a certain number of messages and then flushes them. Since
then, variants on this first design have been proposed in the
literature. In this paper, we focus on two practical mix designs,
which have been implemented and are part of the Mixmaster remailer
network [ref. to Mixmaster], that has been providing anonymous email
services since xxx. 

The first design is called ``Mixmaster'' (as the remailer network)
because it corresponds to the original design by Cottrell
\cite{Cott94,Mix_prot}. The second desing, called ``Reliable'', uses a
different reordering strategy. The details of the two remailers are
explained in the following sections.


\subsection{Mixmaster}



\subsection{Reliable}


\section{Dummy traffic}
\label{dummy}

\subsection{Dummy policy of Mixmaster}

\subsection{Dummy policy of Reliable}


\section{Anonymity metrics}
\label{metrics}

In this section we introduce the anonymity metrics for mixes. We
remark the particularities of some mix designs (binomial mixes and
threshold mixes). Also, we present the attack model considered.

\emph{Anonymity} was defined by Pfitzmann and K\"ohntopp
\cite{Pfitzmann00} as \emph{``the state of being not identifiable within a
  set of subjects, the anonymity set''}.

The use of the information theoretical concept of entropy as a metric for
anonymity was simultaneously proposed by Serjantov and Danezis in 
\cite{Serj02} and by D\'{\i}az \emph{et al.} in \cite{Diaz02}. The
difference between the two models for measuring anonymity is that in
\cite{Diaz02} the entropy is normalized with respect to the number of
users. In this paper we will use the non-normalized flavour of the metric.

The anonymity provided by a mix can be computed for the incoming 
or for the outgoing messages. We call this \emph{sender anonymity}
and \emph{recipient anonymity}. 

\paragraph{Sender anonymity.}
In order to compute the sender anonymity, we want to know the effective
size of the anonymity set of senders for a message output by the mix. 
Therefore, we compute the entropy of the probability distribution that
relates an outgoing message of the mix (the one for which we want to know
the anonymity set size) with all the possible inputs. 

\paragraph{Recipient anonymity.}
If we want to compute the effective
recipient anonymity set size of an incoming message that goes through
the mix, we have to compute the entropy of the probability
distribution that relates the chosen input with all possible outputs.
\\

Note that in the two cases, the metric computes the anonymity of a
\emph{particular} input or output message; it does not give a general
value for a mix design and it is dependent on the traffic pattern. The
advantage of this property is that mixes may offer information about
the \emph{current} anonymity they are providing. The disadvantage is
that it becomes very difficult to compare theoretically different mix
designs. Nevertheless, it is possible to measure on real systems (or
simulate) the anonymity obtained for a large number of messages and
provide comparative statistics.


\subsection{Attack model}


The anonymity metric computes the uncertainty about the sender or the
recipient of a message, given that some information is
available. We compute the metric from the point of view of an
attacker, whose powers must be clearly specified.


\section{Simulators}


\section{Results of the simulations}


\section{Conclusions and future work}
\label{conclusions}


\subsection*{Acknowledgments}

Claudia D\'{\i}az is funded by a research grant of the K.U.Leuven.  
This work was also partially supported by the IWT STWW project on
Anonymity and Privacy in Electronic Services (APES), and by the
Concerted Research Action (GOA) Mefisto-2000/06 of the Flemish
Government. 

The authors also want to thank Jasper Scholten for looking at the
feasibility of some algorithms.



\bibliography{Bib}


\end{document}

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