On-line papers and talks:  Recent Papers, By topic, Technical  Reports.

All On-Line Papers

        M. Ajtai, J. Aspnes, M. Naor, Y. Rabani, L. Schulman and O. Waarts, Fairness in Scheduling, J. Algorithms 29(2), 1998, pp. 306-357. Abstract, Postscript, gzipped Postscript, PDF. Slides for a related lecture: pps.

        Noga Alon and Moni Naor, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Algorithmica, vol 16, 1996, pp. 434-449. Abstract, Postscript, gzipped Postscript.

PDF,

        Cuckoo Hashing:

o   Yuriy Arbitman, Moni Naor and Gil Segev, De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results, Abstract, PDF.

o   Yuriy Arbitman, Moni Naor and Gil Segev, Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation, Abstract, PDF. Slides: pptx.

o    Slides in Hebrew (Shimon Even Memorial talk)

        Mihir Bellare, Russell Impagliazzo and Moni Naor, Does Parallel Repetition Lower the Error in Computationally Sound Protocols? FOCS 1997. Abstract, Postscript, gzipped Postscript, PDF. Slides: Postscript.

        Matt Blaze, Joan Feigenbaum and Moni Naor, A Formal Treatment of Remotely-Keyed Encryption, Eurocrypt 1998. Abstract, Postscript, gzipped Postscript, PDF. Slides: Postscript.

        Memory Checking

o   Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, Moni Naor, Checking the Correctness of Memories, Algorithmica 12(2/3): 225-244 (1994), Postscript, gzipped Postscript

o   Moni Naor and Guy N. Rothblum, The Complexity of Online Memory Checking, JACM 2009. Abstract, Full Version: Postscript, gzipped Postscript, PDF.

o   Moni Naor and Guy N. Rothblum, Simulating Secret Knowledge: The Learnability of Adaptively Changing Distributions, or Learning to Impersonate, ICML 2006. Abstract, Full Version: Postscript, gzipped Postscrip, PDF.

o   Cynthia Dwork, Moni Naor, Guy N. Rothblum and Vinod Vaikuntanathan, How Efficient can Memory Checking be?, TCC 2009. Abstract, Postscript, gzipped Postscript, PDF.

        Dan Boneh and Moni Naor Timed Commitments and Applications, Crypto 2000. Abstract, Postscript, gzipped Postscript

        Zvika Brakerski and Moni Naor, Fast Algorithms for Interactive Coding, SODA 2013, PDF

        Ran Canetti, Cynthia Dwork, Moni Naor and Rafi Ostrovsky, Deniable Encryption, Crypto 97. Abstract, Postscript, gzipped Postscript, PDF.

        Ran Canetti, Uri Feige, Oded Goldreich and Moni Naor, Adaptively Secure Multi-party Computation or Non-Commiting Encryption, STOC 1996, Abstract, Postscript, gzipped Postscript, PDF.

        Ran Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor and B. Pinkas, Issues in Multicast Security: A Taxonomy and Efficient Constructions, Proc. of INFOCOM '99, New York, NY, March 1999. Postscript, gzipped Postscript, PDF.

        Danny Dolev, Cynthia Dwork and Moni Naor, Non-Malleable Cryptography, Siam J. on Computing 30(2), 2000, pp. 391-437.

        Abstract, Postscript, gzipped Postscript.
A Taxonomy of Encryption Scheme Security - Slides of a talk Postscript, gzipped Postscript.
Non-Malleability: An Introduction and Survey of Recent Developments, Postscript, gzipped Postscript, PDF.
(Written circa 2003 for an introduction to the SIAM Review republication of the paper.)

        Differential Privacy

o   Cynthia Dwork and Moni Naor, On the Difficulties of Disclosure Prevention in Statistical Databases or The Case for Differential Privacy. Abstract, Postscript, gzipped Postscript, PDF.

o   Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov and Moni Naor, Our Data, Ourselves: Privacy via Distributed Noise Generation, Eurocrypt 2006. Abstract, Postscript, gzipped Postscript, PDF.

o   Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum, and Salil Vadhan, On the Complexity of Differentially Private Data Release, STOC 2009, Abstract, PDF.

