[freehaven-cvs] Rewrite abstract and intro

[nickm@seul.org (Nick Mathewson)]

Update of /home/freehaven/cvsroot/doc/pynchon-gate
In directory moria.mit.edu:/tmp/cvs-serv21702

Modified Files:
	pynchon.tex pynchon.bib 
Log Message:
Rewrite abstract and intro

Index: pynchon.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/pynchon-gate/pynchon.tex,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- pynchon.tex	7 Sep 2004 23:16:46 -0000	1.16
+++ pynchon.tex	15 Sep 2004 19:30:34 -0000	1.17
@@ -13,7 +13,7 @@
 \title{The Pynchon Gate}
 \subtitle{A Secure Method of Pseudonymous Mail Retrieval}
 
-\author{Len Sassaman\inst{1} \and Bram Cohen\inst{2} \and Nick Mathewson\inst{3}} 
+\author{Len Sassaman\inst{1} \and Bram Cohen\inst{2} \and Nick Mathewson\inst{3}}
 
 \institute{K. U. Leuven ESAT-COSIC \\
 Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium
@@ -31,55 +31,92 @@
 \maketitle
 
 \begin{abstract}
-
-We present The Pynchon Gate, a pseudonymous message retrieval system. The
-Pynchon Gate is based upon Private Information Retrieval, an information
-theory primitive that enables us to address many of the known problems
-with existing pseudonymous communication systems. We propose a system
-where the user retrieves a subset of the collection of all messages in
-such a way that the user leaks no information about which messages he is
-retrieving, and a global observer is unable to correlate sender behavior
-with recipient usage patterns. We introduce a more stable architecture for
-pseudonymous mail systems and analyze its strengths and weaknesses as
-compared to existing systems. We discuss security concerns raised by this
-new model for pseudonymity, and propose solutions. We describe the
-architecture in a form sufficient for implementation, including
-countermeasures to basic attacks against the system.
-
+We present the Pynchon Gate, a practical pseudonymous message retrieval
+system.  Our design uses a simple distributed-trust Private Information
+Retrieval protocol to prevent adversaries from linking recipients to their
+pseudonyms, even when some of the infrastructure has been compromised.  The
+Pynchon Gate design resists global traffic analysis significantly better than
+existing deployed pseudonymous email solutions, at the cost of additional
+bandwidth costs---although unlike other high-bandwidth pseudonymity designs,
+the Pynchon Gate allows the costs to be distributed over many servers without
+compromising security.  We examine the security concerns raised by our model,
+and propose solutions.
+% We propose a system
+%where the user retrieves a subset of the collection of all messages in
+%such a way that the user leaks no information about which messages he is
+%retrieving, and a global observer is unable to correlate sender behavior
+%with recipient usage patterns. We introduce a more stable architecture for
+%pseudonymous mail systems and analyze its strengths and weaknesses as
+%compared to existing systems. We discuss security concerns raised by this
+%new model for pseudonymity, and propose solutions. We describe the
+%architecture in a form sufficient for implementation, including
+%countermeasures to basic attacks against the system.
 \end{abstract}
 
 \section{Introduction}
+Pseudonymous messaging services seek to provide users with a way to send
+messages that originate at a pseudonymous address (or ``nym'') unlinked to
+the user, and to receive messages send to that address, without allowing an
+attacker to deduce which users are associated with which pseudonyms.  But, as
+we will argue below, most existing deployed solutions are either vulnerable
+to traffic analysis, or require unacceptably large amounts of bandwidth and
+storage as the number of users and volume of traffic increase.
 
-We propose a novel way of using private information retrieval
-(PIR)~\cite{pir} primitives as the basis of a secure, fault-tolerant method
-of anonymous mail retrieval.
+We propose the Pynchon Gate, a novel design that uses distributed-trust
+private information retrieval (PIR)~\cite{pir} primitives to build a secure,
+fault-tolerant pseudonymous mail retrieval system.
 
-The system we propose consists of a number of components. The \emph{nym
-server} component interfaces with the email network: it delivers mail to
-external email addresses from authenticated nym owners, receives mail for
-nym accounts, and processes administrative \emph{control messages} related
-to individual nym accounts. Incoming email is passed from the nym server
-to the \emph{collator} component, which prepares message batches to be
-replicated to the \emph{distributor} components. The distributor
-components, through the use of the \emph{private information retrieval
-protocol}, allow nym owners to receive mail from the nym server while
+In our system, pseudonymous users (or ``nym holders'') use an existing
+anonymous email network (such as Mixmaster~\cite{mixmaster-spec} or
+Mixminion~\cite{mixminion}) to send authenticated requests to a {\it nym
+  server}, which delivers outgoing messages to the email network and handles
+administrative commands.  The nym server also receives incoming messages and
+passes them to a {\it collator} component, which encrypts the messages and
+periodically packages them into regular batches.  These batches are
+then replicated at a number of \emph{distributor} servers, which,
+through the use of the \emph{distributed-trust private information retrieval
+protocol}, allow nym owners to receive mail while
 maintaining unlinkability between a message and its recipient.
 
-\subsection{Goals}
+\subsubsection{Goals}
+First of all, our design must be {\it secure}: we want the Pynchon Gate to
+resist active and passive attacks at least as well as the state of the art
+for forward message anonymity.  Thus, we should protect users' identities
+from a global eavesdropper for as long as possible; should hinder active
+attackers who can delay, delete, or introduce traffic; and should resist an
+attacker who has compromised some (but not all) of the servers on the
+network.
 
-While sender-anonymity systems such as Mixmaster~\cite{mixmaster-spec}
-have been available for public use for nearly a decade, there remains a
-need for a secure, robust system that will allow users to receive mail
-anonymously. The system should be of equivalent or greater security than
-the state of the art for forward message anonymity; should gracefully
-handle node failure without loss of mail; should be resistant to attack
-from rogue nodes; and should not require a complicated interface or
-special knowledge in order to be effectively employed by the end user.
+In order to provide real security, however, we must ensure that the system is
+{\it deployable} and {\it usable}---since anonymity and pseudonymity systems
+hide users among each other, fewer users means less
+protection~\cite{econymics}.  This implies that we should gracefully handle
+node failure without loss of mail; that we must not require more bandwidth
+than volunteer servers are able to provide or users are willing to use; and
+that we hould not require a complicated interface or special knowledge from
+our users.
+
+\subsubsection{In this paper}
+We begin in section~\ref{sec:background} with a discussion of related work,
+and an overview of known attacks against existing pseudonymity systems.  (To
+motivate our work, subsection~\ref{subsec:disclosure} presents new analysis
+on the effectiveness of passive traffic analysis against current reply-block
+based nym servers.)  Section~\ref{sec:design} presents the Pynchon Gate in
+more detail, describing its organization, design rationales, and network
+formats.  We describe our simple distributed trust PIR protocol in
+subsection~\ref{subsec:client-design}.  In section~\label{sec:security} we
+analyze security, and in section~\ref{sec:performance} we discuss
+optimizations and compare our performance to that of other pseudonymous
+message systems.)  We close with an evaluation of our succcess in
+section~\ref{sec:conclusions}.
+
+\section{Background}
+\label{sec:background}
 
 \subsection{Related Work}
