On-line papers:  All on-line papers ,  Recent Papers , Technical  Reports

Papers by Topic

Go to papers on: Pseudo-randomness, Oblivious Transfer and Secure Computation ,  Zero-Knowledge and Commitment Schemes , Signature Schemes , Non Malleability and Chosen Ciphertext Attacks, Cryptography and Data Structures,  Visual Cryptography, Physical Cryptography and Puzzles, Voting, Derandomization, Key Protection Techniques,  Metering and Preventing Abuse,   Distributed Computing , Implicit Representation , Aggregation of  information

Pseudo-randomness  

  • Matt Blaze, Joan Feigenbaum and Moni Naor. A Formal Treatment of Remotely-Keyed Encryption, Eurocrypt 98.  Abstract , Postscript , gzipped Postscript
  • Russell Impagliazzo and Moni Naor,  Efficient Cryptographic Schemes Provably as Secure as Subset Sum,  J. of Cryptology  9(4):, 1996, pp. 199--216.   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 .
  • 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, Postscript, gzipped Postscript .
    • The NR Mode of Operation: Postscript, gzipped Postscript .
  • Moni Naor and Omer Reingold, Number-Theoretic constructions of efficient pseudo-random functions, Extended abstract in: Proc. 38th IEEE Symp. on Foundations of Computer Science, 1997, pp. 458-467, full version: J. ACM 51(2): 231-262 (2004)
    • Abstract , 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, Postscript , gzipped Postscript .
  • Moni Naor and Omer Reingold,  Constructing Pseudo-Random Permutations with a Prescribed Structure, J. of Cryptology, vol 14, 2001.
    • Abstract, Postscript, gzipped Postscript.
  • Moni Naor, Omer Reingold and Alon Rosen, Pseudo-Random Functions and Factoring,  Proc. of the 32nd ACM Symp. on Theory of Computing,  2000, pp. 11-20.  Abstract , Postscript , gzipped Postscript  
  • 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.

    Oblivious Transfer and Secure Computation
     
  • 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,  Proc. 26th  ACM Symp. on Theory of Computing,  1994.  Postscript , gzipped Postscript , PDF
  • Danny Harnik, Moni Naor, Omer Reingold and Alon Rosen, Completeness in Two-Party Secure Computation - A Computational View. 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.
  • Moni Naor and Kobbi Nissim, Communication Preserving Protocols for Secure Function Evaluation,  Proc. 33rd  ACM Symp. on Theory of Computing, 2001. Full version:   Postscript, gzipped Postscript
  • 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 , gzipped Postscript

    • Zero-Knowledge and Commitment Schemes
     
  • Dan Boneh and Moni Naor.  Timed Commitments and Applications, Crypto'2000. Abstract , Postscript , gzipped Postscript
  • Cynthia Dwork and  Moni Naor ,  Zaps and Their Applications, Proc. 41st Symposium on Foundations of Computer Science, IEEE, 2000.    Abstract , Postscript , gzipped Postscript
  • Cynthia Dwork,  Moni Naor , Omer Reingold and Larry Stockmayer, Magic Functions, Proc. 40th  Symposium on Foundations of Computer Science, IEEE, 1999. Postscript , gzipped Postscript
  • Cynthia Dwork, Moni Naor and Amit Sahai, Concurrent Zero-Knowledge or The Timing Model for Designing Concurrent Protocols, Proc. 29th ACM Symp. on Theory of Computing, 1998. Abstract , Postscript , gzipped Postscript
  • Moni Naor, Bit Commitment Using Pseudorandomness . J. of Cryptology, Volume 4, pp. 151-158, Postscript , gzipped Postscript
  • Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung, Perfect Zero-Knowledge Arguments for NP Using any One-Way Permutation, J. of Cryptology,Vol 11, Number 2, 1998, pp. 87-108. Abstract , Postscript , gzipped Postscript PDF.

    • Signature and Authentication Schemes
     
  • Cynthia Dwork  and Moni Naor, An Efficient Existentially Unforgeable Signature Scheme and Its Applications ,  J. of Cryptology, Vol 11, Number 2, 1998,  pp. 187-208,  Postscript , gzipped Postscript
  • Moni Naor, Deniable Ring Authentication, Crypto 2002 , Abstract , Postscript , gzipped Postscript , PDF
  • Moni Naor and Moti Yung, Universal One-Way Hash Functions and their Cryptographic Applications Abstract , Postscript , gzipped Postscript
    •  
    Non Malleability and Chosen Ciphertext Attacks
     
  • Mihir Bellare, Russell Impagliazzo and Moni Naor. Does Parallel Repetition Lower the Error in Computationally Sound Protocols? Proceedings of 38th Annual Symposium on Foundations of Computer Science, IEEE, 1997. Abstract , Postscript , gzipped Postscript
  • 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.
  • Moni Naor, Moti Yung: Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks.
    • Abstract , Postscript , gzipped Postscript

    Non-standard attacks on cryptosystem


    Derandomization and small sample spaces
     
  • 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
  • Eyal Kaplan, Moni Naor and Omer Reingold, Derandomized Constructions of k-Wise (Almost) Independent Permutations, Random 2005, Abstract, Postscript, gzipped Postscript PDF, Slides: ppt
  • Moni Naor,  Constructing Ramsey Graphs from Small Probabiltiy Spaces, Postscript, gzipped Postscript
  • Joseph Naor, Moni Naor, Small-Bias Probability Spaces: Efficient Constructions and Applications, SIAM J. Comput. 22(4): 838-856 (1993). Abstract, 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. 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.

    Cryptography and Data Structures
  • Memory Checking
  • Amos Fiat and Moni Naor, Rigorous Time/Space Tradeoffs for Inverting Functions, SIAM J. Computing  29(3), 1999 pp.  790-803. Postscript ,  gzipped Postscript
  • Moni Naor and Kobbi Nissim, Certificate Revocation and Certificate Update, 7th USENIX Security Symposium, 1998. Postscript, gzipped Postscript.

  • History Independence:

    • Visual Cryptography Key Protection Techniques
     
  • R. 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.
  • Cynthia Dwork, Jeff Lotspiech and Moni Naor, Digital Signets: Self-Enforcing Protection of Digital Information ,
    • Abstract , Postscript , gzipped Postscript
  • Amos Fiat and Moni Naor, Broadcast Encryption, Abstract , Postscript , gzipped Postscript .
  • Dalit Naor, Moni Naor and Jeff Lotspiech, Revocation and Tracing Schemes for Stateless Receivers,
    • Abstract , 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, Threshold Traitor Tracing , Crypto 98. Postscript , gzipped Postscript
  • Moni Naor and Benny Pinkas, Efficient Trace and Revoke Schemes , FC'2000. Postscript , gzipped Postscript

    • Metering and Preventing Abuse
     
  • Spam fighting and abuse prevention via pricing functions
  • Moni Naor, Verification of a human in the loop or Identification via the Turing Test,  Abstract , Postscript , gzipped Postscript
  • Moni Naor and Benny Pinkas, Secure and Efficient Metering, Abstract, Postscript, gzipped  Postscript

    • Physical Based Cryptography and Puzzles
     
  • Tal Moran and Moni Naor, Basing Cryptographic Protocols on Tamper-Evident Seals, ICALP 2005,   Abstract ,  Postscript, gzipped Postscript
  • Tal Moran and Moni Naor, Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol, Eurocrypt 2006,   Abstract, Postscript, gzipped Postscript, PDF.
  • Ronen Gradwohl, Moni Naor, Benny Pinkas and Guy Rothblum, Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles, Abstract , Postscript , gzipped Postscript , PDF
  • Moni Naor, Yael Naor and Omer Reingold, Applied Kid Cryptography or How to convince your children you are not cheating, August 98.
    • Abstract , Postscript , gzipped Postscript , PDF
    Also see: The Puzzler page .

    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


    • Distributed Computing
     

  • Moni Naor and Ronny Roth, Optimal File Sharing in Distributed Networks, SIAM J. Computing 24(1): 158-183 (1995). Postscript, gzipped Postscript
  • Moni Naor and Larry Stockmeyer, What Can be Computed Locally ?, SIAM J. Comput. 24(6): 1259-1277 (1995). Postscript , gzipped Postscript.
  • Alain Mayer, Moni Naor and Larry Stockmeyer, Local Computations on Static and Dynamic Graphs. Postscript, gzipped Postscript
  • Dalia Malkhi, Moni Naor and David Ratajczak, Viceroy: A Scalable and Dynamic Emulation of the Butterfly, Proc. 2002 PODC,  Abstract , Postscript , gzipped Postscript , PDF
  • Uri Nadav, Moni Naor, Fault Tolerant Storage in a Dynamic Environment, Proc. Disc 2004.  Postscript, gzipped Postscript
  • Moni Naor and Udi Wieder, Novel Architectures for P2P Applications: the Continuous-Discrete Approach,  gzipped Postscript, PDF
  • Moni Naor and Udi Wieder, A Simple Fault Tolerant Distributed Hash Table,  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,   Postscript , gzipped Postscript , PDF
  • G. S.  Manku, M. Naor, 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 .
  • Moni Naor and Avishai Wool, Access Control and Signatures via Quorum Secret Sharing, 5th ACM Computer and Communication Security, 1996. Abstract , Postscript , gzipped Postscript.


    • Implicit Representation of Data Structures and Graphs
  • Amos Fiat and Moni Naor, Implicit O(1) Probe Search, SIAM J. Comput. 22: 1-10 (1993). Postscript , gzipped Postscript.
  • Sampath Kannan, Moni Naor and Steven Rudich, Implicit Representation of Graphs, SIAM J. on Discrete Math 5: 596-603, 1992,  Postscript , gzipped Postscript.
  • Moni Naor,  Succinct Representation of General Unlabeled Graphs, Discrete Applied Math 28, 303-307,1990. Postscript , gzipped Postscript.


    • Aggregation

  • Cynthia Dwork, Ravi Kumar, and Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, WWW10, 2001 .
    • Abstract , HTML
  • Ron Fagin, Amnon Lotem and Moni Naor , Optimal aggregation algorithms for middleware. Proc. 2001 ACM Symposium on Principles of Database Systems. Abstract ,  Full version: Postscript , gzipped Postscript

    •  

    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 2006. Abstract, Postscript, gzipped Postscript, PDF

    • On-line papers:  All on-line papers ,  Recent Papers , Technical  Reports

    Back Home