On-line papers and talks: Recent Papers, By topic, Technical Reports.
·
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,
gzipped 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.
·
Ran Canetti, Uri Feige, Oded Goldreich
and Moni Naor, Adaptively Secure Multi-party Computation or Non-Commiting Encryption, STOC 1996, Abstract,
Postscript, gzipped
Postscript.
·
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.
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.
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, 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 . 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. PDF, Postscript, gzipped Postscript.
·
Ilya Mironov, Moni Naor and Gil Segev,
Sketching in Adversarial Environments, STOC 2008. Abstract,
PDF.
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. Abstract,
Postscript, gzipped Postscript, PDF
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.
·
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
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
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 .
·
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). 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. 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)...
Now at: J. of Craptology vol. 0(1), April 1999. Abstract, Postscript,
gzipped Postscript, PDF.
Also see: The Puzzler page.
To
Moni Naor's
home page.