o   Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum and Sergey Yekhanin, Pan-Private Streaming Algorithms, in Proceedings of The First Symposium on Innovations in Computer Science (ICS 2010), Abstract, PDF.

o   Cynthia Dwork, Moni Naor, Toniann Pitassi and Guy N. Rothblum, Differential Privacy Under Continual Observation, STOC 2010, Abstract, PDF.

o   Cynthia Dwork, Moni Naor and Salil Vadhan, The privacy of the analyst and the power of the state, FOCS 2012, Abstract, PDF.

        Spam fighting and abuse prevention via pricing functions

o   Cynthia Dwork and Moni Naor, Pricing via Processing or Combatting Junk Mail,  Abstract, Postscript, gzipped Postscript, PDF.

o   Cynthia Dwork, Andrew Goldberg and Moni Naor, On Memory-bound Functions for Fighting Spam, Crypto 2003. Abstract, Postscript, gzipped Postscript, PDF.

o   Cynthia Dwork, Moni Naor and Hoteck Wee, Pebbling and Proofs of Work, CRYPTO 2005, 37-54. Abstract, Postscript, gzipped Postscript, PDF.

        Cynthia Dwork and Moni Naor, An Efficient Existentially Unforgeable Signature Scheme and Its Applications, Journal of Cryptology, Vol 11, Number 2, 1998, pp. 187-208. Postscript, gzipped Postscript

        Cynthia Dwork and  Moni Naor>, Zaps and Their Applications, SIAM J. Computing 36(6): 1513-1543, 2007 (FOCS 2000), Abstract, Postscript, gzipped Postscript, PDF. Slides: ppt.

        Cynthia Dwork, Ravi Kumar, Moni Naor and D. Sivakumar, Rank aggregation methods for the Web, WWW10, 2001. Abstract, HTML .

        Cynthia Dwork, Jeff Lotspiech and Moni Naor, Digital Signets: Self-Enforcing Protection of Digital Information, Proc. 28th Ann. ACM Symp. on Theory of Computing, 1997. Abstract, Postscript, gzipped Postscript

        Cynthia Dwork, Moni Naor, Omer Reingold, Immunizing Encryption Schemes from Decryption Errors, Proc EUROCRYPT 2004, 342-360 Abstract, Postscript, gzipped Postscript, PDF . Slides: ppt.

        Cynthia Dwork, Moni Naor, Omer Reingold and Larry Stockmeyer, Magic Functions, Journal of the ACM 50(6), (November 2003), 852-921. Postscript , gzipped Postscript

        Cynthia Dwork, Moni Naor and Amit Sahai, Concurrent Zero-Knowledge or The Timing Model for Designing Concurrent Protocols, Journal of the ACM, vol. 51(6), 2004, pp. 851--898 (Prel. version STOC 1998). Abstract, Postscript, gzipped Postscript

        Ron Fagin, Amnon Lotem and Moni Naor, Optimal aggregation algorithms for middleware.  J. Comput. Syst. Sci. 66(4), 614--656 2003 (PODS 2001 issue). Abstract, full version:  Postscript, gzipped Postscript, PDF . Slides: ppt.

        Ron Fagin, Moni Naor and Peter Winkler, Comparing Information Without Leaking It, Communications of the ACM, vol 39, May 1996, pp. 77-85. Abstract, Postscript, gzipped Postscript.

        Uri Feige, Joe Kilian and Moni Naor, A Minimal Model for Secure Computation, STOC 1994.  Postscript, gzipped Postscript, PDF.

        Amos Fiat and Moni Naor, Rigorous Time/Space Tradeoffs for Inverting Functions, SIAM J. Computing 29(3), 1999, pp. 790-803. Postscript, gzipped Postscript

        Ronen Gradwohl, Moni Naor, Benny Pinkas and Guy Rothblum, Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles, FUN 2007. Abstract, Postscript, gzipped Postscript, PDF.

        Ran Halprin and Moni Naor, Games for Extracting Randomness, Symposium On Usable Privacy and Security (SOUPS) 2009, Abstract, PDF. Slides: ppt.

        Danny Harnik and Moni Naor, On the Compressibility of NP Instances and Cryptographic Applications, FOCS 2006. Full paper: Abstract, Postscript, gzipped Postscript, PDF. Slides: ppt.

        Danny Harnik and Moni Naor, On Everlasting Security in the Hybrid Bounded Storage Model, ICALP 2006. Abstract, Postscript, gzipped Postscript, PDF.

        Danny Harnik, Joe Kilian, Moni Naor, Omer Reingold and Alon Rosen, On Robust Combiners for Oblivious Transfer and other Primitives, Eurocrypt 2005. Abstract, Postscript, gzipped Postscript. Slides: ppt.

        Danny Harnik, Moni Naor, Omer Reingold and Alon Rosen, Completeness in Two-Party Secure Computation - A Computational View. Abstract, Postscript, gzipped Postscript, PDF. Slides: ppt.

        Russell Impagliazzo and Moni Naor, Efficient Cryptographic Schemes Provably as Secure as Subset Sum,  Journal of Cryptology  9(4), 1996, pp. 199-216.   Postscript, gzipped Postscript.

        Eyal Kaplan, Moni Naor and Omer Reingold, Derandomized Constructions of k-Wise (Almost) Independent Permutations, Algorithmica 55()1, pp. 113-133, 2009 (Random 2005), Abstract, Postscript, gzipped Postscript, PDF. Slides: ppt.

        Joe Kilian and Moni Naor, On the Complexity of Statistical Reasoning, Abstract, Postscript, gzipped Postscript.

        Gillat Kol and Moni Naor, Games for Exchanging Information, STOC 2008, Abstract, Postscript, gzipped Postscript, PDF. Slides: ppt.

        Gillat Kol and Moni Naor, Cryptography and Game Theory: Designing Protocols for Exchanging Information, TCC 2008, Abstract, Postscript, gzipped Postscript, PDF.

        Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass and Alon Rosen, One-Way Functions and (Im)perfect Obfuscation, FOCS 2014, Abstract, PDF.

        Dalia Malkhi, Moni Naor and David Ratajczak, Viceroy: A Scalable and Dynamic Emulation of the Butterfly, Proc. 2002 PODC, Abstract, Postscript, gzipped Postscript, PDF

        Alain Mayer, Moni Naor and Larry Stockmeyer, Local Computations on Static and Dynamic Graphs. PDF, Postscript, gzipped Postscript.

        Ilya Mironov, Moni Naor and Gil Segev, Sketching in Adversarial Environments, SIAM J. Computing 40(6), pp. 1845-1870, 2011 (STOC 2008). Abstract, PDF. Slides: ppt.

        The Scratch-Off papers

