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

All On-Line Papers

• Noga Alon, Omri Ben-eliezer, Yuval Dagan, Shai Moran, Moni Naor and Eylon Yogev, Adversarial Laws of Large Numbers and Optimal Regret in Online Classification, STOC 2021, Paper , Talk
• 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, PDF, Postscript,
• Cuckoo Hashing:
  • Yuriy Arbitman, Moni Naor and Gil Segev, De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results, Abstract, PDF.
  • Yuriy Arbitman, Moni Naor and Gil Segev, Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation, Abstract, PDF. Slides: pptx.
  • Slides in Hebrew (Shimon Even Memorial talk)
  • Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor, Hardness-Preserving Reductions via Cuckoo Hashing. J. Cryptology (2019), Abstract, PDF
• Prabhanjan Ananth, Aayush Jain, Moni Naor, Amit Sahai and Eylon Yogev, Universal Constructions and Robust Combiners for Indistinguishability Obfuscation and Witness Encryption, CRYPTO 2016. PDF.
• Amihood Amir, Oren Kapah, Tsvi Kopelowitz, Moni Naor, Ely Porat: The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets. SPAA 2016, Abstract, PDF
• Gilad Asharov, Moni Naor, Gil Segev, Ido Shahaf, Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. STOC 2016, Abstract, PDF
• 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
  • 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
  • Moni Naor and Guy N. Rothblum, The Complexity of Online Memory Checking, JACM 2009. Abstract, Full Version: Postscript, gzipped Postscript, PDF.
  • 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.
  • Cynthia Dwork, Moni Naor, Guy N. Rothblum and Vinod Vaikuntanathan, How Efficient can Memory Checking be?, TCC 2009. Abstract, Postscript, gzipped Postscript, PDF.
• Elette Boyle and Moni Naor Is there an ORAM Lower Bound? ITCS 2016. Abstract, 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 Full version (merged with Brakerski-Kalai): J. ACM 2014, 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
  • 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.
  • Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov and Moni Naor, Our Data, Ourselves: Privacy via Distributed Noise Generation, Eurocrypt Abstract, Postscript, gzipped Postscript, PDF.
  • Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum, and Salil Vadhan, On the Complexity of Differentially Private Data Release, STOC 2009, Abstract, PDF.
  • 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.
  • Cynthia Dwork, Moni Naor, Toniann Pitassi and Guy N. Rothblum, Differential Privacy Under Continual Observation, STOC 2010, Abstract, PDF.
  • 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
  • Cynthia Dwork and Moni Naor, Pricing via Processing or Combatting Junk Mail, Abstract, Postscript, gzipped Postscript, PDF.
  • Cynthia Dwork, Andrew Goldberg and Moni Naor, On Memory-bound Functions for Fighting Spam, Crypto 2003. Abstract, Postscript, gzipped Postscript, PDF.
  • Cynthia Dwork, Moni Naor and Hoteck Wee, Pebbling and Proofs of Work, CRYPTO 2005, 37-54. Abstract, Postscript, gzipped Postscript, PDF.
• Spooky Interaction
  • Cynthia Dwork, Michael Langberg, Moni Naor, Kobbi Nissim and Omer Reingold Succinct Proofs for NP and Spooky Interactions, PDF
  • Cynthia Dwork, Moni Naor, Guy N. Rothblum: Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems. CRYPTO (3) 2016, Abstract, PDF
  • Moni Naor, Omer Paneth and Guy N. Rothblum, Incrementally Verifiable Computation via Incremental PCPs, TCC 2019.  Abstract, 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, 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.  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. 
• Ben Fisch, Daniel Freund and Moni Naor,
  • Physical zero-knowledge proofs of physical properties, Crypto 2014. Abstract, PDF.
  • Secure Physical Computation Using Disposable Circuits, TCC 2015. Abstract, PDF.
