# Oded Goldreich

According to our database1, Oded Goldreich
• authored at least 435 papers between 1981 and 2018.
• has a "Dijkstra number"2 of three.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2018
Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems.
Electronic Colloquium on Computational Complexity (ECCC), 2018

The Subgraph Testing Model.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Every set in P is strongly testable under a suitable encoding.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017
On Learning and Testing Dynamic Environments.
J. ACM, 2017

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Worst-case to Average-case reductions for subclasses of P.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Simple doubly-efficient interactive proof systems for locally-characterizable sets.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Overview of the doubly-efficient interactive proof systems of RRR.
Electronic Colloquium on Computational Complexity (ECCC), 2017

On the doubly-efficient interactive proof systems of GKR.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Introduction to Property Testing.
Cambridge University Press, ISBN: 978-1-107-19405-2, 2017

2016
Testing Bipartiteness of Graphs in Sublinear Time.
Encyclopedia of Algorithms, 2016

Testing Bipartiteness in the Dense-Graph Model.
Encyclopedia of Algorithms, 2016

Estimating Simple Graph Parameters in Sublinear Time.
Encyclopedia of Algorithms, 2016

On Sample-Based Testers.
TOCT, 2016

Two-sided error proximity oblivious testing.
Random Struct. Algorithms, 2016

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Universal Locally Testable Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Deconstructing 1-local expanders.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Reducing testing affine spaces to testing linearity.
Electronic Colloquium on Computational Complexity (ECCC), 2016

On Emulating Interactive Proofs with Public Coins.
Electronic Colloquium on Computational Complexity (ECCC), 2016

The uniform distribution is complete with respect to testing identity to a fixed distribution.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Special Issue on the 10th Theory of Cryptography Conference: Editor's Foreword.
Computational Complexity, 2016

Matrix rigidity of random toeplitz matrices.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly.
TOCT, 2015

On Randomness Extraction in AC0.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Matrix Rigidity of Random Toeplitz Matrices.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2015

On Sample-Based Testers.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract).
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On Randomness Extraction in AC0.
Proceedings of the 30th Conference on Computational Complexity, 2015

Strong Locally Testable Codes with Relaxed Local Decoders.
Proceedings of the 30th Conference on Computational Complexity, 2015

2014
Finding cycles and trees in sublinear time.
Random Struct. Algorithms, 2014

Super-Perfect Zero-Knowledge Proofs.
Electronic Colloquium on Computational Complexity (ECCC), 2014

On Learning and Testing Dynamic Environments.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Strong Locally Testable Codes with Relaxed Local Decoders.
Electronic Colloquium on Computational Complexity (ECCC), 2014

On derandomizing algorithms that err extremely rarely.
Proceedings of the Symposium on Theory of Computing, 2014

On Learning and Testing Dynamic Environments.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

On Multiple Input Problems in Property Testing.
Proceedings of the Approximation, 2014

2013
A Short Tutorial of Zero-Knowledge.
Proceedings of the Secure Multi-Party Computation, 2013

General Cryptographic Protocols: The Very Basics.
Proceedings of the Secure Multi-Party Computation, 2013

Enhancements of Trapdoor Permutations.
J. Cryptology, 2013

More Constructions of Lossy and Correlation-Secure Trapdoor Functions.
J. Cryptology, 2013

On Derandomizing Algorithms that Err Extremely Rarely.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On Sample-Based Testers.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On Multiple Input Problems in Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On the possibilities and limitations of pseudodeterministic algorithms.
Proceedings of the Innovations in Theoretical Computer Science, 2013

2012
Monotone Circuits: One-Way Functions versus Pseudorandom Generators.
Theory of Computing, 2012

On intellectual and instrumental values in science.
SIGACT News, 2012

On struggle and competition in scientic fields.
SIGACT News, 2012

A theory of goal-oriented communication.
J. ACM, 2012

On the (im)possibility of obfuscating programs.
J. ACM, 2012

The tensor product of two good codes is not necessarily robustly testable.
Inf. Process. Lett., 2012

On the possibilities and limitations of pseudodeterministic algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Two-Sided Error Proximity Oblivious Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2012

