[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] r1781: Unblind Byzantine Postman paper. (doc/trunk/pynchon-gate)
Author: rabbi
Date: 2007-05-07 19:21:13 -0400 (Mon, 07 May 2007)
New Revision: 1781
Added:
doc/trunk/pynchon-gate/byzantine-fix.bib
doc/trunk/pynchon-gate/byzantine-fix.tex
Log:
Unblind Byzantine Postman paper.
Added: doc/trunk/pynchon-gate/byzantine-fix.bib
===================================================================
--- doc/trunk/pynchon-gate/byzantine-fix.bib 2007-04-24 12:47:49 UTC (rev 1780)
+++ doc/trunk/pynchon-gate/byzantine-fix.bib 2007-05-07 23:21:13 UTC (rev 1781)
@@ -0,0 +1,1014 @@
+@inproceedings{CPIR,
+ author = {Benny Chor and Niv Gilboa},
+ title = {Computationally private information retrieval (extended abstract)},
+ booktitle = {STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of Computing},
+ year = {1997},
+ isbn = {0-89791-888-6},
+ pages = {304--313},
+ location = {El Paso, Texas, United States},
+ doi = {http://doi.acm.org/10.1145/258533.258609},
+ publisher = {ACM Press},
+ address = {New York, NY, USA},
+ }
+
+@article{RSA,
+ author = {R. L. Rivest and A. Shamir and L. Adleman},
+ title = {A method for obtaining digital signatures and public-key cryptosystems},
+ journal = {Communications of the ACM},
+ volume = {21},
+ number = {2},
+ year = {1978},
+ issn = {0001-0782},
+ pages = {120--126},
+ doi = {http://doi.acm.org/10.1145/359340.359342},
+ publisher = {ACM Press},
+ address = {New York, NY, USA},
+ }
+
+@article{shamir-secret,
+ author = {A. Shamir},
+ title = {{How to Share a Secret}},
+ journal = {Communications of the ACM},
+ volume = {22},
+ number = {11},
+ year = {1979},
+ issn = {0001-0782},
+ pages = {612--613},
+ doi = {http://doi.acm.org/10.1145/359168.359176},
+ publisher = {ACM Press},
+ address = {New York, NY, USA},
+ }
+
+@article{tompa-woll,
+ author = {M. Tompa and H. Woll},
+ title = {{How to Share a Secret with Cheaters}},
+ journal = {Journal of Cryptology},
+ volume = {1},
+ number = {2},
+ year = {1988},
+ issn = {0933-2790},
+ pages = {133--138},
+ publisher = {Springer-Verlag New York, Inc.},
+ address = {Secaucus, NJ, USA},
+ }
+
+@article{diffie76new,
+ author = {Whitfield Diffie and Martin E. Hellman},
+ title = {New Directions in Cryptography},
+ journal = {IEEE Transactions on Information Theory},
+ volume = {IT-22},
+ number = {6},
+ pages = {644--654},
+ date = {November 1976},
+ year = {1976},
+ url = {citeseer.ist.psu.edu/diffie76new.html},
+}
+
+@Article{remailer-history,
+ author = {Sameer Parekh},
+ title = {Prospects for Remailers},
+ journal = {First Monday},
+ volume = {1},
+ number = {2},
+ month = {August},
+ year = {1996},
+ note = {\url{http://www.firstmonday.dk/issues/issue2/remailers/}},
+}
+
+@Article{Szabo97,
+ author = {Nick Szabo},
+ title = {Formalizing and securing relationships on public networks},
+ journal = {First Monday},
+ volume = {2},
+ number = {9},
+ month = {September},
+ year = {1997},
+ note = {\url{http://www.firstmonday.org/issues/issue2_9/szabo/index.html}},
+}
+
+@article{invasive,
+author = {George Lawton},
+title = {Invasive Software: Who's Inside Your Computer?},
+journal = {Computer},
+volume = {35},
+number = {7},
+year = {2002},
+issn = {0018-9162},
+pages = {15-18},
+doi = {http://doi.ieeecomputersociety.org/10.1109/MC.2002.1016895},
+publisher = {IEEE Computer Society},
+address = {Los Alamitos, CA, USA},
+}
+
+@article{kissner04private,
+ author = {L. Kissner and A. Oprea and M. Reiter and D. Song and K. Yang},
+ title = {Private keywordbased push and pull with applications to anonymous communication},
+ journal = {Applied Cryptography and Network Security},
+ year = {2004},
+ url = {citeseer.ist.psu.edu/kissner04private.html},
+ }
+
+@article{chaum-mix,
+ title = {Untraceable electronic mail, return addresses, and digital pseudonyms},
+ author = {David Chaum},
+ journal = {Communications of the ACM},
+ volume = {4},
+ number = {2},
+ year = {1981},
+ month = {February},
+ www_txt_url = {http://www.eskimo.com/~weidai/mix-net.txt},
+ www_pdf_url = {http://www.ovmj.org/GNUnet/papers/p84-chaum.pdf},
+ www_html_url = {http://world.std.com/~franl/crypto/chaum-acm-1981.html},
+ www_section = {Anonymous communication},
+}
+
+@article{wagner,
+ author = {Robyn Wagner},
+ title = {{Don't Shoot the Messenger: Limiting the Liability of Anonymous Remailer Operators}},
+ journal = {New Mexico Law Review},
+ volume = {32},
+ number = {Winter},
+ pages = {99--142},
+ year = {2002},
+}
+
+@article{elgamal,
+ title = {{A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms}},
+ author = {Taher ElGamal},
+ journal = {{IEEE} Transactions on Information Theory},
+ volume = {IT-31},
+ number = {4},
+ pages = {469--472},
+ year = {1985},
+}
+
+@article{jap-backdoor,
+ title = {Net anonymity service back-doored},
+ author = {Thomas C. Greene},
+ journal = {The Register},
+ year = {2003},
+ note = {\url{http://www.theregister.co.uk/2003/08/21/net_anonymity_service_backdoored/}},
+}
+
+@misc{jap-pr,
+ author = {Independent Centre for Privacy Protection},
+ title = {{AN.ON} still guarantees anonymity},
+ year = {2003},
+ howpublished = {\url{http://www.datenschutzzentrum.de/material/themen/presse/anonip_e.htm}},
+}
+
+@phdthesis{ian-thesis,
+ title = {A Pseudonymous Communications Infrastructure for the Internet},
+ author = {Ian Goldberg},
+ school = {UC Berkeley},
+ year = {2000},
+ month = {December},
+ www_pdf_url = {http://www.isaac.cs.berkeley.edu/~iang/thesis-final.pdf},
+ www_section = {Anonymous communication},
+}
+
+@phdthesis{gd-thesis,
+ title = {Better Anonymous Communications},
+ author = {George Danezis},
+ school = {University of Cambridge},
+ year = {2004},
+}
+
+@inproceedings{freehaven-berk,
+ title = {The {Free Haven Project}: Distributed Anonymous Storage Service},
+ author = {Roger Dingledine and Michael J. Freedman and David Molnar},
+ booktitle = {Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design
+ Issues in Anonymity and Unobservability},
+ year = {2000},
+ month = {July},
+ editor = {H. Federrath},
+ publisher = {Springer-Verlag, LNCS 2009},
+ www_important = {1},
+ www_ps_url = {http://freehaven.net/doc/berk/freehaven-berk.ps},
+ www_section = {Anonymous publication},
+}
+
+@inproceedings{universal,
+ title = {Universal Re-Encryption for Mixnets},
+ author = {Philippe Golle and Markus Jakobsson and Ari Juels and Paul Syverson},
+ booktitle = {Proceedings of the 2004 RSA Conference, Cryptographer's track},
+ year = {2004},
+ month = {February},
+ address = {San Francisco, CA, USA},
+ www_section = {Anonymous communication},
+ www_pdf_url = {http://www.syverson.org/univrenc-ctrsa.pdf},
+}
+
+@inproceedings{bleichenbacher,
+ title = {Generating {E}l{G}amal signatures without knowing the secret key},
+ author = {Daniel Bleichenbacher},
+ booktitle = {Eurocrypt 96},
+ year = {1996},
+ month = {May},
+ address = {Zaragoza, Spain},
+ ftp_ps_url = {ftp://ftp.inf.ethz.ch/pub/publications/papers/ti/isc/ElGamal.ps},
+}
+
+@inproceedings{mixmaster-reliable,
+ title = {Comparison between two practical mix designs},
+ author = {Claudia D\'{\i}az and Len Sassaman and Evelyne Dewitte},
+ booktitle = {Proceedings of 9th European Symposium on Research in Computer Security
+ (ESORICS)},
+ year = {2004},
+ month = {September},
+ address = {France},
+ series = {LNCS},
+ www_ps_gz_url = {http://www.esat.kuleuven.ac.be/~cdiaz/papers/cdiaz_esorics.ps.gz},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{jap,
+ title = {Web {MIX}es: A system for anonymous and unobservable {I}nternet access},
+ author = {Oliver Berthold and Hannes Federrath and Stefan K\"opsell},
+ booktitle = {Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design
+ Issues in Anonymity and Unobservability},
+ year = {2000},
+ month = {July},
+ pages = {115--129},
+ editor = {H. Federrath},
+ publisher = {Springer-Verlag, LNCS 2009},
+ www_pdf_url = {http://www.inf.fu-berlin.de/~feder/publ/2001/BeFK2001BerkeleyLNCS2009.pdf},
+ www_section = {Anonymous communication},
+}
+
+@misc{nguyen,
+ title = {{Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3}},
+ author = {Phong Q. Nguyen},
+ booktitle = {Eurocrypt 04},
+ year = {2004},
+ month = {May},
+ address = {Interlaken, Switzerland},
+ editor = {C. Cachin},
+ ftp_ps_url = {ftp://ftp.di.ens.fr/pub/users/pnguyen/Eurocrypt04.ps},
+}
+
+@inproceedings{pailli99,
+ author = {Pascal Paillier},
+ title = {{Public-Key Cryptosystems Based on Composite Degree
+ Residuosity Classes}},
+ editor = {Jacques Stern},
+ booktitle = {Advances in Cryptology:\ EUROCRYPT '99},
+ year = {1999},
+ series = {Lecture Notes in Computer Science},
+ volume = {1592},
+ pages = {223--238},
+ publisher = {Springer-Verlag},
+}
+
+@inproceedings{tau-indy,
+ author = {Yael Gertner and Shafi Goldwasser and Tal Malkin},
+ title = {A Random Server Model for Private Information Retrieval or How to Achieve Information Theoretic PIR Avoiding Database Replication},
+ booktitle = {RANDOM '98: Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science},
+ year = {1998},
+ isbn = {3-540-65142-X},
+ pages = {200--217},
+ publisher = {Springer-Verlag},
+ address = {London, UK},
+ }
+
+@inproceedings{fiveyearslater,
+ title = {{Privacy-enhancing technologies for the Internet, II: Five years later}},
+ author = {Ian Goldberg},
+ booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2002)},
+ year = {2002},
+ month = {April},
+ editor = {Roger Dingledine and Paul Syverson},
+ publisher = {Springer-Verlag, LNCS 2482},
+ www_section = {Misc},
+}
+
+@inproceedings{beimel-robust,
+ author = {A. Beimel and Y. Stahl},
+ title = {Robust information-theoretic private information retrieval},
+ booktitle = {3rd Conf. on Security in Communication Networks},
+ editor = {S. Cimato C. Galdi G. Persiano },
+ publisher = {Springer-Verlag},
+ series = {Lecture Notes in Computer Science},
+ pages = {326-341},
+ volume = {2576},
+ year = {2002}
+}
+
+@inproceedings{beimel-barrier,
+ title = {{Breaking the $O(n^{1/(2k-1)})$ Barrier for Information-Theoretic Private Information Retrieval}},
+ author = {Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Jean-Fran\c{c}ois Raymond},
+ booktitle = {Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS)},
+ year = {2002},
+ www_pdf_url = {http://www.cs.bgu.ac.il/~beimel/Papers/BIKR.pdf},
+}
+
+@inproceedings{mixencrypt,
+ title = {Provably Secure Public-Key Encryption for Length-Preserving Chaumian Mixes},
+ author = {Bodo M{\"o}ller},
+ booktitle = {Proceedings of {CT-RSA} 2003},
+ year = {2003},
+ month = {April},
+ publisher = {Springer-Verlag, LNCS 2612},
+ www_pdf_url = {http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/mixencrypt-ct-rsa2003.pdf},
+ www_section = {Anonymous communication},
+}
+
+@inproceedings{minx,
+ title = {Minx: A Simple and Efficient Anonymous Packet Format},
+ author = {George Danezis and Ben Laurie},
+ booktitle = {{Proceedings of the Workshop on Privacy in the Electronic Society (WPES
+ 2004)}},
+ year = {2004},
+ month = {October},
+ address = {Washington, DC, USA},
+}
+
+@inproceedings{nym-alias-net,
+ title = {{The Design, Implementation and Operation of an Email Pseudonym Server}},
+ author = {David Mazi\`eres and M. Frans Kaashoek},
+ booktitle = {Proceedings of the 5th ACM Conference on Computer and Communications
+ Security (CCS'98)},
+ year = {1998},
+ month = {November},
+ publisher = {ACM Press},
+ www_pdf_url = {ftp://cag.lcs.mit.edu/pub/dm/papers/mazieres:pnym.pdf},
+ www_section = {Pseudonymity},
+}
+
+@inproceedings{mixminion,
+ title = {{Mixminion: Design of a Type III Anonymous Remailer Protocol}},
+ author = {George Danezis and Roger Dingledine and Nick Mathewson},
+ booktitle = {Proceedings of the 2003 IEEE Symposium on Security and Privacy},
+ year = {2003},
+ month = {May},
+ www_pdf_url = {http://mixminion.net/minion-design.pdf},
+ www_important = {1},
+ www_section = {Anonymous communication},
+}
+
+@inproceedings{goldberg-2007,
+ title = {{Improving the Robustness of Private Information Retrieval}},
+ author = {Ian Goldberg},
+ booktitle = {Proceedings of the 2007 IEEE Symposium on Security and Privacy},
+ year = {2007},
+ month = {May},
+}
+
+@inproceedings{disad-free-routes,
+ title = {The disadvantages of free {MIX} routes and how to overcome them},
+ author = {Oliver Berthold and Andreas Pfitzmann and Ronny Standtke},
+ booktitle = {Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design
+ Issues in Anonymity and Unobservability},
+ year = {2000},
+ month = {July},
+ pages = {30--45},
+ editor = {H. Federrath},
+ publisher = {Springer-Verlag, LNCS 2009},
+ www_important = {1},
+ www_section = {Traffic analysis},
+ www_pdf_url = {http://www.tik.ee.ethz.ch/~weiler/lehre/netsec/Unterlagen/anon/disadvantages_berthold.pdf},
+}
+
+@inproceedings{goldschlag96,
+ author = {David M. Goldschlag and Michael G. Reed and Paul F. Syverson},
+ title = {Hiding Routing Information},
+ booktitle = {Information Hiding},
+ pages = {137-150},
+ year = {1996},
+ www_pdf_url = {http://www.onion-router.net/Publications/IH-1996.pdf},
+}
+
+@inproceedings{berthold,
+ author = {Oliver Berthold and Sebastian Clau\ss and Stefan K\"opsell and Andreas Pfitzmann},
+ title = {Efficiency Improvements of the Private Message Service},
+ booktitle = {Proceedings of Information Hiding Workshop (IH 2001)},
+ year = {2001},
+ month = {April},
+ editor = {Ira S. Moskowitz},
+ publisher = {Springer-Verlag, LNCS 2137},
+ pages = {112-125},
+}
+
+@inproceedings{cooper,
+ title = {Preserving Privacy in a Network of Mobile Computers},
+ author = {David A. Cooper and Kenneth P. Birman},
+ booktitle = {Proceedings of the 1995 IEEE Symposium on Security and Privacy},
+ year = {1995},
+ month = {May},
+}
+
+@inproceedings{reusable-channels,
+ title = {Reusable Anonymous Return Channels},
+ author = {Philippe Golle and Markus Jakobsson},
+ booktitle = {{Proceedings of the Workshop on Privacy in the Electronic Society (WPES
+ 2003)}},
+ year = {2003},
+ month = {October},
+ address = {Washington, DC, USA},
+ www_pdf_url = {http://crypto.stanford.edu/~pgolle/papers/return.pdf},
+ www_remarks = {Reencryption mix-nets can allow users to use a single reply channel even
+ when they maintain multiple separate nyms (think of it like a reply block but it
+ looks different each time you give it to somebody).},
+ www_ps_url = {http://crypto.stanford.edu/~pgolle/papers/return.ps},
+ www_section = {Anonymous communication},
+}
+
+@conference{bh-us-03-sassaman-dingledine,
+ title = {{Attacks on Anonymity Systems: Theory and Practice}},
+ author = {Roger Dingledine and Len Sassaman},
+ booktitle = {{Black Hat USA 2003 Briefings}},
+ year = {2003},
+ month = {July},
+ address = {Las Vegas, NV, USA},
+ www_pdf_url = {http://www.blackhat.com/presentations/bh-usa-03/bh-us-03-sassaman-dingledine/bh-us-03-sassaman.pdf},
+}
+
+@inproceedings{trickle02,
+ title = {From a Trickle to a Flood: Active Attacks on Several Mix Types},
+ author = {Andrei Serjantov and Roger Dingledine and Paul Syverson},
+ booktitle = {Proceedings of Information Hiding Workshop (IH 2002)},
+ year = {2002},
+ month = {October},
+ editor = {Fabien Petitcolas},
+ publisher = {Springer-Verlag, LNCS 2578},
+ www_pdf_url = {http://freehaven.net/doc/batching-taxonomy/taxonomy.pdf},
+ www_ps_url = {http://freehaven.net/doc/batching-taxonomy/taxonomy.ps},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{bittorrent,
+ author = {Bram Cohen},
+ title = {{Incentives Build Robustness in BitTorrent}},
+ booktitle = {Workshop on Economics of Peer-to-Peer Systems},
+ year = {2003},
+ month = {May},
+ address = {Berkeley, CA, USA},
+ note = {\url{http://www.sims.berkeley.edu/research/conferences/p2pecon/papers/s4-cohen.pdf}},
+}
+
+@inproceedings{pir,
+ title = {Private Information Retrieval},
+ author = {Benny Chor and Oded Goldreich and Eyal Kushilevitz and Madhu Sudan},
+ booktitle = {{IEEE} Symposium on Foundations of Computer Science},
+ pages = {41-50},
+ year = {1995},
+ www_ps_url = {http://theory.lcs.mit.edu/~madhu/papers/pir-journ.ps},
+}
+
+@inproceedings{torta05,
+ title = {Low-Cost Traffic Analysis of {Tor}},
+ author = {Steven J. Murdoch and George Danezis},
+ booktitle = {Proceedings of the 2005 IEEE Symposium on Security and Privacy},
+ year = {2005},
+ month = {May},
+ publisher = {IEEE CS},
+ www_pdf_url = {http://www.cl.cam.ac.uk/users/sjm217/papers/oakland05torta.pdf},
+ www_section = {Traffic analysis},
+}
+
+@article{beimel01informationtheoretic,
+ author = {Amos Beimel and Yuval Ishai},
+ title = {Information-Theoretic Private Information Retrieval: {A} Unified Construction},
+ journal = {Lecture Notes in Computer Science},
+ volume = {2076},
+ pages = {89--98},
+ year = {2001},
+ www_pdf_url = {http://www.cs.bgu.ac.il/~beimel/Papers/BI.pdf},
+}
+
+@techreport{freedom2-arch,
+ title = {Freedom Systems 2.0 Architecture},
+ author = {Philippe Boucher and Adam Shostack and Ian Goldberg},
+ institution = {Zero Knowledge Systems, {Inc.}},
+ year = {2000},
+ month = {December},
+ type = {White Paper},
+ www_pdf_url = {http://osiris.978.org/~brianr/crypto-research/anon/www.freedom.net/products/whitepapers/Freedom_System_2_Architecture.pdf},
+ www_section = {Anonymous communication},
+ day = {18},
+}
+
+@techreport{freedom2-mail,
+ title = {Freedom 2.0 Mail System},
+ author = {Roger McFarlane and Adam Back and Graydon Hoare and Serge Chevarie-Pelletier and Bill Heelan and Christian Paquin and Deniz Sarikaya},
+ institution = {Zero Knowledge Systems, {Inc.}},
+ year = {2000},
+ month = {December},
+ type = {White Paper},
+ www_pdf_url = {http://www.cypherspace.org/~adam/pubs/freedom2-mail.pdf},
+ www_section = {Anonymous communication},
+ day = {19},
+}
+
+@techreport{cosic-2007-001,
+ author = {Len Sassaman and Bart Preneel},
+ title = {{The Byzantine Postman Problem: A Trivial Attack Against PIR-based Nym Servers}},
+ year = {2007},
+ month = {February},
+ institution = {Katholieke Universiteit Leuven},
+ number = {ESAT-COSIC 2007-001},
+ url = {http://www.cosic.esat.kuleuven.be/publications/article-880.pdf},
+}
+
+@misc{kidnap-len,
+ author = {Roger Dingledine},
+ title = {Remop inbreeding, or, the 'kidnap {L}en' attack},
+ year = {2003},
+ month = {March},
+ howpublished = {Mailing list post},
+ note = {\url{http://archives.seul.org/mixminion/dev/Mar-2003/msg00007.html}},
+}
+
+@misc{hal-remailer,
+ author = {Hal Finney},
+ title = {New remailer...},
+ year = {1992},
+ month = {October},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1992/10/msg00082.html}},
+}
+
+@misc{harmful,
+ author = {Anonymous},
+ title = {alt.anonymous.messages Considered Harmful},
+ year = {1995},
+ month = {November},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1995/11/msg00089.html}},
+}
+
+@misc{aam,
+ author = {Rick Busdiecker},
+ title = {Message pool: alt.anonymous.messages},
+ year = {1994},
+ month = {August},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1994/08/msg00185.html}},
+}
+
+@misc{remailer-attacks,
+ author = {Lance Cottrell},
+ title = {Mixmaster and Remailer Attacks},
+ note = {\url{http://www.obscura.com/~loki/remailer/remailer-essay.html}},
+}
+
+@misc{replay,
+ author = {Lance Cottrell},
+ title = {Re: Strengthening Remailer Protocols},
+ year = {1996},
+ month = {September},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1996/09/msg00730.html}},
+}
+
+@misc{surb,
+ author = {Mike Ingle},
+ title = {Interoperability, One-use Remailer Tickets},
+ year = {1994},
+ month = {December},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1994/12/msg00245.html}},
+}
+
+@misc{pop-mix,
+ author = {Andrew Loewenstern},
+ title = {Re: Strengthening Remailer Protocols},
+ year = {1996},
+ month = {September},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1996/09/msg00898.html}},
+}
+
+@misc{tcmay,
+ author = {Tim May},
+ title = {Re: Strengthening Remailer Protocols},
+ year = {1996},
+ month = {September},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1996/09/msg00167.html}},
+}
+
+@misc{pipenet,
+ title = {PipeNet 1.1},
+ author = {Wei Dai},
+ year = {1996},
+ month = {August},
+ howpublished = {Usenet post},
+ www_section = {Anonymous communication},
+ note = {\url{http://www.eskimo.com/~weidai/pipenet.txt}},
+}
+
+@misc{alpha-faq,
+ title = {{FAQ} for the {ALPHA.C2.ORG} {R}emailer},
+ author = {Andre Bacard},
+ year = {1995},
+ month = {October},
+ howpublished = {Usenet post},
+ note = {\url{http://groups.google.com/groups?selm=4q4tsr%248ui%40crl14.crl.com&output=gplain}},
+}
+
+@misc{prng-back,
+ title = {Personal Communication},
+ author = {Adam Back},
+ year = {2003},
+ month = {April},
+}
+
+@misc{sassaman-lisa,
+ title = {The Promise of Privacy},
+ author = {Len Sassaman},
+ year = {2002},
+ month = {November},
+ howpublished = {Invited talk, LISA XVI},
+ organization = {USENIX}
+}
+
+@inproceedings{danezis-pet2004,
+ title = {The Traffic Analysis of Continuous-Time Mixes},
+ author = {George Danezis},
+ booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2004)},
+ year = {2004},
+ month = {May},
+ series = {LNCS},
+ www_pdf_url = {http://www.cl.cam.ac.uk/users/gd216/cmm2.pdf},
+ www_section = {Traffic analysis},
+}
+
+@misc{pgp5-elgamal,
+ title = {{Re: ElGamal signature encoding}},
+ author = {Hal Finney},
+ year = {1998},
+ month = {April},
+ howpublished = {Mailing list post},
+ note = {\url{http://www.privacy.nb.ca/cryptography/archives/coderpunks/new/1998-04/0050.html}},
+}
+
+@misc{gpg-compromised,
+ title = {{GnuPG's ElGamal signing keys compromised}},
+ author = {Werner Koch},
+ year = {2003},
+ month = {November},
+ howpublished = {Mailing list post},
+ note = {\url{http://lists.gnupg.org/pipermail/gnupg-announce/2003q4/000276.html}},
+}
+
+@misc{mixmaster-spec,
+ title = {Mixmaster {P}rotocol --- {V}ersion 2},
+ author = {Ulf M\"oller and Lance Cottrell and Peter Palfrader and Len Sassaman},
+ year = {2003},
+ month = {July},
+ www_section = {Anonymous communication},
+ note = {\url{http://www.abditum.com/mixmaster-spec.txt}},
+}
+
+@misc{pynchon-spec,
+ title = {{P}ynchon {G}ate {P}rotocol Draft Specification},
+ author = {Nick Mathewson},
+ year = {2004},
+ month = {September},
+ www_section = {Anonymous communication},
+ note = {\url{http://www.abditum.com/pynchon/}},
+}
+
+@misc{underhill-spec,
+ title = {Underhill: A Proposed Type 3 Nymserver Protocol Specification},
+ author = {Nick Mathewson},
+ year = {2004},
+ month = {August},
+ www_section = {Anonymous communication},
+ note = {\url{http://www.mixminion.net/nym-spec.txt}},
+}
+
+@misc{rfc-1036,
+ title = {{Standard for Interchange of USENET Messages}},
+ author = {M. Horton and R. Adams},
+ year = {1987},
+ month = {December},
+ organization = {Internet Engineering Task Force},
+ howpublished = {Request for Comments: 1036},
+ www_txt_url = {http://www.ietf.org/rfc/rfc1036.txt},
+}
+
+@misc{rfc-2246,
+ title = {{The TLS Protocol}},
+ author = {T. Dierks and C. Allen},
+ year = {1999},
+ month = {January},
+ organization = {Internet Engineering Task Force},
+ howpublished = {Request for Comments: 2246},
+ www_txt_url = {http://www.ietf.org/rfc/rfc2246.txt},
+}
+
+@misc{rfc-2440,
+ title = {{OpenPGP Message Format}},
+ author = {J. Callas and L. Donnerhacke and H. Finney and R. Thayer},
+ year = {1998},
+ month = {November},
+ organization = {Internet Engineering Task Force},
+ howpublished = {Request for Comments: 2440},
+ www_txt_url = {http://www.ietf.org/rfc/rfc2440.txt},
+}
+
+@misc{rfc-2779,
+ title = {{Instant Messaging / Presence Protocol Requirements}},
+ author = {M. Day and S. Aggarwal and G. Mohr and J. Vincent},
+ year = {2000},
+ month = {February},
+ organization = {Internet Engineering Task Force},
+ howpublished = {Request for Comments: 2779},
+ www_txt_url = {http://www.ietf.org/rfc/rfc2779.txt},
+}
+
+@inproceedings{tor-design,
+ title = {Tor: The Second-Generation Onion Router},
+ author = {Roger Dingledine and Nick Mathewson and Paul Syverson},
+ booktitle = {Proceedings of the 13th USENIX Security Symposium},
+ year = {2004},
+ month = {August},
+ www_pdf_url = {http://freehaven.net/tor/tor-design.pdf},
+ www_section = {Anonymous communication},
+}
+
+@misc{echolot,
+ author = {Peter Palfrader},
+ title = {Echolot: a pinger for anonymous remailers},
+ note = {\url{http://www.palfrader.org/echolot/}},
+}
+
+@misc{helsingius,
+ author = {Johan Helsingius},
+ title = {press release announcing closure of anon.penet.fi},
+ howpublished = {\url{http://www.penet.fi/press-english.html}},
+}
+
+@misc{mccoy,
+ author = {Jim McCoy},
+ title = {Anonymous Mailbox Servers},
+ year = {1997},
+ month = {August},
+ howpublished = {Presentation, HIP'97},
+}
+
+@misc{bram-chat,
+ title = {Personal Communication},
+ author = {Bram Cohen},
+ year = {2006},
+ month = {December},
+}
+
+@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},
+}
+
+@InProceedings{e2e-traffic,
+ author = {Nick Mathewson and Roger Dingledine},
+ title = {Practical Traffic Analysis: Extending and Resisting Statistical Disclosure},
+ booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2004)},
+ year = {2004},
+ month = {May},
+ series = {LNCS},
+ www_section = traffic,
+ www_pdf_url = "http://freehaven.net/doc/e2e-traffic/e2e-traffic.pdf";,
+}
+
+@inproceedings{pynchon,
+ title = {{The Pynchon Gate: A Secure Method of Pseudonymous Mail Retrieval}},
+ author = {Len Sassaman and Bram Cohen and Nick Mathewson},
+ booktitle = {{Proceedings of the Workshop on Privacy in the Electronic Society (WPES
+ 2005)}},
+ year = {2005},
+ month = {November},
+ address = {Arlington, VA, USA},
+ www_pdf_url = {http://www.abditum.com/pynchon/sassaman-wpes2005.pdf},
+ www_section = {Pseudonymity},
+}
+
+@inproceedings{DanSer04,
+ title = {Statistical Disclosure or Intersection Attacks on Anonymity Systems},
+ author = {George Danezis and Andrei Serjantov},
+ booktitle = {Proceedings of 6th Information Hiding Workshop (IH 2004)},
+ year = {2004},
+ month = {May},
+ address = {Toronto},
+ series = {LNCS},
+ www_ps_url = {http://www.cl.cam.ac.uk/~aas23/papers_aas/PoolSDA2.ps},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{hitting-set04,
+ title = {The Hitting Set Attack on Anonymity Protocols},
+ author = {Dogan Kesdogan and Lexi Pimenidis},
+ booktitle = {Proceedings of 6th Information Hiding Workshop (IH 2004)},
+ year = {2004},
+ month = {May},
+ address = {Toronto},
+ series = {LNCS},
+ www_pdf_url = {http://freehaven.net/anonbib/papers/Hitting_Set_Attack.pdf},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{statistical-disclosure,
+ title = {Statistical Disclosure Attacks: Traffic Confirmation in Open Environments},
+ author = {George Danezis},
+ booktitle = {Proceedings of Security and Privacy in the Age of Uncertainty, ({SEC2003})},
+ organization = {{IFIP TC11}},
+ year = {2003},
+ month = {May},
+ address = {Athens},
+ pages = {421--426},
+ editor = {Gritzalis and Vimercati and Samarati and Katsikas},
+ publisher = {Kluwer},
+ www_section = {Traffic analysis},
+ www_pdf_url = {http://www.cl.cam.ac.uk/~gd216/StatDisclosure.pdf},
+}
+
+@inproceedings{wright02,
+ title = {An Analysis of the Degradation of Anonymous Protocols},
+ author = {Matthew Wright and Micah Adler and Brian Neil Levine and Clay Shields},
+ booktitle = {Proceedings of the Network and Distributed Security Symposium - {NDSS} '02},
+ year = {2002},
+ month = {February},
+ publisher = {IEEE},
+ www_pdf_url = {http://www.cs.umass.edu/~mwright/papers/wright-degrade.pdf},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{langos02,
+ title = {Dummy Traffic Against Long Term Intersection Attacks},
+ author = {Oliver Berthold and Heinrich Langos},
+ booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2002)},
+ year = {2002},
+ month = {April},
+ editor = {Roger Dingledine and Paul Syverson},
+ publisher = {Springer-Verlag, LNCS 2482},
+ www_pdf_url = {http://www.inf.fu-berlin.de/~berthold/publ/BeLa_02.pdf},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{raymond00,
+ title = {{Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems}},
+ author = {Jean-Fran\c{c}ois Raymond},
+ booktitle = {Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design
+ Issues in Anonymity and Unobservability},
+ year = {2000},
+ month = {July},
+ pages = {10-29},
+ editor = {H. Federrath},
+ publisher = {Springer-Verlag, LNCS 2009},
+ www_important = {1},
+ www_section = {Traffic analysis},
+ www_pdf_url = {http://www.geocities.com/j_f_raymond/mesarticles/berkeley_ws_lncs.pdf},
+ www_ps_url = {http://www.geocities.com/j_f_raymond/mesarticles/berkeley_ws_lncs.ps},
+}
+
+@inproceedings{usability:weis2006,
+ title = {Anonymity Loves Company: Usability and the Network Effect},
+ author = {Roger Dingledine and Nick Mathewson},
+ booktitle = {Proceedings of the Fifth Workshop on the Economics of Information Security
+ (WEIS 2006)},
+ year = {2006},
+ month = {June},
+ address = {Cambridge, UK},
+ www_section = {Economics},
+ bookurl = {http://weis2006.econinfosec.org/},
+ www_pdf_url = {http://freehaven.net/doc/wupss04/usability.pdf},
+}
+
+@inproceedings{back01,
+ title = {Traffic Analysis Attacks and Trade-Offs in Anonymity Providing Systems},
+ author = {Adam Back and Ulf M\"oller and Anton Stiglic},
+ booktitle = {Proceedings of Information Hiding Workshop (IH 2001)},
+ year = {2001},
+ month = {April},
+ pages = {245--257},
+ editor = {Ira S. Moskowitz},
+ publisher = {Springer-Verlag, LNCS 2137},
+ www_important = {1},
+ www_section = {Traffic analysis},
+ www_pdf_url = {http://www.cypherspace.org/adam/pubs/traffic.pdf},
+}
+
+@inproceedings{limits-open,
+ title = {Limits of Anonymity in Open Environments},
+ author = {Dogan Kesdogan and Dakshi Agrawal and Stefan Penz},
+ booktitle = {Proceedings of Information Hiding Workshop (IH 2002)},
+ year = {2002},
+ month = {October},
+ editor = {Fabien Petitcolas},
+ publisher = {Springer-Verlag, LNCS 2578},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{fsmix03,
+ title = {Forward Secure Mixes},
+ author = {George Danezis},
+ booktitle = {Proceedings of 7th Nordic Workshop on Secure {IT} Systems},
+ year = {2002},
+ month = {November},
+ address = {Karlstad, Sweden},
+ pages = {195--207},
+ editor = {Fisher-Hubner, Jonsson},
+ www_section = {Anonymous communication},
+ day = {7},
+ www_pdf_url = {http://www.cl.cam.ac.uk/~gd216/fsmix.pdf},
+}
+
+@inproceedings{wright03,
+ title = {Defending Anonymous Communication Against Passive Logging Attacks},
+ author = {Matthew Wright and Micah Adler and Brian Neil Levine and Clay Shields},
+ booktitle = {Proceedings of the 2003 IEEE Symposium on Security and Privacy},
+ year = {2003},
+ month = {May},
+ www_pdf_url = {http://www.cs.umass.edu/~mwright/papers/wright-passive.pdf},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{sybil,
+ title = {{The Sybil Attack}},
+ author = {John Douceur},
+ booktitle = {Proceedings of the 1st International Peer To Peer Systems Workshop (IPTPS
+ 2002)},
+ year = {2002},
+ month = {March},
+ www_important = {1},
+ www_pdf_url = {http://www.cs.rice.edu/Conferences/IPTPS02/101.pdf},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{feamster:wpes2004,
+ title = {Location Diversity in Anonymity Networks},
+ author = {Nick Feamster and Roger Dingledine},
+ booktitle = {{Proceedings of the Workshop on Privacy in the Electronic Society (WPES
+ 2004)}},
+ year = {2004},
+ month = {October},
+ address = {Washington, DC, USA},
+ www_ps_url = {http://freehaven.net/doc/routing-zones/routing-zones.ps},
+ www_section = {Anonymous communication},
+}
+
+@inproceedings{randomized-checking,
+ title = {Making mix nets robust for electronic voting by randomized partial checking},
+ author = {Markus Jakobsson and Ari Juels and Ronald L. Rivest},
+ booktitle = {Proceedings of the 11th USENIX Security Symposium},
+ year = {2002},
+ month = {August},
+ www_important = {1},
+ www_pdf_url = {http://www.rsasecurity.com/rsalabs/staff/bios/mjakobsson/rpcmix/rpcmix.pdf},
+ www_section = {Provable shuffles},
+}
+
+@article{min-disclosure,
+ author = {Gilles Brassard and David Chaum and Claude Cr\&\#233;peau},
+ title = {Minimum disclosure proofs of knowledge},
+ journal = {Journal of Computer and System Sciences},
+ volume = {37},
+ number = {2},
+ year = {1988},
+ issn = {0022-0000},
+ pages = {156--189},
+ doi = {http://dx.doi.org/10.1016/0022-0000(88)90005-0},
+ publisher = {Academic Press, Inc.},
+ address = {Orlando, FL, USA},
+ }
+
+@InProceedings{Rabin77,
+ author = {M. O. Rabin},
+ editor = {R. Lipton and R. De Millo},
+ booktitle = {Foundations of Secure Computation},
+ title = {Digitalized Signatures},
+ publisher = {Academic Press},
+ address = {New York},
+ pages = {155-166},
+ year = {1978},
+}
+
+@InProceedings{ChaumFiNa88,
+ author = {D. Chaum and A. Fiat and M. Naor},
+ title = {Untraceable Electronic Cash},
+ pages = {319--327},
+ booktitle = {CRYPTO88},
+ editor = {S. Goldwasser},
+ note = {Lecture Notes in Computer Science No. 403},
+ publisher = {Springer-Verlag},
+ year = {1988},
+}
+
+@inproceedings{parkes-auction,
+ author = {David C. Parkes and Michael O. Rabin and Stuart M. Shieber and C. A. Thorpe},
+ title = {Practical secrecy-preserving, verifiably correct and trustworthy auctions},
+ booktitle = {ICEC '06: Proceedings of the 8th International Conference on Electronic Commerce},
+ year = {2006},
+ isbn = {1-59593-392-1},
+ pages = {70--81},
+ location = {Fredericton, New Brunswick, Canada},
+ ee = {http://doi.acm.org/10.1145/1151454.1151478},
+ doi = {http://doi.acm.org/10.1145/1151454.1151478},
+ publisher = {ACM Press},
+ address = {New York, NY, USA},
+ }
\ No newline at end of file
Added: doc/trunk/pynchon-gate/byzantine-fix.tex
===================================================================
--- doc/trunk/pynchon-gate/byzantine-fix.tex 2007-04-24 12:47:49 UTC (rev 1780)
+++ doc/trunk/pynchon-gate/byzantine-fix.tex 2007-05-07 23:21:13 UTC (rev 1781)
@@ -0,0 +1,197 @@
+\documentclass{llncs-rabbi}
+
+
+\usepackage{url}
+%\usepackage{graphics}
+\usepackage{amsmath}
+\usepackage{subfigure}
+\usepackage{epsfig}
+
+\setcounter{page}{1}
+
+\begin{document}
+
+\title{Solving the Byzantine Postman Problem}
+\subtitle{Improving the Robustness of Private Information Retrieval Without Loss of Security}
+
+\author{Len Sassaman\inst{1} \and Bart Preneel\inst{1}}
+\institute{K. U. Leuven ESAT-COSIC \\
+Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium
+\email{\{len.sassaman,bart.preneel\}@esat.kuleuven.be}}
+
+
+\maketitle
+\begin{abstract}
+
+Over the last several decades, there have been numerous systems proposed which aim to preserve the anonymity of the recipient of some data. Some have involved trusted third-parties or trusted hardware; others have been constructed on top of link-layer anonymity systems or mix networks.
+
+In this paper, we examine the Pynchon Gate~\cite{pynchon}, a pseudonymous message system which takes an alternate approach to this problem by using Private Information Retrieval (PIR) as the basis for its pseudonymity properties. We restrict our examination to a flaw in the Pynchon Gate system first described in our technical report~\cite{cosic-2007-001}; as it was originally presented, the Pynchon Gate detects the presence of (and protects against certain attacks by) Byzantine servers operating in the system, but it fails to identify \emph{which} server or set of servers is Byzantine, thus opening the door for denial of service attacks as well as other potential anonymity compromises by Byzantine servers. We evaluate a solution to this problem recently proposed by Goldberg~\cite{goldberg-2007}, and critique the security and performance trade-offs made in~\cite{goldberg-2007} as compared to the original (but flawed) Pynchon Gate Protocol (PynGP)~\cite{pynchon-spec} presented in the first Pynchon Gate paper, and find Goldberg's solution to be inadequate for several reasons.
+
+We then show a trivial modification to the original PynGP which allows for detection and identification of Byzantine nodes, with no weakening of the security model necessary, at the relatively affordable cost of greater bandwidth requirements during certain communication operations. We demonstrate that this adequately solves the problems raised by~\cite{cosic-2007-001}, and argue that it is the most suitable method of addressing the attack in question yet proposed.
+
+%We then show that certain PIR algorithms, such as that proposed by Goldberg and previously by Beimel and Stahl~\cite{beimel-robust}, are unsuitable in their present form for use as the basis of a pseudonymity system, for they are vulnerable to a class of attacks known as \emph{tagging attacks}. We demonstrate that both the original and the revised PynGP is secure against these attacks.
+
+%Lastly, we suggest an examination of other PIR protocols as to their suitability for use in anonymity systems, based on the additional security requirements inherent to anonymity systems compared to the other uses more commonly proposed in the literature.
+
+\end{abstract}
+
+\section{Introduction}
+Several proposals have been made for the use of private information
+retrieval (PIR)~\cite{pir} primitives to build secure, fault-tolerant
+pseudonymous mail retrieval systems~\cite{cooper,berthold,kissner04private,pynchon}.
+
+PIR-based pseudonym (or \emph{nym}) servers have several significant advantages over nym servers based on other technologies. PIR protocols can be designed to offer \emph{information-theoretic security}, i.e., assuming that the system is correct, an attacker with unlimited computational power cannot defeat the system merely by virtue of being able to perform calculations which reveal the private information. Other PIR protocols merely offer computational security: in Computational PIR systems~\cite{CPIR}, the privacy of the PIR query is protected only against an adversary restricted to polynomial-time computational capability. CPIR-based solutions have the significant advantage that they can be performed using a single server, and do not require distribution of trust to ensure that the information retrieval requests remain private. However, such systems presently have prohibitive computational cost on commodity hardware.
+
+\subsection{Distribution of Trust in Public Anonymity Systems}
+
+In distributed-trust information-theoretic PIR systems, the privacy of the system is predicated upon no single entity being able to gain access to sensitive data, be it the private information itself, or second-order information which can be used to obtain information about the private information. Of particular concern are the possibilities that a single adversary may operate multiple nodes under different identities, effectively ensuring node collusion~\cite{sybil}, or that significant amounts of the anonymity infrastructure may lack good \emph{location independence}~\cite{feamster:wpes2004}. Thus, systems which encourage participation by many unaffiliated operators of diverse backgrounds across a wide range of network providers can provide stronger services than those in which infrastructure operation is more tightly restricted. Rather than attempting to ensure that the adversary is unable to gain control of any part of the infrastructure, this \emph{laissez-faire} approach to anonymity service operation taken by some of the more successful anonymity services~\cite{tor-design,mixmaster-spec} simply accepts that some nodes will be controlled by an adversary, and accounts for this fact in the design of these systems.
+
+
+%In distributed-trust information-theoretic PIR systems, the privacy of the system is predicated upon no single entity being able to gain access to sensitive data, be it the private information itself, or a second-; of particular concern are the possibilities that a single adversary may operate multiple nodes under different identities, effectively ensuring node collusion~\cite{sybil}, or that significant amounts of the anonymity infrastructure may be lack good \emph{location independence}~\cite{feamster:wpes2004}. Thus, systems which encourage participation by many unaffiliated operators of diverse backgrounds across a wide range of network providers may provide stronger services than those in which infrastructure operation is more tightly restricted. Rather than attempt to ensure that the adversary is unable to gain control of any part of the infrastructure, this \emph{laissez-faire} approach to anonymity service operation taken by some of the more successful anonymity services~\cite{tor-design,mixmaster-spec} simply accepts that some nodes will be controlled by an adversary, and accounts for this fact in the design of these systems.
+
+\subsection{Background on Nym Servers} % move this higher perhaps?
+Pseudonymous messaging services allow users to send
+messages that originate at a pseudonymous address (or ``nym'') unlinked to
+the user, and to receive messages sent to that address, without allowing
+an attacker to deduce which users are associated with which pseudonyms.
+These systems can be used for parties to communicate without revealing their
+identities, or as a building-block for other systems that need a bi-directional anonymous
+communication channel, such as Free Haven~\cite{freehaven-berk}.
+
+\subsection{The Pynchon Gate and The Byzantine Postman Problem}
+The most recent proposal for a nym server based on PIR with information-theoretic security, the Pynchon Gate~\cite{pynchon}, offers greater robustness, stronger anonymity assurances, and better traffic analysis resistance than previously proposed pseudonym systems.
+However, as we have previously noted~\cite{cosic-2007-001}, it contains a flaw in its protocol which can be used to launch a denial of service attack against the system, rendering it unusable.\footnote{If one or more of the servers in the system is Byzantine, the protocol will detect that the results of the PIR request are not correct, and will treat the results as poisoned, thus eliminating potential direct attacks by Byzantine servers against the \emph{privacy properties} of the system. However, the specific PIR protocol used in the Pynchon Gate is designed in such a way that it is impossible to know which server was Byzantine, and therefore Byzantine servers can act with impunity, inevitably locking every user of the system into a state of constant denial of service.} Furthermore, the attack is not merely limited to decreased utility of the system; due to the network-effects properties of anonymity systems, denying service to one set of users can effectively weaken the anonymity provided to a different set of users~\cite{econymics}. This paper evaluates an independent attempt to address this problem~\cite{goldberg-2007}, and proposes an alternative solution.
+
+
+\section{Background on The Pynchon Gate}
+To address the reliability problems of silent node failure, as well as the serious security problems of statistical disclosure attacks~\cite{raymond00,statistical-disclosure,DanSer04} and end-to-end traffic analysis~\cite{e2e-traffic}, Sassaman et al. propose a complete architectural design of a PIR-based pseudonym service offering information-theoretic protection, called the Pynchon Gate~\cite{pynchon}.
+
+\subsection{Architecture Overview}
+The architecture consists of an Internet-facing component referred to as the ``nym server'', which receives messages addressed to users of the system and acts as a gateway between the pseudonym service and other Internet services such as email. Behind the nym server is a component known as the ``collator'', which structures the incoming messages in the form of a three-level hash tree, which is then replicated to a series of mutually untrusted distribution databases referred to as ``distributors''.
+
+Email addressed to a specific pseudonym is stored in a specific location in the database, such that the owner of the pseudonym knows what information to request to obtain his message. Using the PIR protocol described in Section~\ref{subsec:PIR}, the user submits a PIR query to $\ell$ distributors, and his message is returned with none of the distributors able to deduce any information about the user's query unless all $\ell$ distributors collude.
+
+\subsection {The Pynchon Gate PIR Protocol}
+\label{subsec:PIR}
+
+The protocol runs as follows: after choosing distributors, the client
+establishes an encrypted connection to each
+(e.g., using TLS~\cite{rfc-2246}). These connections must be unidirectionally authenticated
+to prevent man-in-the-middle attacks, and can be made sequentially or in
+parallel.
+
+%FIXME \vec exclusive-or
+The client sends a different ``random-looking'' bit vector
+${\nu}_{s\beta}$ to each distributor $s$ for each message block $\beta$ to be retrieved. Each
+bit vector has a length equal to the number of message blocks in the database. Each
+distributor $s$ then
+computes $R(\nu_{s\beta})$ as the exclusive-\textsc{or} of all message blocks whose positions are set to $1$
+in $\nu_{s\beta}$. The resulting value is then returned to the client.
+
+Thus, in order to retrieve the $\beta$'th message block, the client need only choose
+the values of $\nu_{s\beta}$ such that when all $\nu_{s\beta}$ are \textsc{xor}ed together, all values are $0$ at every position except $\beta$. (For security, $\ell-1$ of the vectors should be generated
+randomly, and the bit vectors should be sent in a random order so that the $\ell$'th, specially-crafted vector cannot be identified as such.) When the client receives the corresponding $R(\nu_{s\beta})$ values, she
+can \textsc{xor} them to compute the message block's contents.
+%need only choose the values of v_{sB} such that when all v_{sB} are \textsc{xor}ed together, all values are 0 at every position except B.
+
+\subsection{Byzantine Server Protection}
+
+In a distributed-trust anonymity system such as the Pynchon Gate, there exists the possibility that some servers may be \emph{Byzantine}, i.e., they may behave incorrectly, either due to intentional malice or simple error.\footnote{This concern is present in many other anonymity systems, including Chaumian mix-nets~\cite{chaum-mix,mixmaster-spec,mixminion} and systems built on top of them~\cite{nym-alias-net,underhill-spec}.} In the case of the Pynchon Gate, the Byzantine behavior we are concerned with is an incorrect response to a PIR query of a distributor's database.
+
+All $n$ distributors in the system have the exact same copy of the database, and the system is designed such that any attempt by a Byzantine server to modify its response to the PIR query will be detected by the user when he verifies the root of the hash tree. This is crucial to preserving the anonymity properties of the system, for if an attacker can alter a message or observe the cleartext of a message, he may potentially be able to later link an input message with a given output retrieved by the nym holder.
+
+The Pynchon Gate's message and link encryption prevents an attacker from observing the cleartext of a message. Active attacks that are dependent upon the attacker's ability to alter some of the data being transmitted to the user such that the attacker may later link the user to his pseudonym based either on a variance in the user's response to altered versus unaltered data, or by simply recognizing the product of the altered data as it is processed by the system (collectively known as \emph{tagging attacks}~\cite{bh-us-03-sassaman-dingledine}) are ineffective, as TLS protects data integrity on the wire. Thus, any tagging attacks an attacker wished to attempt against a user would have to occur through the use of a corrupt distributor. To protect against the case where a distributor provides (intentionally or otherwise) an incorrect response to the PIR query, the client verifies that the hash of the message block it has received can be authenticated through the hash tree with the verified hash root.
+
+\section{A Remaining Byzantine Server Attack}
+
+We present the following attack not prevented by the hash tree verification system: a corrupt distributor can, through malice or error, create a denial of service attack on the system by responding with incorrect data to a client's query. While the client will detect that the message block is invalid after performing the final step of the PIR protocol in Subsection \ref{subsec:PIR}, and thus can conclude that \emph{some} server was Byzantine, the client cannot determine \emph{which} server or servers returned the incorrect response. The client cannot safely pass the message block contents (assuming they consist of anything other than garbage) to the user, lest the user's anonymity be potentially compromised.
+
+Furthermore, if attacks on portions of the pseudonymity infrastructure affect some users differently than others, an attacker may exploit such attacks on components of the system to facilitate an intersection attack against a user of the system as a whole~\cite{usability:weis2006}. In the Pynchon Gate, if a Byzantine distributor selectively performed denial of service attacks against certain users by returning garbage results to their queries, but correctly responded to other users' queries, the attacker would increase his chances of learning the identity of certain users, based on which users responded to messages that were successfully delivered.\footnote{This type of attack is present (in a slightly different form) in non-PIR-based nym server systems as well. For instance, in a reply-block system, an attacker could disable certain mixes and observe which nyms ceased receiving traffic. If the nym holder has a fixed-route reply-block, this would enable the attacker to identify the mixes used in the nym holder's reply-block path, and increase his chances of successfully linking the nym with the nym holder's true name~\cite{trickle02}.} In other cases, a passive adversary could observe the actions of Byzantine servers not under his control (and perhaps not even behaving maliciously, but simply incorrectly) to help facilitate intersection attacks~\cite{wright03}. Additionally, if a user cannot know with confidence which server is behaving in a Byzantine fashion, she is more likely to change the nodes she uses on a regular basis, both increasing her exposure to long-term intersection attacks and increasing the probability of selecting a server-set that consists of nodes operated entirely by a single adversary.
+
+\section{Byzantine Server Detection}
+
+Ideally, there would exist a way to identify a Byzantine server without modifying the existing threat model or positive security properties of the Pynchon Gate. This is a challenging problem to solve with the existing \textsc{xor}-based PIR protocol, which makes verifying the results of a PIR query returned by a specific distributor impossible. (The client does not know what a ``correct'' response $R(\nu_{s\beta})$ from any given distributor should look like; only that $$R(\nu_{s_1\beta}) \oplus R(\nu_{s_2\beta}) \oplus \cdots \oplus R(\nu_{s_\ell\beta}) = \beta'th~\text{message block}$$ and thus cannot identify which of the responses were invalid.)
+
+\subsection{An Attempt to Improve the Robustness of the Pynchon Gate}
+
+In his recent paper~\cite{goldberg-2007}, Goldberg suggests that detection of Byzantine servers in the Pynchon Gate should be addressed using a PIR protocol with a different underlying primitive than the one originally proposed. As a replacement to the \textsc{xor}-based Pynchon Gate Protocol (PynGP), he offers a novel Byzantine-robust PIR protocol based on Shamir secret sharing~\cite{shamir-secret}, similar to that proposed by Beimel and Stahl~\cite{beimel-robust} in that only $k$ out of a total $\ell$ servers in the network need to respond, and no server coalition of up to $t$ servers can learn anything about the query. Furthermore, as in the protocol presented by Beimel and Stahl, Goldberg's protocol offers \emph{Byzantine robustness}; some servers may respond with incorrect answers to a given query, and the user can still reconstruct the proper results of the query. The protocols of interest for our problem presented in~\cite{beimel-robust} and~\cite{goldberg-2007} are termed \textbf{$t$-private $v$-Byzantine-robust $k$-out-of-$\ell$ PIR}.\footnote{In discussion of this prior work, we limit our focus to the PIR protocols suggested in~\cite{goldberg-2007} as suitable alternatives to the protocol described in~\cite{pynchon,pynchon-spec}. \cite{beimel-robust} presents several different varieties of PIR protocols in addition to the type that~\cite{goldberg-2007} has proposed for use with the Pynchon Gate, and we will not address them here. \cite{goldberg-2007} presents an extension to its primary PIR protocol such that, if this extension is used, no coalition of up to \emph{$\tau$ servers} can know the contents of the database distributed among them. This property, termed \textbf{$\tau$-independent PIR} by Gertner et al.~\cite{tau-indy}, is not required in the case of the Pynchon Gate, for the security of the system is not predicated upon the contents of the database being kept a secret, as anyone may request any message block contained in the database. Secrecy of the database is instead handled by an encryption protocol at the nym-server and collator components; if a user requests a message block for which he does not hold the correct short-term shared secret, he will be unable to decrypt and obtain its contents. Similarly, distributors do not hold any of the shared secrets or derived subkeys necessary for decryption of the message block contents; therefore, collusion among distributors is irrelevant when considering message content secrecy.} Goldberg presents a strict improvement over the previous result for this type of PIR protocol (except, as he notes, when $(t,k) = (1,4)$, where it is the same) by presenting a $t$-private $v$-Byzantine-robust $k$-out-of-$\ell$ PIR protocol for any $0 < t < k$ and $v < k - \lfloor \sqrt{kt} \rfloor$~\cite{goldberg-2007}.
+
+One advantage to using a $t$-private $k$-out-of-$\ell$ PIR scheme over using PynGP (itself an \textbf{information-theoretic ($\ell-1$)-private $\ell$-server PIR} protocol) is that the user need not know which databases are online at the time she makes her request. Indeed, $t$-private $k$-out-of-$\ell$ PIR schemes handle the situation where some servers $n$ (where $n < k$) crash while the request is being made, such that the user is still able to obtain the results to her query in an expedient fashion.\footnote{From a usability standpoint, this is superior to the existing PynGP, where the user is not permitted to re-request his mail, and encouraged to be patient -- undelivered mail will remain in the system for later retrieval.}
+
+Unfortunately, $t$-private $k$-out-of-$\ell$ PIR protocols such as those based on Shamir secret sharing force a trade-off between the number of servers that may collude before the system is compromised, and the number of servers that may be Byzantine without affecting the user's ability to obtain the results of her query. (In a $t$-private $k$-out-of-$\ell$ PIR scheme, any $t+1$ may collude to break the security of the system, as long as those $k$ servers all received a valid query from the user. Thus, the maximum collusion protection such a system can offer is where $t$ = ($k-1$).) An ($\ell-1$)-private $\ell$-server PIR protocol is equivalent to a $t$-private $k$-out-of-$\ell$ PIR scheme, where $t$ = ($\ell-1$) and $k$ = $\ell$. Since it is the case that when availability guarantees (inversely proportional to $k$) are increased, the threshold at which \emph{any} query at \emph{any} time may be compromised by colluding servers is diminished in response, the decision must be made as to how critical for a given use case it is that the system respond with a correct answer in the face of sudden node failure. This permits a safe trade-off between availability of service and the security of the system. In the case of a service offering persistent pseudonyms, we consider intermittent and infrequent service interruptions to be the lesser concern.
+
+%Unfortunately, $t$-private $k$-out-of-$\ell$ PIR protocols such as those based on Shamir secret sharing force a trade-off between the number of servers that may collude before the system is compromised, and the number of servers that may be Byzantine without affecting the user's ability to obtain the results of her query. (In a $t$-private $k$-out-of-$\ell$ PIR scheme, any $t+1$ may collude to break the security of the system, as long as those $k$ servers all received a valid query from the user. Thus, the maximum collusion protection such a system can offer is where $t$ = $k-1$.) An ($\ell-1$)-private $\ell$-server PIR protocol is equivalent to a $t$-private $k$-out-of-$\ell$ PIR scheme, where $t$ = ($\ell-1$) and $k$ = $\ell$. Therefore, the decision must be made as to how critical for a given use case it is that the system respond with a correct answer in the face of sudden node failure, so that a safe trade-off may be made between availability of service and the security of the system. Since it is the case that when availability guarantees are increased, the threshold at which \emph{any} query at \emph{any} time may be compromised by colluding servers is diminished in response. In the case of a service offering persistent pseudonyms, we consider intermittent and infrequent service interruptions to be the lesser concern.
+
+
+The author of~\cite{goldberg-2007} addresses this serious concern by introducing an extension to his $t$-private $v$-Byzantine-robust $k$-out-of-$\ell$ PIR protocol that provides \emph{computational security} protection for the results of a query, even in the case that \emph{all servers} collude, by proposing a hybrid privacy protection scheme which relies on the \emph{Paillier additive homomorphic cryptosystem}~\cite{pailli99}. This extension gives a PIR protocol with $t$-private $v$-Byzantine-robust $k$-out-of-$\ell$ information-theoretic protection and $\ell$-computational protection. However, as the author states, adding this modification is quite expensive. While the rest of the protocol performs rather efficiently (and better than previous results, under certain configurations), the CPIR hybrid extension suffers the same problem as all other currently existing CPIR solutions. For each $n$-bit word in the database, the server must perform a modular exponentiation operation. Based on the performance calculations in~\cite{goldberg-2007}, we do not believe this satisfies the goals of \emph{deployability} and \emph{usability} as set forth in Section 1.0.1 of the Pynchon Gate design paper~\cite{pynchon}. The concept of a hybrid information-theoretic/computational PIR scheme is quite promising, should a CPIR scheme be proposed with affordable computation requirements. Until that happens, though, we are forced to discount the $\ell$-computational protection extension to the protocol in~\cite{goldberg-2007}, as it is presently impractical given real-world resource constraints. This leaves the protocol of~\cite{goldberg-2007} able to identify Byzantine servers at the cost of reduced overall security as compared to PynGP. A decision to deploy the protocol as suggested in~\cite{goldberg-2007} would require considering this overall weakening of the security model.\footnote{Changing the security model from ($\ell-1$)-private $\ell$-server PIR to $t$-private $k$-out-of-$\ell$ PIR substantially violates one of the original design goals of the Pynchon Gate. While it is now known that communication through a mix network is unlikely to be secure in the scenario where all but one of the nodes are compromised~\cite{e2e-traffic}, at the time that the Pynchon Gate design paper was written, this was optimistically considered to be true under some threat models. Thus, when the authors of the Pynchon Gate design paper stated ``we want the Pynchon Gate to resist active and passive attacks at least as well as the state of the art of forward message anonymity''~\cite{pynchon} , it can safely be assumed that they had an ($\ell-1$)-private $\ell$-server PIR protocol in mind as a partial means to achieving this goal. As the Pynchon Gate does not provide a mechanism for forward message delivery, however, one should consider that the overall system is only as strong as its constituent parts, and ($\ell-1$)-private $\ell$-server information-theoretic PIR is arguably substantially more secure than mix networks~\cite{chaum-mix,remailer-history,hal-remailer,mixmaster-spec,fsmix03,mixminion,mixencrypt,minx}, for reasons too numerous to elaborate in this work~\cite{back01,mixmaster-reliable,limits-open,wright02,hitting-set04}.}
+
+\section{A Novel Solution to the Byzantine Postman Problem}
+
+We propose a solution to the Byzantine Postman Problem which preserves the original threat model established for the original Pynchon Gate Protocol (henceforth referred to as PynGP 1.0). Described below, our revised PynGP (PynGP 2.0) protocol relies only on additional sets of operations already performed by PynGP 1.0, yet this modified version of PynGP 1.0 allows for the detection and identification of Byzantine nodes with sufficient probability that our denial of service attack against the PynGP 1.0 is no longer feasible in practice. Furthermore, while it increases the amount of communication bandwidth needed to perform PynGP operations, the communcation overhead is still within the realm of affordability for the target user and operator demographic stated in~\cite{pynchon}.
+
+\subsection{PynGP 2.0}
+
+We have modified PynGP 1.0 only as much as necessary to address its known security flaws. The revised version of the protocol retains the same security properties set forth in the original design paper. We address the issue of Byzantine nodes by introducing a \emph{cut-and-choose} methodology~\cite{Rabin77,min-disclosure}. To support this addition, we modify the query algorithm and add a response validation algorithm (to be run if the reconstruction algorithm fails) at the cost of trivial computation expense and a doubling in the bandwidth needed to perform queries of the database.\footnote{While this is indeed a significant increase in system overhead, it is still feasible, especially given the Pynchon Gate's resource tuning properties which permit a linear trade-off between bandwidth and storage, adjusted simply by changing the size of the message blocks stored in the database. Doubling the size of the message blocks halves the bandwidth necessary to perform a query.} Finally, we introduce a new component in the Pynchon Gate architecture, known as the \emph{validator}.
+
+Thus, PynGP 2.0 is identical to PynGP 1.0 as described in Subsection \ref{subsec:PIR}, with the following modifications to the protocol:
+
+Each time the protocol runs, the client prepares two sets of bit vectors to send to the chosen distributors. The first set, $\alpha$, is used to obtain the private mailbox data via the PIR protocol; the second set, $\eta$, consists entirely of randomly generated bit vectors and is used to challenge the honesty of each distributor.
+
+At the step in the PynGP 1.0 protocol where the client would transmit the ``random-looking'' bit vector to each distributor, the client submits two ``random-looking'' bit vectors instead, one from $\{\alpha\}$ and one from $\{\eta\}$, transmitted in a random order.
+
+Upon receiving these bit vectors, the distributor performs the operations as described in Subsection \ref{subsec:PIR}, and then returns two responses, in the same order which the requests were received (or otherwise in such a manner that the responses are linkable to the requests which generated them). The client caches the response for the $\{\eta\}$ request, then performs the PIR operation as previously described using the $\{\alpha\}$ results from all distributors.
+
+We now introduce a new component in the Pynchon Gate architecture, known as the \emph{validator}. This component is essentially a distributor, except that it only exists to confirm that the other distributors are not Byzantine. This specialized distributor validates the ``cut-and-chosen'' responses as being correct, deterring the operation of Byzantine nodes and probabilistically uncovering them should they exist. The validator must be operated by the same entity who operates the collator, since the operator of the collator is already empowered to perform a denial of service attack by turning off the server running the collator. Ergo, the balance of power in this distributed trust system is maintained by placing the validator (whose operator could also force a denial of service attack, though not as easily) under the control of the same entity. Note that communication with the validator occurs over an encrypted link, just as with normal distributors.
+
+The responses from set $\{\eta\}$ (while possibly able to return a valid mailbox) are not of interest to the client for their contents. Instead, these responses are cached by the client, along with the corresponding request that was sent to the distributor to generate them as well as an identifier for the distributor which returned the responses. To verify that a distributor is not attempting to behave in a Byzantine manner, the same bit vectors in $\{\eta\}$ that had been submitted to each distributor can subsequently be submitted to the validator, and the validator should return a response identical to that which the original distributor returned for each request. (The entire $\{\eta\}$ needs to be submitted, as there may be multiple Byzantine servers acting simultaneously.) Should the validator return a response that differs from the one received by the client from a given distributor, that distributor should be suspected of being Byzantine.\footnote{Strictly speaking, the $\{\eta\}$ vectors should always be sent to the validator, regardless of the outcome of the PIR operation using the $\{\alpha\}$ results, to guard against the scenario where an additional adversary not in collusion with the Byzantine server might learn additional information about the state of the network. However, this level of paranoia may not be affordable until bandwidth and computation become less expensive.}
+
+%The client should avoid sending the entire set at once, however. Instead, each element should be submitted at a metered pace to avoid excessive load on the valiator.
+As proposed above, this protocol gives a Byzantine server a 50\% chance of being discovered each time it attempts to behave in a Byzantine manner. That threshold can be increased at the expense of greater bandwidth overhead; however, we feel that a 50\% detection rate is sufficient to deter this sort of attack, due to the inherent reputation system involved with the distributor network. (One Byzantine action by a distributor \emph{verifiable as such} to the collator, validator, or nym server operator should be sufficient to blacklist a Byzantine distributor. Care must be taken to ensure that an attacker does not frame an honest server as Byzantine to have it blacklisted. Multiple reports identifying a given server as Byzantine might simply indicate a Sybil attack being performed to achieve the blacklisting.)
+
+\section{Remarks on Performance}
+As previously stated, PynGP 2.0 has a higher performance cost than its predecessor. We have attempted to strike a balance between security and excessive resource consumption when the security issues are unlikely to be problematic, or the resource requirements too great to qualify the protocol as ``deployable''. Areas where security could be increased, if performance cost were no object, include the addition of more than a single challenge-vector set to decrease the probability of a Byzantine server successfully avoiding detection.\footnote{For $n$ challenge-vector sets, the probability of avoiding detection is $\frac{1}{n+1}$.} Also, as previously noted, it would be ideal, were it affordable, for the challenge-vectors to be validated every time a PynGP protocol run was performed. This is likely cost-ineffective, though, given that knowledge of the user's failure to validate the hash root is unlikely to give an adversary any significant advantage, let alone lead to a user-level privacy vulnerability.
+%This is likely too resource-intensive to be warranted given the low likelihood that knowledge of the user's failure to validate the hash root on the result returned by the system could lead to a user-level privacy vulnerability.
+ It is far more important that all clients in the system behave according to the same policy in this regard. Also, if the number of challenge-vector sets is increased, the cost of validation increases proportionally.
+
+The resource requirements for the validator must be more fully investigated, and will not truly be known until the system is tested in a live environment with actual Byzantine nodes. It is conceivable that the validator might best be deployed as multiple load-balanced servers, should the level of resource consumption warrant it. It is also conceivable that there may be few to no challenge validations necessary under normal conditions. When challenge validations are required, however, the bandwidth cost per challenge is non-trivial. (The validator receives ($r \cdot \ell$) bits from a given client, and returns ($n \cdot \ell$) bytes, where $r$ is the number of message blocks (and thus the length of any given bit vector) and $n$ is the size of a message block.) Though a client must validate its challenge-set in its entirety, the client should avoid sending the entire set at once, however. It is advisable to submit each element of the challenge-set to the validator successively, so that the validator can impose rate-limiting on the incoming validation requests to cope with instances of sudden high load.
+
+The ability to gracefully address the issue of Byzantine nodes is itself an anti-Byzantine measure; it has been suggested that when the Pynchon Gate is first deployed, it use PynGP 1.0 until evidence of the existence of Byzantine servers in the system is observed~\cite{bram-chat}. It is possible that merely having PynGP 2.0 implemented in the software and able to be enabled instantly could serve as a deterrent to a casual attacker whose goal is to deny service to the system, as the only effect such an attacker would have by deploying a Byzantine node would be to increase the network communication and verifier computation costs to a level that we have already deemed acceptable.
+
+%\section{Attacking PIR-based Pseudonym Services via Tagging Attacks and User Oracles}
+%\subsection{Attacking Beimel-Stahl}
+%\subsection{Attacking Goldberg}
+%FIXME challenge-vector vs. challenge vector; cite bram-chat; figs.
+
+\section{Conclusions}
+We have reviewed the attack we first described in~\cite{cosic-2007-001}, and have show that it has significant impact on the deployability and potential success of the Pynchon Gate, as well as other PIR-based nym server systems which do not account for Byzantine servers. A denial or degradation of service attack would be nearly impossible to thwart, and would likely happen soon after the system became popular among users. This vulnerability must not be present in the public system if it is to be expected to achieve and maintain any level of popularity or substantial user-base.
+
+We have examined the solution proposed by Goldberg in~\cite{goldberg-2007} to address this vulnerability. We show that the trade-offs made in Goldberg's proposal do not satisfy the the security requirements set forth for the Pynchon Gate in its original design paper, as Goldberg's core protocol weakens the security assumptions significantly compared to the original PynGP. We show, using the performance metrics provided in~\cite{goldberg-2007}, that the proposed extension offered by the author to sufficiently strengthen the protocol to an adequate security level, while a groundbreaking idea in the theory of PIR, fails the engineering requirements for the Pynchon Gate: namely, it is too costly for volunteer operators to be expected to operate, and thus in practice, the security of the Pynchon Gate would rely on the weaker core protocol presented in~\cite{goldberg-2007}, without the addition of the stronger computational PIR-based protocol extension.
+
+We then show that we can modify the original PynGP 1.0, relying on nothing more than an additional set of operations already performed by the original PynGP 1.0, and that this new version of PynGP (PynGP 2.0) allows for the detection and identification of Byzantine nodes with sufficient probability that the denial of service attack against the PynGP 1.0 is no longer feasible. PynGP 2.0 requires no weakening of the original security model, and while it increases the bandwidth communication overhead, the bandwidth costs are still reasonable enough to fall within the engineering requirements of the original Pynchon Gate design goals: namely, that the system's bandwidth requirements be inexpensive enough to be reasonable for both users and system operators.
+
+With the addition of PynGP 2.0, we consider the Pynchon Gate design to be superior to any other high-latency pseudonym service offering strong privacy properties currently proposed in the literature.
+
+\section{Future Work}
+
+The ``cut-and-choose'' Byzantine protection in PynGP 2.0 provided by the set of challenge bit-vectors $\{\eta\}$ is possibly not as efficient as it could be. The security implications of a modified validator protocol should be explored, perhaps with inspiration from sister disciplines, such as digital cash authenticity verification~\cite{ChaumFiNa88}, secure secrecy-preserving auctions~\cite{parkes-auction}, or randomized partial checking in mix networks for voting applications~\cite{randomized-checking}.
+
+Using the PynGP 2.0 protocol, users can detect when a given server has behaved in a Byzantine fashion. However, they have no irrefutable way of proving this to a third party. We have considered a scenario where the distributors always return a signed response to a PIR query, but there is no reason why a Byzantine server would not simply refuse to sign (or more likely, sign incorrectly) data it wished to later repudiate. Until an adequate solution which enables the user to prove a given flawed response came from a particular server is available, distributor reputation is likely to be dictated by consensus.\footnote{However, it may be a positive property that signing is not used in this way, as this permits a wider degree of repudiation on the part of the user with regard to her received messages.}
+
+The security implications of permitting users to recover from Byzantine failures (and obtain their data, even when some number of responding distributors are known to be Byzantine) are not well studied. It is our intuition that an attacker, particularly one with access to at least two colluding distributors, could manipulate his responses such that some users were able to pass the recovery step, and others unable to, and in this manner the attacker could use the user as an oracle and gain information based on his actions.
+
+The prototype Pynchon Gate system needs to be deployed and performance tested, and user-studies must be performed to evaluate its success from a deployability and usability standpoint.
+
+% The resource requirements for the new architectural component validator need to be more fully investigated, and won't truly be known until the system is tested in a live environment with actual Byzantine nodes. It is conceivable that the validator might actually be multiple validators in a
+
+
+\section{Acknowledgements}
+
+We would like to thank Brian Warner and Bryce Wilcox-O'Hearn for their helpful early discussions of the Byzantine Postman Problem; Ian Goldberg for suggesting the potential of polynomial interpolation-based PIR solutions; Orr Dunkelman, Meredith L. Patterson, and Julia Wolf for informative discussions of $t$-private $k$-out-of-$\ell$ PIR schemes; Elena Andreeva, Ian Goldberg and David Molnar for assistance in searching the literature for pertinent work; and David Chaum, Bram Cohen and Meredith L. Patterson for inspirational discussion of PynGP 2.0.
+
+We would also like to especially thank Nikita Borisov, David Chaum, Shar van Egmond, and Meredith L. Patterson for their advice and support during the course of this research.
+
+This work was supported in part by the Concerted Research Action (GOA) Ambiorics 2005/11 of the Flemish Government and by the IAP Programme P6/26 BCRYPT of the Belgian State (Belgian Science Policy). Len Sassaman's work was supported in part by the EU within the PRIME Project under contract IST-2002-507591.
+
+\bibliographystyle{plain}
+\bibliography{byzantine-fix}
+\end{document}
\ No newline at end of file
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/