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
- Ran Canetti, Cynthia Dwork, Moni Naor and
Rafi Ostrovsky, Deniable Encryption, Crypto 97.
Abstract,
Postscript,
gzipped Postscript. - Ran Canetti, Uri Feige, Oded Goldreich
and Moni
Naor, Adaptively Secure Multi-party Computation
(non-commiting encryption) ,
Abstract, Postscript, gzipped
Postscript
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
- 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, FOCS 2005. 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.
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:
- Moni Naor and Vanessa Teague, Anti-persistence:
History Independent Data Structures, Proc. 33rd ACM Symp. on
Theory of Computing, 2001. Abstract,
Postscript,
gzipped Postscript.
- 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).
- Moni Naor, Gil Segev and Udi Wieder, History-Independent Cuckoo
Hashing,
ICALP 2008. Abstract,
Postscript,
gzipped
Postscript,
PDF.
- Yuriy Arbitman, Moni Naor and Gil Segev, De-amortized Cuckoo
Hashing: Provable Worst-Case Performance and Experimental Results,
Abstract,
PDF.
Visual Cryptography
- Moni Naor and Adi Shamir, Visual Cryptography ,
Eurocrypt 94.
Postscript ,
gzipped Postscript
- Moni Naor and Adi Shamir, Visual Cryptography II
, Cambridge Workshop on Protocols, 1996.
Postscript,
gzipped Postscript
- Moni Naor and Benny Pinkas, Visual Authentication
, Crypto 97.
Postscript,
gzipped Postscript
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
- Cynthia Dwork and Moni Naor, Pricing via Processing
or Combatting Junk Mail,
Abstract , Postscript, gzipped Postscript
- 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, ,
CRYPTO 2005.
Abstract ,
Postscript ,
gzipped Postscript , PDF
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
Back Home