On the Effect of the Proximity Parameter on Property Testers.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Finding Cycles and Trees in Sublinear Time.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Invitation to complexity theory.

Special issue from RANDOM'09: Editors' Foreword.
Computational Complexity, 2012

Hierarchy Theorems for Property Testing.
Computational Complexity, 2012

Two-Sided Error Proximity Oblivious Testing - (Extended Abstract).
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
On Proximity-Oblivious Testing.
SIAM J. Comput., 2011

Algorithmic Aspects of Property Testing in the Dense Graphs Model.
SIAM J. Comput., 2011

On the complexity of computational problems regarding distributions (a survey).
Electronic Colloquium on Computational Complexity (ECCC), 2011

Enhancements of Trapdoor Permutations.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Monotone Circuits: One-Way Functions versus Pseudorandom Generators.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Two Comments on Targeted Canonical Derandomizers.
Electronic Colloquium on Computational Complexity (ECCC), 2011

A theory of goal-oriented communication.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Proximity Oblivious Testing and the Role of Invariances.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Testing Graph Blow-Up.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More).
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On the Circuit Complexity of Perfect Hashing.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Simplified Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On the Complexity of Computational Problems Regarding Distributions.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Testing Expansion in Bounded-Degree Graphs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Yao's XOR-Lemma.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Constructing 1-1 One-Way Functions.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Proximity Oblivious Testing and the Role of Invariances.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Collision-Free Hashing from Lattice Problems.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Another Motivation for Reducing the Randomness Complexity of Algorithms.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Contemplations on Testing Graph Properties.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Security Preserving Reductions - Revised Terminology.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Randomness and Computation.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Introduction to Testing Graph Properties.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

A Brief Introduction to Property Testing.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Average Case Complexity, Revisited.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Bravely, Moderately: A Common Theme in Four Recent Works.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Short Locally Testable Codes and Proofs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

A Sample of Samplers: A Computational Perspective on Sampling.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Three XOR-Lemmas - An Exposition.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Notes on Levin's Theory of Average-Case Complexity.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

In a World of P=BPP.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

A Candidate Counterexample to the Easy Cylinders Conjecture.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On the Average-Case Complexity of Property Testing.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Candidate One-Way Functions Based on Expander Graphs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Strong Proofs of Knowledge.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

From Absolute Distinguishability to Positive Distinguishability.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Proving Computational Ability.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Testing Graph Blow-Up.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010
On the Implementation of Huge Random Objects.
SIAM J. Comput., 2010

On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits.
J. Cryptology, 2010

Proximity Oblivious Testing and the Role of Invariances.
Electronic Colloquium on Computational Complexity (ECCC), 2010

In a World of P=BPP.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Introduction to Testing Graph Properties.
Electronic Colloquium on Computational Complexity (ECCC), 2010

On Testing Computability by Small Width OBDDs.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Finding Cycles and Trees in Sublinear Time
CoRR, 2010

On The Randomness Complexity of Property Testing.
Computational Complexity, 2010

Erratum for: on basing one-way functions on NP-hardness.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Proceedings of the Property Testing, 2010

Hierarchy Theorems for Property Testing.
Proceedings of the Property Testing, 2010

Introduction to Testing Graph Properties.
Proceedings of the Property Testing, 2010

Short Locally Testable Codes and Proofs: A Survey in Two Parts.
Proceedings of the Property Testing, 2010

The Program of the Mini-Workshop.
Proceedings of the Property Testing, 2010

A Brief Introduction to Property Testing.
Proceedings of the Property Testing, 2010

More Constructions of Lossy and Correlation-Secure Trapdoor Functions.
Proceedings of the Public Key Cryptography, 2010

On Testing Computability by Small Width OBDDs.
Proceedings of the Approximation, 2010

P, NP, and NP-Completeness: The Basics of Complexity Theory.
Cambridge University Press, ISBN: 978-0-521-12254-2, 2010

2009
On our duties as scientists.
SIGACT News, 2009

More Constructions of Lossy and Correlation-Secure Trapdoor Functions.
IACR Cryptology ePrint Archive, 2009

A Theory of Goal-Oriented Communication.
Electronic Colloquium on Computational Complexity (ECCC), 2009