+\label{subsec:related-work}
 
 \subsubsection{Reply blocks and return addresses.}
-
 Chaum~\cite{chaum-mix} describes a method of using \emph{return addresses}
 with forward-secure mix-nets. However, the system relies upon all selected
 component nodes of the mix being operational in order for mail to be
@@ -107,7 +144,6 @@
 blocks, and contain replay-attack protection mechanisms~\cite{replay}.
 
 \subsubsection{Single-use reply blocks.}
-
 While the Type II system does not have any means of support for anonymous
 reply blocks, the Type III system introduces single-use reply blocks
 (SURBs)~\cite{surb} as a means of avoiding the replay attack issues. The
@@ -184,8 +220,7 @@
 encryption techniques used by re-encryption mixes, general concerns about
 implementation security of the ElGamal cryptosystem remain.}
 
-\subsubsection{Broadcast messages and dead-drops.} 
-
+\subsubsection{Broadcast messages and dead-drops.}
 Chaum discusses a traffic-analysis prevention method wherein all reply
 mail in the anonymous mail system is sent to all possible recipients. A
 more friendly optimization has already been attempted in the form of
@@ -210,14 +245,23 @@
 interest, and provides a way to attack the security of the
 system~\cite{harmful}.
 
+\subsection{Known attacks against}
+\label{subsec:known-attacks}
+%XXXX writeme
 