o   Tal Moran and Moni Naor, Basing Cryptographic Protocols on Tamper-Evident Seals, ICALP 2005. Abstract, Postscript, gzipped Postscript, PDF.

o   Tal Moran and Moni Naor, Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol, Eurocrypt 2006. Abstract, Postscript, gzipped Postscript, PDF.

        Voting with Everlasting Privacy:

o   Tal Moran and Moni Naor, Receipt-Free Universally-Verifiable Voting With Everlasting Privacy, Crypto 2006, Abstract, Postscript, gzipped Postscript, PDF.

o   Tal Moran and Moni Naor, Split-Ballot Voting: Everlasting Privacy With Distributed Trust, ACM CCS 2007, PDF.

o   Talk on "Receipt-Free Universally-Verifiable Voting With Everlasting Privacy" by Tal Moran at Harvard

        Tal Moran, Moni Naor and Gil Segev, Deterministic History-Independent Strategies for Storing Information on Write-Once Memories, ICALP 2007.  Abstract, Postscript, gzipped Postscript, PDF. Slides: short talk (ppt), long talk (ppt).

        Tal Moran, Moni Naor and Gil Segev, An Optimally Fair Coin Toss. Abstract, Postscript, gzipped Postscript, PDF.

        Uri Nadav, Moni Naor, Fault Tolerant Storage in a Dynamic Environment, Proc. Disc 2004. Postscript, gzipped Postscript.

        Dalit Naor, Moni Naor and Jeff Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Abstract, Postscript, gzipped Postscript, PDF, PDF (no figures) . Slides of talk on the subject: ppt

        Moni Naor, Evaluation May Be Easier Than Generation, Proc. STOC 1996, Abstract, Postscript, gzipped Postscript

        Moni Naor, Verification of a human in the loop or Identification via the Turing Test, Abstract, Postscript, gzipped Postscript, PDF.

        Moni Naor, Deniable Ring Authentication, Crypto 2002. AbstractPostscriptgzipped PostscriptPDF