• 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.
• Tomer Grossman, Ilan Komargodski and Moni Naor, Instance Complexity and Unlabeled Certificates in the Decision Tree Model, Abstract, 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 (SIAM J. Computing 2010): 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.
• Pavel Hubacek, Moni Naor and Jon Ullman, When Can Limited Randomness Be Used in Repeated Games? Abstract, PDF. Slides: ppt.
• Pavel Hubacek, Moni Naor and Eylon Yogev, The Journey from NP to TFNP Hardness Abstract, 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.
• Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor and Uri Stemmer, Privately Learning Thresholds: Closing the Exponential Gap, COLT 2020, Paper , Talk
• 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, Alon Rosen and Eylon Yogev, One-Way Functions and (Im)perfect Obfuscation, FOCS 2014, Abstract, PDF.
• Secret Sharing
  • Ilan Komargodski, Moni Naor and Eylon Yogev, Secret Sharing for NP, Abstract, PDF. Slides: PDF.
  • Ilan Komargodski, Moni Naor and Eylon Yogev, How to Share a Secret, Infinitely Abstract, PDF. Slides: PDF.
  • Popular talk on secret sharing (Hebrew), Cryptography from Secrets to_Sharing: Slides, Video (Youtube)
• Ilan Komargodski, Moni Naor and Eylon Yogev, White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing PDF. Slides: PDF.
• Ilan Komargodski, Moni Naor, Eylon Yogev, Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions. EUROCRYPT 2018: 162-194. PDF. Slides: PDF.

• Dalia Malkhi, Moni Naor and David Ratajczak, Viceroy: A Scalable and Dynamic Emulation of the Butterfly, 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.
• Boaz Menuhin and Moni Naor, Keep That Card in Mind: Card Guessing with Limited Memory, Paper.
• 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
  • Tal Moran and Moni Naor, Basing Cryptographic Protocols on Tamper-Evident Seals, ICALP 2005. Abstract, Postscript, gzipped Postscript, PDF.
  • Tal Moran and Moni Naor, Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol, Eurocrypt Abstract, Postscript, gzipped Postscript, PDF.
• Voting with Everlasting Privacy:
  • Tal Moran and Moni Naor, Receipt-Free Universally-Verifiable Voting With Everlasting Privacy, Crypto 2006, Abstract, Postscript, gzipped Postscript, PDF.
  • Tal Moran and Moni Naor, Split-Ballot Voting: Everlasting Privacy With Distributed Trust, ACM CCS 2007, PDF.
  • 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, 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, STOC 1996, Abstract, PDF, 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. Abstract, Postscript, gzipped Postscript, PDF
  • Also see Open Day 2005 talk: Cryptography and Complexity at the Weizmann Institute, Slides: ppt
• The Carpool problem
  • 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.
  • 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. PDF, Postscript, gzipped Postscript.
• Moni Naor and Kobbi Nissim, Communication Preserving Protocols for Secure Function Evaluation, STOC 2001. Full version: PDF, Postscript, gzipped Postscript.
• Moni Naor, Rafi Ostrovsky, Ramarathnam Venkatesan and Moti Yung, Perfect Zero-Knowledge Arguments for NP Using any One-Way Permutation, of Cryptology, 11(2), 1998, pp. 87-108. Abstract, Postscript, gzipped Postscript, PDF.

• Moni Naor, Merav Parter, Eylon Yogev, The Power of Distributed Verifiers in Interactive Proofs., SODA 2020, Abstract, PDF
• 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 Omer Reingold,  Constructing Pseudo-Random Permutations with a Prescribed Structure, of Cryptology, vol 14, 2001. Abstract, PDF, Postscript, gzipped Postscript. Slides: ppt
• 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, 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, 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
• Moni Naor and Omer Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions . of Computer and Systems Sciences, vol. 58 (2), April 1999, pp. 336-375. Abstract, Postscript, gzipped Postscript, PDF.
• Moni Naor, Benny Pinkas and Omer Reingold, Distributed Pseudo-Random Functions and KDC. Eurocrypt'99. Abstract, Postscript, PDF.
• Visual Cryptography
  • Moni Naor and Adi Shamir, Visual Cryptography, Eurocrypt Postscript, gzipped Postscript, PDF.
  • Moni Naor and Adi Shamir, Visual Cryptography II, Cambridge Workshop on Security Protocols, LNCS 1189, Springer, pp. 197-202, 1996. PDF, Postscript, gzipped Postscript
  • Moni Naor and Benny Pinkas, Visual Authentication, Crypto 97. PDF Postscript, gzipped Postscript
