[freehaven-cvs] Revise optimization section

[nickm@seul.org (Nick Mathewson)]

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

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

Index: pynchon.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/pynchon-gate/pynchon.tex,v
retrieving revision 1.45
retrieving revision 1.46
diff -u -d -r1.45 -r1.46
--- pynchon.tex	18 Sep 2004 00:01:06 -0000	1.45
+++ pynchon.tex	18 Sep 2004 00:30:58 -0000	1.46
@@ -1,10 +1,10 @@
 \documentclass[runningheads]{llncs}
 %
 % TODO:
-%   - Revise design section, make it correct. (NM, LS)
-%   - Add figures for design. (LS, mockups from NM?)
-%   - Add performance section. (NM)
-%   - Compute and add results for statistical disclosure section. (NM)
+%   o Revise design section, make it correct. (NM, LS)
+%   o Add figures for design. (LS, mockups from NM?)
+%   o Add performance section. (NM)
+%   o Compute and add results for statistical disclosure section. (NM)
 %   - Write conclusion. (LS)
 %   - Finish "known attacks" section. (LS)
 %
@@ -712,54 +712,52 @@
 other of these values is large enough to cause scaling problems, then the
 collator can trade off bucket size for bit field size by doubling the
 bucket size, which halves the bit field size. With this approach, if the
-number of buckets becomes very large, then the message size will rise
+number of buckets becomes very large, then the message size rises
 proportionately to the square root of the number of buckets. This scales
 well, although it may necessitate multiple collators if the number of
-buckets gets extremely large. As the collator presents a single target
-point in a legal attack~\cite{nym-alias-net,wagner} or denial of
-service scenario, it would be a good practice for multiple collators to
-exist.\footnote{Note that while different collators may share the same
-distribution nodes for architecture or resource reasons, the anonymity
-sets would remain separate.}
+buckets gets extremely large.
+%As the collator presents a single target
+%point in a legal attack~\cite{nym-alias-net,wagner} or denial of
+%service scenario, it would be a good practice for multiple collators to
+%exist.
+% XXXX Maybe fold the above point into the attacks section.
+(Note that while different collators may share the same
+distribution nodes for architecture or resource reasons, their anonymity
+sets would remain separate.)
 
-The private information retrieval algorithm suggested in this paper does
-not have optimal asymptotic performance. In particular, it uses more
-bandwidth than necessary. We present this particular algorithm because it
+The PIR algorithm suggested in this paper does
+not have optimal asymptotic performance, especially in terms of bandwidth.
+We present it nonetheless because it
 is easy to explain, implement, and analyze, and offers sufficient
 scalability to be useful. A reasonable engineering plan is to implement
 the algorithm that we describe, then once the implementation reaches a
 level of scaling high enough to warrant the much greater difficulty of a
-more sophisticated algorithm, build a follow-on protocol which uses fewer
-resources. Waiting to do that is prudent from a security standpoint, since
-the potential effectiveness of attacks in which a distributor sends back
-garbled data to see if the client accepts it is unclear. Also, private
+more sophisticated algorithm, implement a follow-on protocol which uses fewer
+resources. This delay is prudent, since
+% from a security standpoint, since
+%the potential effectiveness of attacks in which a distributor sends back
+%garbled data to see if the client accepts it is unclear. Also,
+private
 information retrieval primitives are an area of active research with
-ongoing improvements taking place~\cite{beimel-barrier}, so waiting to
+ongoing improvements~\cite{beimel-barrier}, so waiting to
 implement a more sophisticated algorithm will likely result in greater
-resource savings once the implementation occurs.\footnote {Modifications
-to the protocol which break compatibility with existing clients should be
-made cautiously, however, to avoid unnecessary fragmentation of the
-existing anonymity set.}
-
-Distributors have to perform a linear scan of their entire database in
-order to fulfill a request in this protocol. However, they can compute the
-results of many requests in parallel with a single linear pass through the
-database. Thus, distributors can fulfill a huge number of requests, but
-the latency to answer those requests is limited by the total size of all
-buckets put together, with the limiting factor on that being the
-distributor's hard drive throughput.
+resource savings once the implementation occurs.%\footnote{Modifications
+%to the protocol which break compatibility with existing clients should be
+%made cautiously, however, to avoid unnecessary fragmentation of the
+%existing anonymity set.}
 
-An optimization can be made to minimize distributor response latency. By
+Another potential bottleneck lies in the fact that
+distributors have to perform a linear scan of the entire bucket pool in
+order to fulfill a request. However, they can use a single linear pass to
+compute the results of many requests in parallel.
+Thus, a distributor can fulfill a large number of requests at once, though
+the latency to answer those requests is limited by the total size of the
+bucket pool, and the throughput to the distributor's hard drive.  Also, bu
 performing continuous linear scans of the entire database, the distributor
 can begin computing the result of a request at any point during the scan,
-finishing when the next scan returns to that same point. Thus the latency
+finishing when the next scan returns to that same point. Thus, the latency
 is exactly the time of one full scan.
 
-Back et al. discuss similar performance vs. anonymity trade-off issues for
-low-latency anonymity systems, and also conclude that deployability over
-existing network infrastructure with attainable resources must be a design
-consideration for serious anonymity solutions~\cite{back01}.
-
 \subsection{Comparing Pynchon Gate to other systems}
 %XXXX write this.  Describe the other systems:
 %  Type I nymservers, aam, underhill, underhill with full padding,
@@ -805,8 +803,6 @@
 PIR stream seed size is $SS$, and $K$ is the number of distributors chosen
 from which to retrieve data.
 
-% XXXX This table is badly formatted, and doesn't fit on the page, but at
-% least all the math is in it.  Can a latex-ist fix?
 \noindent
 \begin{figure}
 \begin{center}

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