A Candidate Counterexample to the Easy Cylinders Conjecture.
Electronic Colloquium on Computational Complexity (ECCC), 2009

From absolute distinguishability to positive distinguishability.
Electronic Colloquium on Computational Complexity (ECCC), 2009

On proximity oblivious testing.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Proceedings of the Approximation, 2009

Hierarchy Theorems for Property Testing.
Proceedings of the Approximation, 2009

2008
Computational complexity: a conceptual perspective.
SIGACT News, 2008

Universal Arguments and their Applications.
SIAM J. Comput., 2008

Approximating average parameters of graphs.
Random Struct. Algorithms, 2008

Probabilistic Proof Systems: A Primer.
Foundations and Trends in Theoretical Computer Science, 2008

On Proximity Oblivious Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Hierarchy Theorems for Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Preface to the Special Issue from Random'06.
Computational Complexity, 2008

Computational complexity - a conceptual perspective.
Cambridge University Press, ISBN: 978-0-521-88473-0, 2008

2007
On the randomness complexity of property testing.
Electronic Colloquium on Computational Complexity (ECCC), 2007

The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable.
Electronic Colloquium on Computational Complexity (ECCC), 2007

On the Average-Case Complexity of Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword.
Computational Complexity, 2007

On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits.
Proceedings of the Theory of Cryptography, 4th Theory of Cryptography Conference, 2007

On the Randomness Complexity of Property Testing.
Proceedings of the Approximation, 2007

On Approximating the Average Distance Between Points.
Proceedings of the Approximation, 2007

2006
Special Issue on Randomness and Complexity.
SIAM J. Comput., 2006

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.
SIAM J. Comput., 2006

Session-Key Generation Using Human Passwords Only.
J. Cryptology, 2006

Locally testable codes and PCPs of almost-linear length.
J. ACM, 2006

On Post-Modern Cryptography.
IACR Cryptology ePrint Archive, 2006

On Expected Probabilistic Polynomial-Time Adversaries - A suggestion for restricted definitions and their benefits.
IACR Cryptology ePrint Archive, 2006

On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.
IACR Cryptology ePrint Archive, 2006

On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits.
Electronic Colloquium on Computational Complexity (ECCC), 2006

On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Lower bounds for linear locally decodable codes and private information retrieval.
Computational Complexity, 2006

On basing one-way functions on NP-hardness.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

On Teaching the Basics of Complexity Theory.
Proceedings of the Theoretical Computer Science, 2006

On Promise Problems: A Survey.
Proceedings of the Theoretical Computer Science, 2006

Concurrent Zero-Knowledge with Timing, Revisited.
Proceedings of the Theoretical Computer Science, 2006

Approximating Average Parameters of Graphs.
Proceedings of the Approximation, 2006

2005
Foundations of Cryptography - A Primer.
Foundations and Trends in Theoretical Computer Science, 2005

Bravely, Moderately: A Common Theme in Four Recent Results
Electronic Colloquium on Computational Complexity (ECCC), 2005

Approximating Average Parameters of Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2005

On Promise Problems (a survey in memory of Shimon Even [1935-2004])
Electronic Colloquium on Computational Complexity (ECCC), 2005

Short Locally Testable Codes and Proofs (Survey)
Electronic Colloquium on Computational Complexity (ECCC), 2005

Approximating Average Parameters of Graphs.
Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

Contemplations on Testing Graph Properties.
Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

Short PCPs Verifiable in Polylogarithmic Time.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Preface.
J. Cryptology, 2004

The random oracle methodology, revisited.
J. ACM, 2004

The Power of Verification Queries in Message Authentication and Authenticated Encryption.
IACR Cryptology ePrint Archive, 2004

Electronic Colloquium on Computational Complexity (ECCC), 2004

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding
Electronic Colloquium on Computational Complexity (ECCC), 2004

On Estimating the Average Degree of a Graph
Electronic Colloquium on Computational Complexity (ECCC), 2004

On the Random-Oracle Methodology as Applied to Length-Restricted Signature Schemes.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Robust pcps of proximity, shorter pcps and applications to coding.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