• Oblivious Transfer and Computation
  • Moni Naor and Benny Pinkas, Computationally Secure Oblivious Transfer, Crypto 99. Postscript, gzipped Postscript
  • Moni Naor and Benny Pinkas, Distributed Oblivious Transfer, ASIACRYPT 2000. Postscript, gzipped Postscript
  • Moni Naor and Benny Pinkas, Oblivious Polynomial Evaluation, Postscript, gzipped Postscript, PDF
  • Moni Naor and Benny Pinkas, Efficient Oblivious Transfer Protocols, Postscript, gzipped Postscript
  • Moni Naor, Benny Pinkas and Reuben Sumner, Privacy preserving auctions and mechanism design, ACM Conference on Electronic Commerce, 1999. Postscript, PDF
• Moni Naor and Benny Pinkas, Trace and Revoke Schemes, Financial Crypto'2000. Abstract, Postscript, gzipped Postscript, PDF.
• 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, Threshold Traitor Tracing, Crypto 98. Postscript, gzipped Postscript.
• Moni Naor and Benny Pinkas, Secure and Efficient Metering, Eurocrypt 98, Abstract, Postscript, gzipped Postscript, PDF.
• Moni Naor, Benny Pinkas and Eyal Ronen, How to (not) share a password: Privacy preserving protocols for finding heavy hitters with adversarial behavior, ACM CCS 2019, PDF
  
• Moni Naor, Shahar Paz and Eyal Ronen, CRISP: Compromise Resilient Identity-based Symmetric PAKE,, Abstract, PDF
  
• Moni Naor, Lior Rotem, Gil Segev: The Security of Lazy Users in Out-of-Band Authentication. TCC 2018: 575-599. Abstract, PDF
• Moni Naor, Lior Rotem, Gil Segev, Out-Of-Band Authenticated Group Key Exchange: From Strong Authentication to Immediate Key Delivery. ITC 2020: 9:1-9:25. Abstract, PDF,
• 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, 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, 33rd ACM Symp. on Theory of Computing, 2001. Abstract, Postscript, gzipped Postscript, PDF. Slides: ppt.
• Moni Naor and Neil Vexler, Can Two Walk Together: Privacy Enhancing Methods and Preventing Tracking of Users. FORC 2020: 4:1-4:20. Talk (Youtube)
• Moni Naor and Udi Wieder, Novel Architectures for P2P Applications: the Continuous-Discrete Approach, 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.
• 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.
• Primary-Secondary-Resolver Proofs System and their Applications to DNSSEC
  • Sharon Goldberg, Moni Naor, Dimitrios Papadopoulos, Leonid Reyzin, Sachin Vasant and Asaf Ziv, NSEC5: Provably Preventing DNSSEC Zone Enumeration NDSS'2015. PD
  • Moni Naor and Asaf Ziv, Primary-Secondary-Resolver Membership Proof Systems, TCC 2015. PDF
  • Talks (YouTube): Sharon Goldberg , Moni Naor
• Moni Naor and Eylon Yogev, Tight Bounds for Sliding Bloom Filters, PDF.
• Moni Naor and Eylon Yogev, Bloom Filter in Adversarial Environments, PDF. Slides: PPT

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