o   Also see Open Day 2005 talk: Cryptography and Complexity at the Weizmann Institute, Slides: ppt

        Moni Naor, On Fairness in the Carpool Problem, J of Algorithms 55(1), 2005, pp. 93-98. Abstract, Postscript, gzipped Postscript, PDF. Slides for a related talk: pps.

        Moni Naor and Kobbi Nissim, Certificate Revocation and Certificate Update, 7th USENIX Security Symposium, 1998. Postscript, gzipped Postscript.

        Moni Naor and Kobbi Nissim, Communication Preserving Protocols for Secure Function Evaluation, STOC 2001. Full version: Postscript, gzipped Postscript.

        Moni Naor, Rafi Ostrovsky, Ramarathnam Venkatesan and Moti Yung, Perfect Zero-Knowledge Arguments for NP Using any One-Way Permutation, J. of Cryptology, 11(2), 1998, pp. 87-108. Abstract, Postscript, gzipped Postscript, PDF.

        Moni Naor and Benny Pinkas, Secure and Efficient Metering , Eurocrypt 98, Abstract, Postscript, gzipped Postscript, PDF.

        Moni Naor and Benny Pinkas, Threshold Traitor Tracing, Crypto 98. Postscript, gzipped Postscript.

        Benny Chor, Amos Fiat, Moni Naor and Benny Pinkas, Tracing Traitors, IEEE Transactions on Information Theory, Vol. 46(3), pp. 893-910, 2000. Postscript, gzipped Postscript

        Moni Naor and Benny Pinkas, Trace and Revoke Schemes, Financial Crypto'2000. Abstract, Postscript, gzipped Postscript, PDF.

        Oblivious Transfer and Computation

o   Moni Naor and Benny Pinkas, Computationally Secure Oblivious Transfer, Crypto 99. Postscript, gzipped Postscript

o   Moni Naor and Benny Pinkas, Distributed Oblivious Transfer, ASIACRYPT 2000. Postscript, gzipped Postscript

o   Moni Naor and Benny Pinkas, Oblivious Polynomial Evaluation, Postscript, gzipped Postscript, PDF

o   Moni Naor and Benny Pinkas, Efficient Oblivious Transfer Protocols, Postscript, gzipped Postscript

o   Moni Naor, Benny Pinkas and Reuben Sumner, Privacy preserving auctions and mechanism design, ACM Conference on Electronic Commerce, 1999. Postscript, gzipped Postscript

        Visual Cryptography

o   Moni Naor and Adi Shamir, Visual Cryptography, Eurocrypt 94. Postscript, gzipped Postscript, PDF.

o   Moni Naor and Adi Shamir, Visual Cryptography II, Cambridge Workshop on Security Protocols, LNCS 1189, Springer, pp. 197-202, 1996. Postscript, gzipped Postscript

o   Moni Naor and Benny Pinkas, Visual Authentication, Crypto 97. Postscript, gzipped Postscript

        Moni Naor, Benny Pinkas and Omer Reingold, Distributed Pseudo-Random Functions and KDC. Eurocrypt'99. Abstract, Postscript, gzipped Postscript.

        Moni Naor and Omer Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions . J. of Computer and Systems Sciences, vol. 58 (2), April 1999, pp. 336-375. Abstract, Postscript, gzipped Postscript, PDF.

        Moni Naor and Omer Reingold, On the construction of pseudo-random permutations: Luby-Rackoff revisited, J. of Cryptology, vol 12, 1999, pp. 29-66. Extended abstract in: Proc. 29th Ann. ACM Symp. on Theory of Computing, 1997, pp. 189-199. Abstract, PDF, Postscript, gzipped Postscript.