-\section{Design Rationale}
+\subsection{Statistical disclosure}
+\label{subsec:disclosure}
 
+\section{The Pynchon Gate Design}
+\label{sec:design}
+% XXXX write stuff here
+
+\section{Overview and Rationale}
 The Pynchon Gate is a network of servers that provide anonymous message
 retrieval capabilities. The servers receive messages for many different
-pseudonym accounts via email\footnote {The servers could also receive
+pseudonym accounts via email\footnote{The servers could also receive
 messages through any suitable medium for message transfer, such as
-``instant message'' systems~\cite {rfc-2779}. Note that there must exist a
+``instant message'' systems~\cite{rfc-2779}. Note that there must exist a
 suitable forward anonymity protocol to allow the nym holder to communicate
 with the nym server, so at a minimum the nym server must be able to
 receive email in addition to any optional support for other protocols.
@@ -328,6 +372,7 @@
 the \emph{Pynchon Gate PIR Protocol}.
 
 \subsection{The Pynchon Gate Client}
+\label{subsec:client-design}
 
 The \emph{Pynchon Gate Client} application resides on the nym owner's
 local computer, and periodically retrieves messages from the distributor
@@ -371,7 +416,7 @@
 %servers~\cite{imap-over-minion}.}
 
 \section{Security Concerns}
-
+\label{sec:security}
 As with any anonymity system, care must be taken at all steps to prevent
 possible attacks on the effective anonymity provided.
 
@@ -427,8 +472,8 @@
 information about the nym owner. This can be achieved by allowing the
 client to query the distributors only at regular intervals.
 
-\section{Scalability and Optimizations}
-
+\section{Performance, Scalability and Optimizations}
+\label{sec:performance}
 In this protocol, the size of requests is proportional to the total number
 of messages and the size of responses is the bucket size. If one or the
 other of these values is large enough to cause scaling problems, then the
@@ -483,6 +528,7 @@
 consideration for serious anonymity solutions~\cite{back01}.
 
 \section{A Note on Usability}
+%XXXX Merge into conclusion, where we evaluate our success.
 
 The most popular pseudonym system ever deployed was {\tt
 anon.penet.fi}~\cite{helsingius}. This system provided users with an easy,
@@ -512,6 +558,7 @@
 necessary component to the security of the system.
 
 \section{Conclusions}
+\label{sec:conclusions}
 
 We have presented a system for anonymous message retrieval which provides
 stronger anonymity assurance and greater robustness than any other

Index: pynchon.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/pynchon-gate/pynchon.bib,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- pynchon.bib	7 Sep 2004 21:30:50 -0000	1.10
+++ pynchon.bib	15 Sep 2004 19:30:35 -0000	1.11
@@ -428,3 +428,11 @@
    howpublished = {\url{http://www.penet.fi/press-english.html}},
 }
 
+@inproceedings{econymics,
+  title = {On the Economics of Anonymity}, 
+  author = {Alessandro Acquisti and Roger Dingledine and Paul Syverson}, 
+  booktitle = {Financial Cryptography}, 
+  year = {2003}, 
+  editor = {Rebecca N. Wright}, 
+  publisher = {Springer-Verlag, LNCS 2742}, 
+}

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