• M. Ajtai, N. Alon, J. Bruck, R. Cypher, C. T. Ho, M. Naor and E. Szemeredi, Fault tolerant graphs, perfect hash functions and disjoint paths, FOCS 1992, 693-702. Postscript, gzipped Postscript, PDF.
• Noga Alon and Moni Naor, Coin-flipping games immune against linear-sized coalitions, SIAM J. Computing 22(2): 403-417, 1993. Postscript, gzipped Postscript, PDF.
• N. Alon, M. Blum, A. Fiat, S. Kannan, M. Naor and R. Ostrovsky, Matching Nuts and Bolts, SODA 1994, Postscript, gzipped Postscipt, PDF, A puzzle about it.
• Amotz Bar-Noy, Joseph Naor, Moni Naor One-Bit Algorithms, Distributed Computing 4, pp. 3-8, 1990. Abstract, PDF.
• Shucki Bruck and Moni Naor, The Hardness of Decoding Linear Codes with Preprocessing, IEEE Transactions on Information Theory, 36(2), 1990, 381-385. PDF.
• David Chaum, Amos Fiat and Moni Naor, Untraceable Electronic Cash, Abstract, Postscript, gzipped Postscript, PDF.
• T. Feder, E. Kushilevitz, M. Naor and N. Nisan, Amortized Communication Complexity, SIAM Journal on Computing, 1995, pp. 736--750. Abstract, PDF.
• D. Feldman, R. Impagliazzo, M. Naor, N. Nisan, S. Rudich and A. Shamir, On Dice and Coins: Models of Computation for Random Generation, Information and Computation 104(2), 1993, pp. 159-174. Abstract, PDF.
• Amos Fiat and Moni Naor, Broadcast Encryption, Abstract, Postscript, gzipped Postscript., PDF.
• Amos Fiat and Moni Naor, Implicit O(1) Probe Search, SIAM J. Computing 22: 1-10 (1993). Postscript, gzipped Postscript, PDF.
• Russel Impagliazzo and Moni Naor, Decision trees and downward closure, Proc. of 3rd Annual Conference on Structure in Complexity Theory, 1988, pp. 29-38. PDF.
• La'szlo' Lovasz, Moni Naor, Ilan Newman and Avi Wigderson, Search Problems in the Decision Tree Model, SIAM J. Discrete Math. 8(1): 119-13, 1995. Postscript, gzipped Postscript, PDF.
• Sampath Kannan, Moni Naor and Steven Rudich, Implicit Representation of Graphs, SIAM J. on Discrete Math 5: 596-603, 1992, Postscript, gzipped Postscript, PDF.
• Nimrod Megiddo, Moni Naor, David P. Anderson, The Minimum Reservation Rate Problem in Digital Audio/Video Systems, Proc. of ISTCS'93, The Second Israel Symposium on the Theory of Computing and Systems, IEEE Computer Society Press, 1993, pp. 43-48. Postscript, gzipped Postscript, PDF
• Moni Naor, Succinct Representation of General Unlabeled Graphs, Discrete Applied Math 28, 303-307,1990. Postscript, gzipped Postscript, PDF.
• Rajeev Motwani, Joseph (Seffi) Naor and Moni Naor, The probabilistic method yields deterministic parallel algorithms, Journal of Computer and System Sciences, Volume 49, Issue 3, December 1994, Pages 478-516 (Special issue of FOCS 89). 28, 303-307,1990. Postscript, PDF.
• Moni Naor, A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring, SIAM J. Discrete Math. 4(3): 409-412 (1991) Postscript, gzipped Postscript, PDF.
• Moni Naor, Constructing Ramsey Graphs from Small Probability Spaces, Postscript, gzipped Postscript, PDF.
• Moni Naor, Bit Commitment Using Pseudorandomness, J. of Cryptology, Volume 4, pp. 151-158, Postscript, gzipped Postscript, PDF.
• Small bias space and codes
• Joseph Naor, Moni Naor, Small-Bias Probability Spaces: Efficient Constructions and Applications, SIAM J. Comput. 22(4): 838-856 (1993). Abstract, Postscript, gzipped Postscript, PDF.
• N. Alon, J. Bruck, J. Naor, M. Naor and R. M. Roth, Construction of Asymptotically Good Low-Rate Error-Correcting Codes through Pseudo-Random Graphs, IEEE Transactions on Information Theory, 38(2), pp. 509-516, 1992. Abstract, Postscript, gzipped Postscript, PDF.
• Moni Naor and Moti Yung, Universal One-Way Hash Functions and their Cryptographic Applications. Abstract, Postscript, gzipped Postscript, PDF.
• Moni Naor and Moti Yung, Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. Abstract, Postscript, gzipped Postscript, PDF.

Are You Sure?

• Moni Naor, Yael Naor and Omer Reingold, Applied Kid Cryptography or How to convince your children you are not cheating, August 98.

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 topic, Technical Reports.

The Puzzler

• The Puzzler Page containing puzzles, games and other recreations reflecting research.

To Moni Naor's home page.