The NR Mode of Operation Postscript, gzipped Postscript.

        Moni Naor and Omer Reingold, Number-Theoretic constructions of efficient pseudo-random functions,  J. ACM 51(2): 231-262 (2004). Abstract, PDF, Postscript, gzipped Postscript.
Implementation (Mike Langberg)

        Moni Naor and Omer Reingold, From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs, Crypto'98. Abstract, PDF, Postscript, gzipped Postscript.

        Moni Naor and Omer Reingold,  Constructing Pseudo-Random Permutations with a Prescribed Structure, J. of Cryptology, vol 14, 2001. Abstract, PDF, Postscript, gzipped Postscript. Slides: ppt

        Moni Naor, Omer Reingold and Alon Rosen, Pseudo-Random Functions and Factoring,  SIAM J. Computing, vol 31(5), 2002, pp. 1383--1404, (STOC 2000), Abstract, PDF, Postscript, gzipped Postscript.

        Moni Naor and Ronny Roth, Optimal File Sharing in Distributed Networks, SIAM J. Computing 24(1), pp. 158-183, 1995. PDF, Postscript, gzipped Postscript.

        Moni Naor and Sitvnit Ruah, On the Decisional Complexity of Problems Over the Reals, Information and Computation, vol 167(1) pp. 27-45, 2001 (special issue of ISTCS 1996). PDF

        Moni Naor, Leonard J. Schulman and Aravind Srinivasan, Splitters and near-optimal derandomization, Proc. of the 36th IEEE Symp. on Foundations of Computer Science, pp. 182-191. Postscript, gzipped Postscript, PDF,

        Moni Naor and Gil Segev, Public-Key Cryptosystems Resilient to Key Leakage. Abstract, PDF.

        Moni Naor, Gil Segev and Adam Smith, Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models, CRYPTO 2006. Abstract, PDF. Slides: ppt

        Moni Naor, Gil Segev and Udi Wieder, History-Independent Cuckoo Hashing, ICALP 2008. Abstract, Postscript, gzipped Postscript, PDF. Slides: ppt.

        Moni Naor and Larry Stockmeyer, What Can be Computed Locally, SIAM J. Computing. 24(6), pp. 1259-1277, 1995. PDF, Postscript, gzipped Postscript.

        Moni Naor and Vanessa Teague,  Anti-persistence: History Independent Data Structures, Proc. 33rd ACM Symp. on Theory of Computing, 2001. Abstract, Postscript, gzipped Postscript, PDF. Slides: ppt.

        Moni Naor and Udi Wieder, Novel Architectures for P2P Applications: the Continuous-Discrete Approach, Proc. SPAA 2003. Postscript, gzipped Postscript, PDF.

        Moni Naor and Udi Wieder, A Simple Fault Tolerant Distributed Hash Table, Proc. IPTPS 2003, Lecture Notes in Computer Science 2735, Springer, pp. 88-97, Postscript, gzipped Postscript, PDF.

        Moni Naor and Udi Wieder,  Scalable and Dynamic Quorum Systems, Distributed Computing, Vol. 17(4), pp. 311-322 2005 (PODC 2003), Postscript, gzipped Postscript, PDF.

        G. S. Manku, M. Naor and U. Wieder, Know thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks, STOC 2004, PDF.

        Moni Naor and Avishai Wool, The Load Capacity and Availability of Quorum Systems, SIAM J. on Computing, April 1998. Abstract, Postscript, gzipped Postscript, PDF.

        Moni Naor and Avishai Wool, Access Control and Signatures via Quorum Secret Sharing, 5th ACM Conf. on Computer and Communication Security, 1996. Abstract, Postscript, gzipped Postscript, PDF.

        Moni Naor and Eylon Yogev, Tight Bounds for Sliding Bloom Filters, PDF.

Some Oldies (roughly, pre-Weizmann)...

Are You Sure?

Now at: J. of Craptology vol. 0(1), April 1999. Abstract, Postscript, gzipped Postscript, PDF.
Also see: The Puzzler page.

On-line papers:  Recent Papers,  By topicTechnical  Reports.

The Puzzler

To Moni Naor's home page.