Moni Naor: On-Line Papers

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 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, 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

Cryptography and Complexity at the Weizmann Institute

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.