Moni Naor

According to our database1, Moni Naor authored at least 215 papers between 1987 and 2018.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
How to (not) share a password: Privacy preserving protocols for finding heavy hitters with adversarial behavior.
IACR Cryptology ePrint Archive, 2018

The Power of Distributed Verifiers in Interactive Proofs.
Electronic Colloquium on Computational Complexity (ECCC), 2018

The Security of Lazy Users in Out-of-Band Authentication.
Proceedings of the Theory of Cryptography - 16th International Conference, 2018

Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions.
Proceedings of the Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29, 2018

2017
Can NSEC5 be practical for DNSSEC deployments?
IACR Cryptology ePrint Archive, 2017

The Journey from NP to TFNP Hardness.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
NSEC5 from Elliptic Curves: Provably Preventing DNSSEC Zone Enumeration with Shorter Responses.
IACR Cryptology ePrint Archive, 2016

Universal Obfuscation and Witness Encryption: Boosting Correctness and Combining Security.
IACR Cryptology ePrint Archive, 2016

How to Share a Secret, Infinitely.
Proceedings of the Theory of Cryptography - 14th International Conference, 2016

Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets.
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Is There an Oblivious RAM Lower Bound?
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems.
Proceedings of the Advances in Cryptology - CRYPTO 2016, 2016

Universal Constructions and Robust Combiners for Indistinguishability Obfuscation and Witness Encryption.
Proceedings of the Advances in Cryptology - CRYPTO 2016, 2016

2015
Tight Bounds for Sliding Bloom Filters.
Algorithmica, 2015

Primary-Secondary-Resolver Membership Proof Systems.
Proceedings of the Theory of Cryptography - 12th Theory of Cryptography Conference, 2015

Secure Physical Computation Using Disposable Circuits.
Proceedings of the Theory of Cryptography - 12th Theory of Cryptography Conference, 2015

When Can Limited Randomness Be Used in Repeated Games?
Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

NSEC5: Provably Preventing DNSSEC Zone Enumeration.
Proceedings of the 22nd Annual Network and Distributed System Security Symposium, 2015

Bloom Filters in Adversarial Environments.
Proceedings of the Advances in Cryptology - CRYPTO 2015, 2015

Pure Differential Privacy for Rectangle Queries via Private Partitions.
Proceedings of the Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29, 2015

2014
Fast Interactive Coding against Adversarial Noise.
J. ACM, 2014

Secret-Sharing for NP from Indistinguishability Obfuscation.
IACR Cryptology ePrint Archive, 2014

One-Way Functions and (Im)Perfect Obfuscation.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Physical Zero-Knowledge Proofs of Physical Properties.
Proceedings of the Advances in Cryptology - CRYPTO 2014, 2014

Secret-Sharing for NP.
Proceedings of the Advances in Cryptology - ASIACRYPT 2014, 2014

2013
Hardness Preserving Reductions via Cuckoo Hashing.
Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Fast Algorithms for Interactive Coding.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Sliding Bloom Filters.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

2012
The Privacy of the Analyst and the Power of the State.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2010
On the Compressibility of NP Instances and Cryptographic Applications.
SIAM J. Comput., 2010

Differential privacy under continual observation.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Pan-Private Streaming Algorithms.
Proceedings of the Innovations in Computer Science, 2010

Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Public-Key Encryption in the Bounded-Retrieval Model.
Proceedings of the Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30, 2010

The privacy of tracing traitors.
Proceedings of the 10th ACM Workshop on Digital Rights Management, 2010

2009
Derandomized Constructions of k-Wise (Almost) Independent Permutations.
Algorithmica, 2009

An Optimally Fair Coin Toss.
Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

How Efficient Can Memory Checking Be?.
Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

On the complexity of differentially private data release: efficient algorithms and hardness results.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Games for extracting randomness.
Proceedings of the 5th Symposium on Usable Privacy and Security, 2009

De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Public-Key Cryptosystems Resilient to Key Leakage.
Proceedings of the Advances in Cryptology, 2009

Hedged Public-Key Encryption: How to Protect against Bad Randomness.
Proceedings of the Advances in Cryptology, 2009

2008
Cryptography and Game Theory: Designing Protocols for Exchanging Information.
Proceedings of the Theory of Cryptography, Fifth Theory of Cryptography Conference, 2008

Sketching in adversarial environments.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Games for exchanging information.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Informational overhead of incentive compatibility.
Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

