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.
- Yuriy Arbitman, Moni Naor and Gil Segev, De-amortized Cuckoo
Hashing: Provable Worst-Case Performance and Experimental Results,
ICALP 2009.
Abstract,
PDF.
- 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. Slides:
Postscript.
- Matt Blaze, Joan Feigenbaum and Moni Naor, A Formal
Treatment of Remotely-Keyed Encryption, Eurocrypt 98.
Abstract,
Postscript,
gzipped Postscript. 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, 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.
- Dan Boneh and Moni Naor, Timed Commitments and
Applications, Crypto'2000. Abstract,
Postscript,
gzipped
Postscript
- 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
or Non-Commiting Encryption, STOC 1996,
Abstract,
Postscript, gzipped Postscript.
- 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.
- 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.)
- Database 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.
- Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum, and Salil Vadhan,
On the Complexity of Differentially Private Data Release, STOC
2009,
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.
- 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.
- 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
- Cynthia Dwork and Moni Naor,
Zaps and Their Applications, Proc. 41st Symposium on
Foundations of Computer Science, IEEE, 2000.
Abstract,
Postscript,
gzipped Postscript, PDF. Slides: ppt.
- Cynthia Dwork, Ravi Kumar, and Moni Naor, 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 Stockmayer, 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,
Proc. 26th ACM Symp. on Theory of Computing, 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 . Slides:
ppt.
- 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.
- Eyal Kaplan, Moni Naor and Omer Reingold, Derandomized
Constructions of k-Wise (Almost) Independent Permutations,
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.
- 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.
Postscript,
gzipped Postscript.
- Ilya Mironov, Moni Naor and Gil Segev, Sketching in Adversarial
Environments, STOC 2008.
Abstract,
PDF.
- 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 2006. Abstract,
Postscript,
gzipped Postscript,
PDF.
-
Voting with Everlasting Privacy:
- 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.
Abstract, Postscript
, gzipped Postscript, PDF
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,
Proc. 33rd ACM Symp. on Theory of Computing, 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.
- 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.
- 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,
gzipped Postscript
- 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 Security Protocols, LNCS 1189, Springer, pp.
197-202, 1996.
Postscript,
gzipped Postscript
- 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.
- 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, 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. 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,
Postscript,
gzipped Postscript.
- Moni Naor and Ronny Roth, Optimal File
Sharing in Distributed Networks,
SIAM J. Computing 24(1), pp. 158-183, 1995.
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 .
-
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. Comput. 24(6): 1259-1277
(1995).
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. 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, Proc. 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.
- 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
.
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.
-
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.
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.
- Cynthia Dwork and Moni Naor, Pricing via Processing
or Combatting Junk Mail, Postscript
, gzipped Postscript.
- 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.
- Amos Fiat and Moni Naor, Implicit O(1) Probe Search,
SIAM J. Computing 22: 1-10 (1993).
Postscript,
gzipped Postscript.
-
Russel Imagliazzo 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.
- Sampath Kannan, Moni Naor and Steven Rudich, Implicit
Representation of Graphs, SIAM J. on Discrete Math 5: 596-603,
1992,
Postscript,
gzipped Postscript.
- 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.
- Moni Naor, Succinct Representation of General
Unlabeled Graphs, Discrete Applied Math 28, 303-307,1990.
Postscript,
gzipped Postscript.
- Moni Naor, A Lower Bound on Probabilistic Algorithms
for Distributive Ring Coloring, SIAM J. Discrete Math. 4(3):
409-412 (1991) Postscript,
gzipped Postscript.
- Moni Naor, Constructing Ramsey Graphs from Small
Probability Spaces, Postscript,
gzipped Postscript.
- Moni Naor, Bit Commitment Using Pseudorandomness
. J. of Cryptology, Volume 4, pp. 151-158,
Postscript,
gzipped Postscript.
- 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.
- 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.
- Moni Naor and Moti Yung, Universal One-Way Hash Functions
and their Cryptographic Applications.
Abstract,
Postscript,
gzipped Postscript.- Moni Naor and Moti Yung, Public-key
Cryptosystems Provably Secure against Chosen Ciphertext Attacks.
Abstract,
Postscript,
gzipped Postscript.
Are You Sure?
The Puzzler
- The
Puzzler Page containing puzzles, games and other recreations
reflecting research.
To Moni Naor's
home page.