The Foundations of Cryptography - Volume 2, Basic Applications.
Cambridge University Press, ISBN: 0-521-83084-2, 2004

2003
Three theorems regarding testing graph properties.
Random Struct. Algorithms, 2003

On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators.
J. Cryptology, 2003

Almost k-wise independence versus k-wise independence.
Inf. Process. Lett., 2003

On the random-oracle methodology as applied to length-restricted signature schemes.
IACR Cryptology ePrint Archive, 2003

On the Implementation of Huge Random Objects.
Electronic Colloquium on Computational Complexity (ECCC), 2003

Bounds on 2-Query Codeword Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2003

Cryptography and cryptographic protocols.
Distributed Computing, 2003

Bounds on 2-Query Codeword Testing.
Proceedings of the Approximation, 2003

On the Implementation of Huge Random Objects.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

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

Zero-Knowledge twenty years after its invention.
IACR Cryptology ePrint Archive, 2002

The GGM Construction does NOT yield Correlation Intractable Function Ensembles.
IACR Cryptology ePrint Archive, 2002

Zero-Knowledge twenty years after its invention
Electronic Colloquium on Computational Complexity (ECCC), 2002

Locally Testable Codes and PCPs of Almost-Linear Length
Electronic Colloquium on Computational Complexity (ECCC), 2002

On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators
Electronic Colloquium on Computational Complexity (ECCC), 2002

Almost k-wise independence versus k-wise independence.
Electronic Colloquium on Computational Complexity (ECCC), 2002

The GGM Construction does NOT yield Correlation Intractable Function Ensembles.
Electronic Colloquium on Computational Complexity (ECCC), 2002

Derandomization that is rarely wrong from short advice that is typically good
Electronic Colloquium on Computational Complexity (ECCC), 2002

On interactive proofs with a laconic prover.
Computational Complexity, 2002

Property Testing in Bounded Degree Graphs.
Algorithmica, 2002

Concurrent zero-knowledge with timing, revisited.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Locally Testable Codes and PCPs of Almost-Linear Length.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Zero-Knowledge.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Universal Arguments and their Applications.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
Concurrent Zero-Knowledge With Timing, Revisited.
IACR Cryptology ePrint Archive, 2001

On the (Im)possibility of Obfuscating Programs.
IACR Cryptology ePrint Archive, 2001

Resettably-Sound Zero-Knowledge and its Applications.
IACR Cryptology ePrint Archive, 2001

Universal Arguments and their Applications.
IACR Cryptology ePrint Archive, 2001

Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.
Electronic Colloquium on Computational Complexity (ECCC), 2001

Universal Arguments and their Applications.
Electronic Colloquium on Computational Complexity (ECCC), 2001

Concurrent Zero-Knowledge With Timing, Revisited
Electronic Colloquium on Computational Complexity (ECCC), 2001

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval
Electronic Colloquium on Computational Complexity (ECCC), 2001

On the (Im)possibility of Obfuscating Programs
Electronic Colloquium on Computational Complexity (ECCC), 2001

On Interactive Proofs with a Laconic Prover
Electronic Colloquium on Computational Complexity (ECCC), 2001

Three Theorems regarding Testing Graph Properties.
Electronic Colloquium on Computational Complexity (ECCC), 2001

On Interactive Proofs with a Laconic Prover.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Three Theorems Regarding Testing Graph Properties.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Resettably-Sound Zero-Knowledge and its Applications.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Session-Key Generation Using Human Passwords Only.
Proceedings of the Advances in Cryptology, 2001

On the (Im)possibility of Obfuscating Programs.
Proceedings of the Advances in Cryptology, 2001

The Foundations of Cryptography - Volume 1, Basic Techniques.
Cambridge University Press, ISBN: 0-521-79172-3, 2001

2000
Chinese remaindering with errors.
IEEE Trans. Information Theory, 2000

Learning Polynomials with Queries: The Highly Noisy Case.
SIAM J. Discrete Math., 2000

A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
SIAM J. Comput., 2000

Preface.
J. Cryptology, 2000

On the Limits of Nonapproximability of Lattice Problems.
J. Comput. Syst. Sci., 2000

Uniform Generation of NP-Witnesses Using an NP-Oracle.
Inf. Comput., 2000

