[freehaven-cvs] Revise PIR section

[nickm@seul.org (Nick Mathewson)]

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

Modified Files:
	pynchon.tex 
Log Message:
Revise PIR section

Index: pynchon.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/pynchon-gate/pynchon.tex,v
retrieving revision 1.42
retrieving revision 1.43
diff -u -d -r1.42 -r1.43
--- pynchon.tex	17 Sep 2004 23:10:41 -0000	1.42
+++ pynchon.tex	17 Sep 2004 23:18:05 -0000	1.43
@@ -444,12 +444,12 @@
 
 \begin{figure}
 \begin{center}
-\includegraphics[width=10cm, height=7cm]{figs/PynFig1.pdf}
-
+\includegraphics[width=10cm, height=7cm]{figs/PynFig1}
 \caption{The Pynchon Gate Architecture}
 \label{pyn-arch}
 \end{center}
 \end{figure}
+%XXXX Reference this figure!
 
 \subsection{The Nym Server}
 
@@ -558,7 +558,6 @@
 messages that are delivered out of order, or in different cycles.
 
 \subsection{Distributors and clients}
-\label{subsec:client-design}
 Once the collator is done, it relays the signed meta-index, and the entire
 bucket pool, to a set of
 independently operated \emph{distributor nodes}. (This data should be
@@ -580,53 +579,61 @@
 cycle than her maximum, she performs extra PIR operations up to that maximum,
 to prevent an observer from learning how many messages she has received.
 
+Depending on the length of the cycle, clients may not be able to download
+messages every cycle.  Therefore, distributors must retain meta-indexes and
+bucket pools for a reasonable window of time, to be sure that all clients
+have time to download their messages.
+
 \subsubsection{The Pynchon Gate PIR Protocol}
 \label{subsec:protocol-design}
-The \emph{Pynchon Gate Client} application resides on the nym owner's
-local computer, and periodically retrieves messages from the distributor
-nodes using the Pynchon Gate PIR Protocol.
+The Pynchon Gate distributed-trust PIR protocol allows a client to retrieve a
+bucket from $k$ chosen distributors, so that an attacker cannot tell which
+bucket the client is retrieving without compromising or controlling all $k$
+of the servers.
 
-The Pynchon Gate PIR Protocol is as follows: The client application
-sends a random-looking bit field to the distributor. This bit field has a
-length equal to the number of buckets. The distributor performs a linear
-scan across all buckets, and XORs the buckets whose positions have a
-corresponding 1 in the bit field. The result of this XOR is then returned
-to the client.\footnote{As an optimization, a client may send a seed to a
-stream cipher instead of the full bit field. The distributor will use the
-stream cipher as a pseudo-random number generator to generate the full bit
-field. This reduces the size of the request from linear on the number of
-buckets to fixed~\cite{prng-back}.}
+The protocol runs as follows: after choosing distributors, the client
+establishes an encrypted to each
+(say, using TLS).  These connections must be unidirectionally authenticated
+to prevent man-in-the-middle attacks, and can be made sequentially, or in
+parallel.
 
-For a single distributor chosen at random, the client takes the XOR of all
-of the other bit fields that it sent\footnote{Stream cipher output
-generated by the seeds it sent could also be used.} and flips a single bit
-corresponding to the bucket to be retrieved.\footnote{The bandwidth
-conservation optimization does not apply at this step.}
+The client the client sends a different ``random-looking'' bit vector
+$v_{sb}$ to each distributor $s$, for each bucket $b$ to be retrieved.  Each
+bit vector has a length equal to the number of buckets in the pool.  In
+response, each distributor $s$ performs a linear scan across all buckets, and
+computes $R(v_{sb})$ as the XOR of all buckets whose positions is set to $1$
+in $v_{sb}$.  The resulting value is then returned to the client.
 
-The client XORs the results returned by all the distributors and verifies
-that the path to the hash root appended by the distributors is correct. At
-this point, the client has received the bucket that it requested. This
-process is repeated until the hash tree is traversed to a leaf node, which
-will contain the desired message or messages.
+Thus, in order to retrieve the $b$'th bucket, the client need only to choose
+the values of $v_{sb}$ so that their exclusive OR is 0 at every position
+except $b$.  (For security, $k-1$ of the vectors should be generated
+randomly.) When the client receives the corresponding $R(v_{sb})$ values, she
+can XOR them to compute the bucket's contents.
 
-To prevent man-in-the-middle attacks, TLS is used as the protocol's
-transport layer~\cite{rfc-2246}. Users negotiate a TLS connection with a
-given distributor, and then relay PIR messages as described. The
-connection is authenticated using a certificate in a two-level certificate
-chain. The top-level certificate is a self-signed long-term certificate
-for the distributor. The second-level certificate is used to authenticate
-the distributor and establish the TLS session for the PIR protocol, and
-should be rotated regularly to provide forward secrecy.
+As an optimization, a client may send $k-1$ of the distributors a key for a
+stream cipher instead of a full bit vector. The distributors can use the
+stream in place of the vector.  This reduces the size of the request from
+linear on the number of buckets to fixed~\cite{prng-back}.  One distributor,
+however, will still need to receive a full vector.
 
-In order to protect against usage pattern attacks, the size of the
-response to all message requests for an individual client must be a fixed
-size. If the number of messages contained in the system is too great to
-return in this normalized manner, a notation must be included in the data
-from the collator indicating that there are further messages waiting as
-well as the size of the pending data to be delivered. The client may then
-send administrative requests via an anonymous email message to the
-collator indicating whether the pending messages should be delivered or
-discarded.
+%To prevent man-in-the-middle attacks, TLS is used as the protocol's
+%transport layer~\cite{rfc-2246}. Users negotiate a TLS connection with a
+%given distributor, and then relay PIR messages as described. The
+%connection is authenticated using a certificate in a two-level certificate
+%chain. The top-level certificate is a self-signed long-term certificate
+%for the distributor. The second-level certificate is used to authenticate
+%the distributor and establish the TLS session for the PIR protocol, and
+%should be rotated regularly to provide forward secrecy.
+
+%In order to protect against usage pattern attacks, the size of the
+%response to all message requests for an individual client must be a fixed
+%size. If the number of messages contained in the system is too great to
+%return in this normalized manner, a notation must be included in the data
+%from the collator indicating that there are further messages waiting as
+%well as the size of the pending data to be delivered. The client may then
+%send administrative requests via an anonymous email message to the
+%collator indicating whether the pending messages should be delivered or
+%discarded.
 
 %\footnote{This ``INBOX management'' protocol is similar to one
 %which has been proposed as the basis for the Mixminion nym

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