History-Independent Cuckoo Hashing.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Traitor tracing with constant size ciphertext.
Proceedings of the 2008 ACM Conference on Computer and Communications Security, 2008

2007
Deterministic History-Independent Strategies for Storing Information on Write-Once Memories.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles.
Proceedings of the Fun with Algorithms, 4th International Conference, 2007

Split-ballot voting: everlasting privacy with distributed trust.
Proceedings of the 2007 ACM Conference on Computer and Communications Security, 2007

Implementing Huge Sparse Random Graphs.
Proceedings of the Approximation, 2007

2006
Oblivious Polynomial Evaluation.
SIAM J. Comput., 2006

Derandomized Constructions of k-Wise (Almost) Independent Permutations
Electronic Colloquium on Computational Complexity (ECCC), 2006

Learning to impersonate.
Proceedings of the Machine Learning, 2006

On Everlasting Security in the Hybrid Bounded Storage Model.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

On the Compressibility of NP Instances and Cryptographic Applications.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol.
Proceedings of the Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28, 2006

Our Data, Ourselves: Privacy Via Distributed Noise Generation.
Proceedings of the Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28, 2006

Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models.
Proceedings of the Advances in Cryptology, 2006

Receipt-Free Universally-Verifiable Voting with Everlasting Privacy.
Proceedings of the Advances in Cryptology, 2006

2005
Computationally Secure Oblivious Transfer.
J. Cryptology, 2005

On fairness in the carpool problem.
J. Algorithms, 2005

The Dynamic And-Or Quorum System.
Proceedings of the Distributed Computing, 19th International Conference, 2005

Efficiently Constructible Huge Graphs That Preserve First Order Properties of Random Graphs.
Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

Basing Cryptographic Protocols on Tamper-Evident Seals.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

The Complexity of Online Memory Checking.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

On Robust Combiners for Oblivious Transfer and Other Primitives.
Proceedings of the Advances in Cryptology, 2005

Pebbling and Proofs of Work.
Proceedings of the Advances in Cryptology, 2005

Derandomized Constructions of k-Wise (Almost) Independent Permutations.
Proceedings of the Approximation, 2005

2004
Fault-Tolerant Storage in a Dynamic Environment.
Proceedings of the Distributed Computing, 18th International Conference, 2004

Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Completeness in two-party secure computation: a computational view.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Know Thy Neighbor's Neighbor: Better Routing for Skip-Graphs and Small Worlds.
Proceedings of the Peer-to-Peer Systems III, Third International Workshop, 2004

Immunizing Encryption Schemes from Decryption Errors.
Proceedings of the Advances in Cryptology, 2004

2003
Nonmalleable Cryptography.
SIAM Review, 2003

Completeness in Two-Party Secure Computation - A Computational View
Electronic Colloquium on Computational Complexity (ECCC), 2003

Protecting Cryptographic Keys: The Trace-and-Revoke Approach.
IEEE Computer, 2003

Novel architectures for P2P applications: the continuous-discrete approach.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Scalable and dynamic quorum systems.
Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, 2003

A Simple Fault Tolerant Distributed Hash Table.
Proceedings of the Peer-to-Peer Systems II, Second International Workshop, 2003

Moderately Hard Functions: From Complexity to Spam Fighting.
Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

On Cryptographic Assumptions and Challenges.
Proceedings of the Advances in Cryptology, 2003

On Memory-Bound Functions for Fighting Spam.
Proceedings of the Advances in Cryptology, 2003

2002
Pseudorandom Functions and Factoring.
SIAM J. Comput., 2002

On Chosen Ciphertext Security of Multiple Encryptions.
IACR Cryptology ePrint Archive, 2002

Revocation and Tracing Schemes for Stateless Receivers
Electronic Colloquium on Computational Complexity (ECCC), 2002

Zaps and Their Applications
Electronic Colloquium on Computational Complexity (ECCC), 2002

Viceroy: a scalable and dynamic emulation of the butterfly.
Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, 2002

Deniable Ring Authentication.
Proceedings of the Advances in Cryptology, 2002

2001
Anti-persistence: History Independent Data Structures.
IACR Cryptology ePrint Archive, 2001

Pseudo-Random Functions and Factoring.
IACR Cryptology ePrint Archive, 2001

Communication Complexity and Secure Function Evaluation.
IACR Cryptology ePrint Archive, 2001