On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators.
IACR Cryptology ePrint Archive, 2000

Session-Key Generation using Human Passwords Only.
IACR Cryptology ePrint Archive, 2000

Candidate One-Way Functions Based on Expander Graphs.
IACR Cryptology ePrint Archive, 2000

On Security Preserving Reductions - Revised Terminology.
IACR Cryptology ePrint Archive, 2000

Candidate One-Way Functions Based on Expander Graphs
Electronic Colloquium on Computational Complexity (ECCC), 2000

On Pseudorandomness with respect to Deterministic Observers.
Electronic Colloquium on Computational Complexity (ECCC), 2000

On Testing Expansion in Bounded-Degree Graphs
Electronic Colloquium on Computational Complexity (ECCC), 2000

Simplified derandomization of BPP using a hitting set generator.
Electronic Colloquium on Computational Complexity (ECCC), 2000

The Random Oracle Methodology, Revisited
CoRR, 2000

Testing Monotonicity.
Combinatorica, 2000

Resettable zero-knowledge (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

On Pseudorandomness with respect to Deterministic Observes.
ICALP Satellite Workshops, 2000

Pseudorandomness.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999
Computational Sample Complexity.
SIAM J. Comput., 1999

Computational Indistinguishability: A Sample Hierarchy.
J. Comput. Syst. Sci., 1999

The Graph Clustering Problem has a Perfect Zero-Knowledge Interactive Proof.
Inf. Process. Lett., 1999

Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors.
Inf. Process. Lett., 1999

Chinese Remaindering with Errors.
IACR Cryptology ePrint Archive, 1999

Interleaved Zero-Knowledge in the Public-Key Model.
IACR Cryptology ePrint Archive, 1999

Resettable Zero-Knowledge.
IACR Cryptology ePrint Archive, 1999

Resettable Zero-Knowledge.
Electronic Colloquium on Computational Complexity (ECCC), 1999

Interleaved Zero-Knowledge in the Public-Key Model.
Electronic Colloquium on Computational Complexity (ECCC), 1999

Improved Testing Algorithms for Monotonicity.
Electronic Colloquium on Computational Complexity (ECCC), 1999

Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK
Electronic Colloquium on Computational Complexity (ECCC), 1999

Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors.
Electronic Colloquium on Computational Complexity (ECCC), 1999

A Sublinear Bipartiteness Tester for Bounded Degree Graphs.
Combinatorica, 1999

Quantifying Knowledge Complexity.
Computational Complexity, 1999

Chinese Remaindering with Errors.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Improved Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Randomization, 1999

Improved Testing Algorithms for Monotonicity.
Proceedings of the Randomization, 1999

Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK.
Proceedings of the Advances in Cryptology, 1999

Stateless Evaluation of Pseudorandom Functions: Security beyond the Birthday Barrier.
Proceedings of the Advances in Cryptology, 1999

Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Deterministic Amplification of Space-Bounded Probabilistic Algorithms.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
Computational Indistinguishability: Algorithms vs. Circuits.
Theor. Comput. Sci., 1998

Computational Complexity and Knowledge Complexity.
SIAM J. Comput., 1998

Fault-Tolerant Computation in the Full Information Model.
SIAM J. Comput., 1998

Free Bits, PCPs, and Nonapproximability-Towards Tight Results.
SIAM J. Comput., 1998

Efficient approximation of product distributions.
Random Struct. Algorithms, 1998

Property Testing and its Connection to Learning and Approximation.
J. ACM, 1998

Private Information Retrieval.
J. ACM, 1998

On the Complexity of Interactive Proofs with Bounded Communication.
Inf. Process. Lett., 1998

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof.
IACR Cryptology ePrint Archive, 1998

Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK.
IACR Cryptology ePrint Archive, 1998

On the possibility of basing Cryptography on the assumption that P ≠ NP.
IACR Cryptology ePrint Archive, 1998

The Random Oracle Methodology, Revisited.
IACR Cryptology ePrint Archive, 1998

Deterministic Amplification of Space Bounded Probabilistic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 1998

Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK
Electronic Colloquium on Computational Complexity (ECCC), 1998

Chinese Remaindering with Errors
Electronic Colloquium on Computational Complexity (ECCC), 1998

Learning Polynomials with Queries - The Highly Noisy Case.
Electronic Colloquium on Computational Complexity (ECCC), 1998

Uniform Generation of NP-witnesses using an NP-oracle.
Electronic Colloquium on Computational Complexity (ECCC), 1998

Computational Indistinguishability: A Sample Hierarchy
Electronic Colloquium on Computational Complexity (ECCC), 1998

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
Electronic Colloquium on Computational Complexity (ECCC), 1998

Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

A Sublinear Bipartiteness Tester for Bunded Degree Graphs.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On the Limits of Non-Approximability of Lattice Problems.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Random Oracle Methodology, Revisited (Preliminary Version).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Testing Monotonicity.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop.
Proceedings of the Advances in Cryptology, 1998

Computational Indistinguishability: A Sample Hierarchy.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

Modern Cryptography, Probabilistic Proofs and Pseudorandomness.
Algorithms and Combinatorics 17, Springer, ISBN: 978-3-540-64766-9, 1998

1997
Theory of computing: a scientific perspective (extended abstract).
SIGACT News, 1997

Tiny families of functions with random properties: A quality-size trade-off for hashing.
Random Struct. Algorithms, 1997

On Universal Learning Algorithms.
Inf. Process. Lett., 1997

Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop.
IACR Cryptology ePrint Archive, 1997

A Probabilistic Error-Correcting Scheme.
IACR Cryptology ePrint Archive, 1997

Notes on Levin's Theory of Average-Case Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 1997

Combinatorial Property Testing (a survey).
Electronic Colloquium on Computational Complexity (ECCC), 1997

Another proof that BPP subseteq PH (and more).
Electronic Colloquium on Computational Complexity (ECCC), 1997

On the Limits of Non-Approximability of Lattice Problems
Electronic Colloquium on Computational Complexity (ECCC), 1997

Computational Sample Complexity
Electronic Colloquium on Computational Complexity (ECCC), 1997

A Sample of Samplers - A Computational Perspective on Sampling (survey).
Electronic Colloquium on Computational Complexity (ECCC), 1997

Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.
Electronic Colloquium on Computational Complexity (ECCC), 1997

Property Testing in Bounded Degree Graphs.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Probabilistic Proof Systems - A Survey.
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Combinatorial property testing (a survey).
Proceedings of the Randomization Methods in Algorithm Design, 1997

Public-Key Cryptosystems from Lattice Reduction Problems.
Proceedings of the Advances in Cryptology, 1997

Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.
Proceedings of the Advances in Cryptology, 1997

On the Foundations of Modern Cryptography.
Proceedings of the Advances in Cryptology, 1997

Computational Sample Complexity.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996
The future of computational complexity theory: part I.
SIGACT News, 1996

On the Composition of Zero-Knowledge Proof Systems.
SIAM J. Comput., 1996

How to Construct Constant-Round Zero-Knowledge Proof Systems for NP.
J. Cryptology, 1996

On-Line/Off-Line Digital Signatures.
J. Cryptology, 1996

Software Protection and Simulation on Oblivious RAMs.
J. ACM, 1996

Public-Key Cryptosystems from Lattice Reduction Problems.
IACR Cryptology ePrint Archive, 1996

Collision-Free Hashing from Lattice Problems.
IACR Cryptology ePrint Archive, 1996

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof.
IACR Cryptology ePrint Archive, 1996

Computational Indistinguishability - Algorithms vs. Circuits.
Electronic Colloquium on Computational Complexity (ECCC), 1996

Property Testing and its connection to Learning and Approximation
Electronic Colloquium on Computational Complexity (ECCC), 1996

Public-Key Cryptosystems from Lattice Reduction Problems
Electronic Colloquium on Computational Complexity (ECCC), 1996

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof.
Electronic Colloquium on Computational Complexity (ECCC), 1996

A Combinatorial Consistency Lemma with application to the PCP Theorem
Electronic Colloquium on Computational Complexity (ECCC), 1996

Collision-Free Hashing from Lattice Problems
Electronic Colloquium on Computational Complexity (ECCC), 1996

On the Circuit Complexity of Perfect Hashing
Electronic Colloquium on Computational Complexity (ECCC), 1996

On the Message Complexity of Interactive Proof Systems
Electronic Colloquium on Computational Complexity (ECCC), 1996

Theory of Computing: A Scientific Perspective.
ACM Comput. Surv., 1996

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Property Testing and Its Connection to Learning and Approximation.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Lower Bounds for Sampling Algorithms for Estimating the Average.
Inf. Process. Lett., 1995

Three XOR-Lemmas - An Exposition
Electronic Colloquium on Computational Complexity (ECCC), 1995

On Yao's XOR-Lemma
Electronic Colloquium on Computational Complexity (ECCC), 1995

On Constructing 1-1 One-Way Functions
Electronic Colloquium on Computational Complexity (ECCC), 1995

Free Bits, PCP and Non-Approximability - Towards Tight Results
Electronic Colloquium on Computational Complexity (ECCC), 1995

Incremental cryptography and application to virus protection.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Learning Polynomials with Queries: The Highly Noisy Case.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Private Information Retrieval.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Free Bits, PCPs and Non-Approximability - Towards Tight Results.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs.
Proceedings of the Advances in Cryptology, 1995

1994
A taxonomy of proof systems (part 2).
SIGACT News, 1994

Definitions and Properties of Zero-Knowledge Proof Systems.
J. Cryptology, 1994

The Random Oracle Hypothesis Is False.
J. Comput. Syst. Sci., 1994

Probabilistic Proof Systems (A Survey)
Electronic Colloquium on Computational Complexity (ECCC), 1994

Computational Complexity and Knowledge Complexity
Electronic Colloquium on Computational Complexity (ECCC), 1994

Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing
Electronic Colloquium on Computational Complexity (ECCC), 1994

Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Computational complexity and knowledge complexity (extended abstract).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Incremental Cryptography: The Case of Hashing and Signing.
Proceedings of the Advances in Cryptology, 1994

1993
On the Existence of Pseudorandom Generators.
SIAM J. Comput., 1993

Addendum to "Simple Construction of Almost k-wise Independent Random Variables".
Random Struct. Algorithms, 1993

A Perfect Zero-Knowledge Proof System for a Problem Equivalent to the Discrete Logarithm.
J. Cryptology, 1993

A Uniform-Complexity Treatment of Encryption and Zero-Knowledge.
J. Cryptology, 1993

Bounds on Tradeoffs Between Randomness and Communication Complexity.
Computational Complexity, 1993

Randomness in Interactive Proofs.
Computational Complexity, 1993

Asynchronous secure computation.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992
Sparse Pseudorandom Distributions.
Random Struct. Algorithms, 1992

Simple Construction of Almost k-wise Independent Random Variables.
Random Struct. Algorithms, 1992

On the Theory of Average Case Complexity.
J. Comput. Syst. Sci., 1992

On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap Between Determinism and Randomization.
J. Comput. Syst. Sci., 1992

Approximations of General Independent Distributions
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On the Complexity of Global Computation in the Presence of Link Failures: The Case of Uni-Directional Faults.
Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992

Towards a Computational Theory of Statistical Tests (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

On Defining Proofs of Knowledge.
Proceedings of the Advances in Cryptology, 1992

1991
Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems.
J. ACM, 1991

On the Complexity of Computation in the Presence of Link Failures: The Case of a Ring.
Distributed Computing, 1991

Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection.
Distributed Computing, 1991

Quantifying Knowledge Complexity
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Fault-tolerant Computation in the Full Information Model (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
J. ACM, April, 1990

A fair protocol for signing contracts.
IEEE Trans. Information Theory, 1990

The Best of Both Worlds: Guaranteeing Termination in Fast Randomized Byzantine Agreement Protocols.
Inf. Process. Lett., 1990

A Note on Computational Indistinguishability.
Inf. Process. Lett., 1990

On the number of monochromatic close pairs of beads in a rosary.
Discrete Mathematics, 1990

An Improved Parallel Algorithm for Integer GCD.
Algorithmica, 1990

A Quantitative Approach to Dynamic Networks.
Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, 1990

On the Composition of Zero-Knowledge Proof Systems.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

Security Preserving Amplification of Hardness
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Bounds on Tradeoffs between Randomness and Communication Complexity
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Randomness in Interactive Proofs
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Simple Constructions of Almost k-Wise Independent Random Variables
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
On the power of two-point based sampling.
J. Complexity, 1989

On Completeness and Soundness in Interactive Proof Systems.

Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection.
Proceedings of the Distributed Algorithms, 1989

A Hard-Core Predicate for all One-Way Functions
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

On the Theory of Average Case Complexity
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Source to Destination Communication in the Presence of Faults.
Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989

Sparse Pseudorandom Distributions.
Proceedings of the Advances in Cryptology, 1989

On-Line/Off-Line Digital Schemes.
Proceedings of the Advances in Cryptology, 1989

On the Theory of Average Case Complexity (abstract).
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity.
SIAM J. Comput., 1988

RSA and Rabin Functions: Certain Parts are as Hard as the Whole.
SIAM J. Comput., 1988

On the Existence of Pseudorandom Generators (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

On the Existence of Pseudorandom Generators.
Proceedings of the Advances in Cryptology, 1988

A Perfect Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm.
Proceedings of the Advances in Cryptology, 1988

Everything Provable is Provable in Zero-Knowledge.
Proceedings of the Advances in Cryptology, 1988

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
Acta Inf., 1987

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Towards a Theory of Software Protection and Simulation by Oblivious RAMs
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

On the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization.
Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987

Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

How to Solve any Protocol Problem - An Efficiency Improvement.
Proceedings of the Advances in Cryptology, 1987

1986
How to construct random functions.
J. ACM, 1986

The Effect of Link Failures on Computations in Asynchronous Rings.
Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986

Proofs that Release Minimum Knowledge.
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design.
Proceedings of the Advances in Cryptology, 1986

Towards a Theory of Software Protection.
Proceedings of the Advances in Cryptology, 1986

Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme.
Proceedings of the Advances in Cryptology, 1986

1985
On the Power of Cascade Ciphers
ACM Trans. Comput. Syst., 1985

A Randomized Protocol for Signing Contracts.
Commun. ACM, 1985

A Fair Protocol for Signing Contracts (Extended Abstract).
Proceedings of the Automata, 1985

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

On the Security of Ping-Pong Protocols when Implemented using the RSA.
Proceedings of the Advances in Cryptology, 1985

The Bit Security of Modular Squaring Given Partial Factorization of the Modulos.
Proceedings of the Advances in Cryptology, 1985

1984
Correction to 'DES-like functions can generate the alternating group' (Nov 83 863-865).
IEEE Trans. Information Theory, 1984

On the np-completeness of certain network testing problems.
Networks, 1984

How to Construct Random Functions (Extended Abstract)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

On Concurrent Identification Protocols.
Proceedings of the Advances in Cryptology: Proceedings of EUROCRYPT 84, 1984

On the Number of Close-and-Equal Pairs of Bits in a String.
Proceedings of the Advances in Cryptology: Proceedings of EUROCRYPT 84, 1984

On the Cryptographic Applications of Random Functions.
Proceedings of the Advances in Cryptology, 1984

RSA/Rabin Least Significant Bits are 1/2 + 1/(poly(log N)) Secure.
Proceedings of the Advances in Cryptology, 1984

1983
DES-like functions can generate the alternating group.
IEEE Trans. Information Theory, 1983

On the Security of Multi-Party Ping-Pong Protocols
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Electronic Wallet.
Proceedings of the Advances in Cryptology, 1983

On the Power of Cascade Ciphers.
Proceedings of the Advances in Cryptology, 1983

A Simple Protocol for Signing Contracts.
Proceedings of the Advances in Cryptology, 1983

1982
A Randomized Protocol for Signing Contracts.
Proceedings of the Advances in Cryptology: Proceedings of CRYPTO '82, 1982

On the Security of Multi-Party Ping-Pong Protocols.
Proceedings of the Advances in Cryptology: Proceedings of CRYPTO '82, 1982

1981
The Minimum-Length Generator Sequence Problem is NP-Hard.
J. Algorithms, 1981