Pseudo-Random Functions and Factoring
Electronic Colloquium on Computational Complexity (ECCC), 2001

Communication Complexity and Secure Function Evaluation
Electronic Colloquium on Computational Complexity (ECCC), 2001

Rank aggregation methods for the Web.
Proceedings of the Tenth International World Wide Web Conference, 2001

Anti-presistence: history independent data structures.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Communication preserving protocols for secure function evaluation.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Constructing pseudo-random permutations with a prescribed structure.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Efficient oblivious transfer protocols.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Optimal Aggregation Algorithms for Middleware.
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Revocation and Tracing Schemes for Stateless Receivers.
Proceedings of the Advances in Cryptology, 2001

2000
Tracing traitors.
IEEE Trans. Information Theory, 2000

Nonmalleable Cryptography.
SIAM J. Comput., 2000

Certificate revocation and certificate update.
IEEE Journal on Selected Areas in Communications, 2000

Visual cryptography for grey level images.
Inf. Process. Lett., 2000

Pseudo-random functions and factoring (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Zaps and Their Applications.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Efficient Trace and Revoke Schemes.
Proceedings of the Financial Cryptography, 2000

Timed Commitments.
Proceedings of the Advances in Cryptology, 2000

Distributed Oblivious Transfer.
Proceedings of the Advances in Cryptology, 2000

1999
Rigorous Time/Space Trade-offs for Inverting Functions.
SIAM J. Comput., 1999

On the Construction of Pseudorandom Permutations: Luby-Rackoff Revisited.
J. Cryptology, 1999

Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions.
J. Comput. Syst. Sci., 1999

Oblivious Transfer and Polynomial Evaluation.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

A Formal Treatment of Remotely Keyed Encryption.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Privacy preserving auctions and mechanism design.
Proceedings of the First ACM Conference on Electronic Commerce (EC-99), 1999

Multicast Security: A Taxonomy and Some Efficient Constructions.
Proceedings of the Proceedings IEEE INFOCOM '99, 1999

Magic Functions.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Distributed Pseudo-random Functions and KDCs.
Proceedings of the Advances in Cryptology, 1999

Oblivious Transfer with Adaptive Queries.
Proceedings of the Advances in Cryptology, 1999

1998
The Load, Capacity, and Availability of Quorum Systems.
SIAM J. Comput., 1998

Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation.
J. Cryptology, 1998

Fairness in Scheduling
J. Algorithms, 1998

Private Information Retrieval by Keywords.
IACR Cryptology ePrint Archive, 1998

Secure Accounting and Auditing on the Web.
Computer Networks, 1998

Certificate Revocation and Certificate Update.
Proceedings of the 7th USENIX Security Symposium, 1998

Concurrent Zero-Knowledge.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Secure and Efficient Metering.
Proceedings of the Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31, 1998

A Formal Treatment of Remotely Keyed Encryption.
Proceedings of the Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31, 1998

From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs (Extended Abstract).
Proceedings of the Advances in Cryptology, 1998

Threshold Traitor Tracing.
Proceedings of the Advances in Cryptology, 1998

1997
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited
Electronic Colloquium on Computational Complexity (ECCC), 1997

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Number-theoretic Constructions of Efficient Pseudo-random Functions.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Does Parallel Repetition Lower the Error in Computationally Sound Protocols?
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Visual Authentication and Identification.
Proceedings of the Advances in Cryptology, 1997

Deniable Encryption.
Proceedings of the Advances in Cryptology, 1997

1996
Efficient Cryptographic Schemes Provably as Secure as Subset Sum.
J. Cryptology, 1996

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited.
IACR Cryptology ePrint Archive, 1996

Comparing Information Without Leaking It.
Commun. ACM, 1996

Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions.
Algorithmica, 1996

Evaluation May Be Easier Than Generation (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Digital Signets: Self-Enforcing Protection of Digital Information (Preliminary Version).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Adaptively Secure Multi-Party Computation.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Visual Cryptography II: Improving the Contrast Via the Cover Base.
Proceedings of the Security Protocols, 1996

On the Decisional Complexity of Problems Over the Reals.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

Access Control and Signatures via Quorum Secret Sharing.
Proceedings of the CCS '96, 1996

1995
Search Problems in the Decision Tree Model.
SIAM J. Discrete Math., 1995

Optimal File Sharing in Distributed Networks.
SIAM J. Comput., 1995

Amortized Communication Complexity.
SIAM J. Comput., 1995

Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions
Electronic Colloquium on Computational Complexity (ECCC), 1995

Fairness in Scheduling.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Local Computations on Static and Dynamic Graphs (Preliminary Version).
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

On the Complexity of Statistical Reasoning (extended abtract).
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Splitters and Near-Optimal Derandomization.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Synthesizers and Their Application to the Parallel Construction of Psuedo-Random Functions.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
The Probabilistic Method Yields Deterministic Parallel Algorithms.
J. Comput. Syst. Sci., 1994

Checking the Correctness of Memories.
Algorithmica, 1994

A minimal model for secure computation (extended abstract).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Matching Nuts and Bolts.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

The Load, Capacity and Availability of Quorum Systems
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Visual Cryptography.
Proceedings of the Advances in Cryptology, 1994

An Efficient Existentially Unforgeable Signature Scheme and its Applications.
Proceedings of the Advances in Cryptology, 1994

Tracing Traitors.
Proceedings of the Advances in Cryptology, 1994

1993
On Dice and Coins: Models of Computation for Random Generation
Inf. Comput., June, 1993

Three results on interactive communication.
IEEE Trans. Information Theory, 1993

Small-Bias Probability Spaces: Efficient Constructions and Applications.
SIAM J. Comput., 1993

Implicit O(1) Probe Search.
SIAM J. Comput., 1993

Coin-Flipping Games Immune Against Linear-Sized Coalitions.
SIAM J. Comput., 1993

What can be computed locally?
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

The Minimum Reservation Rate Problem in Digital Audio/Video Systems.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Codes for Interactive Authentication.
Proceedings of the Advances in Cryptology, 1993

Broadcast Encryption.
Proceedings of the Advances in Cryptology, 1993

1992
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs.
IEEE Trans. Information Theory, 1992

Implicit Representation of Graphs.
SIAM J. Discrete Math., 1992

On the Time and Space Complexity of Computation Using Write-Once Memory Or Is Pen Really Much Worse Than Pencil?
Mathematical Systems Theory, 1992

Nonoblivious Hashing.
J. ACM, 1992

Witnesses for Boolean Matrix Multiplication and for Shortest Paths
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions (Extended Abstract).
Proceedings of the Advances in Cryptology, 1992

Pricing via Processing or Combatting Junk Mail.
Proceedings of the Advances in Cryptology, 1992

Low Communication 2-Prover Zero-Knowledge Proofs for NP.
Proceedings of the Advances in Cryptology, 1992

1991
A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring.
SIAM J. Discrete Math., 1991

Bit Commitment Using Pseudorandomness.
J. Cryptology, 1991

An Implicit Data Structure for Searching a Multikey Table in Logarithmic Time.
J. Comput. Syst. Sci., 1991

Rigorous Time/Space Tradeoffs for Inverting Functions
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Non-Malleable Cryptography (Extended Abstract)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

String Matching with Preprocessing of Text and Pattern.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Optimal File Sharing in Distributed Networks (Preliminary Version)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Search Problems in the Decision Tree Model (Preliminary Version)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Amortized Communication Complexity (Preliminary Version)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Checking the Correctness of Memories
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
The hardness of decoding linear codes with preprocessing.
IEEE Trans. Information Theory, 1990

Succinct representation of general unlabeled graphs.
Discrete Applied Mathematics, 1990

Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Small-bias Probability Spaces: Efficient Constructions and Applications
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
Fast Parallel Algorithms for Chordal Graphs.
SIAM J. Comput., 1989

Universal One-Way Hash Functions and their Cryptographic Applications
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Implicit O(1) Probe Search
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

On Dice and Coins: Models of Computation for Random Generation.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

The Probabilistic Method Yields Deterministic Parallel Algorithms
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Efficient Cryptographic Schemes Provably as Secure as Subset Sum
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Bit Commitment Using Pseudo-Randomness.
Proceedings of the Advances in Cryptology, 1989

1988
Implicit Representation of Graphs
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Storing and Searching a Multikey Table (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Non-Oblivious Hashing (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

One Bit Algorithms.
Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988

Untraceable Electronic Cash.
Proceedings of the Advances in Cryptology, 1988

Decision trees and downward closures.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Fast Parallel Algorithms for Chordal Graphs (Extended Abstract)
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987


  Loading...