Few of my old paper (predating 1990) and almost all of my papers postdating 1990 can be found here. Also available are partial lists of

- most RECENT papers
- CRYPTOGRAPHIC related papers
- COMPLEXITY related papers
- Property Testing related papers.
- webpages on SPECIFIC topics
- Technical SURVEYS
- Some useful trivialities
- a collection of some unpublished papers
- Non-technical ESSAYS (and opinions) (not included below)

The following papers can be obtained in PostScript or PDF (papers are ordered by the full author-list):

PDF version of all files are available at the directory PSX; I'm in the process of making links on each individual entry below. So far, I reached the letter G...

- A. Akavia, O. Goldreich, S. Goldwasser, and D. Moshkovitz, On Basing One-Way Functions on NP-Hardness, 2005.
- W. Alexi, B. Chor, O. Goldreich, and C.P. Schnorr, On the hardness of the least-signficant bits of the RSA and Rabin functions, 1984.
- N. Alon, O. Goldreich J. Hastad and R. Peralta, Simple Constructions of Almost $k$-wise Independent Random Variables, June 1992.
- N. Alon, O. Goldreich Y. Mansour, Almost $k$-wise independence versus $k$-wise independence, 2002
- L. Avigad and O. Goldreich, Testing Graph Blow-Up, March 2010.
- B. Awerbuch, O. Goldreich, D. Peleg, and R. Vainish, A Trade-off between Information and Communication in Broadcast Protocols, June 1989. [in PDF].
- B. Barak and O. Goldreich, Universal Arguments and their Applications, 2001.
- B. Barak, O. Goldreich, S. Goldwasser and Y. Lindell, Resettably-Sound Zero-Knowledge and its Applications, 2001. [in PDF].
- B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan and K. Yang, On the (Im)possibility of Obfuscating Programs, 2001.
- K. Barhum, O. Goldreich, and A. Shraibman, On approximating the average distance between points, 2007.
- R. Bar-Yehuda, O. Goldreich, and A. Itai, On the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization (abstract and errarata), 1992.
- Z. Bar-Yossef, O. Goldreich, and A. Wigderson, Deterministic Amplification of Space Bounded Probabilistic Algorithms, 1998. [in PDF].
- M. Bellare and O. Goldreich,
On Defining Proofs of Knowledge, 1992.

See also our notes on Proofs of Computational Ability (1992). [in PDF]. - M. Bellare and O. Goldreich, On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge, 2006.
- M. Bellare, O. Goldreich and S. Goldwasser, Randomness in Interactive Proofs, August 1991. [in PDF]. Addendum, May 1997. [in PDF].
- M. Bellare, O. Goldreich and S. Goldwasser, Incremental Cryptography, 1995.
- M. Bellare, O. Goldreich and H. Krawczyk, Stateless evaluation of pseudorandom functions: Security beyond the birthday barrier, 1999. (Available in multiple formats from Mihir's page.) [in PDF].
- M. Bellare, O. Goldreich and A. Mityagin, The Power of Verification Queries in Message Authentication and Authenticated Encryption, 2004.
- M. Bellare, O. Goldreich and E. Petrank, Uniform Generation of NP-witnesses using an NP-oracle, 1998. [in PDF].
- M. Bellare, O. Goldreich and M. Sudan, Free Bits, PCPs and Non-Approximability, 1995.
- S. Ben-David, B. Chor, O. Goldreich and M. Luby, On the Theory of Average Case Complexity, 1989. [in PDF].
- M. Ben-Or, R. Canetti and O. Goldreich, Asynchronous Secure Computation, 1993. See Ran Canetti's PhD Thesis, 1995. (over 100 pages, 1.4M) [in PDF].
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan, Robust PCPs of Proximity, Shorter PCPs and Applications to Coding, March 2004. [in PDF].
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan, Short PCPs verifiable in polylogarithmic time, 2005 [in PDF].
- E. Ben-Sasson, O. Goldreich and M. Sudan, Bounds on 2-Query Codeword Testing, 2003. [in PDF].
- M. Blum and O. Goldreich, Towards a Computational Theory of Statistical Tests, 1992. [in PDF].
- Z. Brakerski and O. Goldreich, From absolute distinguishability to positive distinguishability, March 2009.
- R. Canetti, G. Even and O. Goldreich, Lower Bounds for Sampling Algorithms for Estimating the Average, October 1994. [in PDF].
- R. Canetti, U. Feige, O. Goldreich and M. Naor, Adaptively Secure Multi-party Computation, TR-682, LCS/MIT, 1996. [in PDF].
- R. Canetti and O. Goldreich, Bounds on Tradeoffs between Randomness and Communication Complexity, August 1990. [in PDF].
- R. Canetti, O. Goldreich, S. Goldwasser and S. Micali, Resettable Zero-Knowledge, 1999. [in PDF].
- R. Canetti, O. Goldreich, S. Halevi, The Random Oracle Methodology, Revisited, March 1998. [in PDF].
- R. Canetti, O. Goldreich, S. Halevi, On the random-oracle methodology as applied to length-restricted signature schemes, July 2003. [in PDF].
- R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad, D. Ranjan and P. Rohatgi, The Random Oracle Hypothesis is False, July 1992. [in PDF].
- B. Chor, J. Freidmann, O. Goldreich, J. Hastad, S. Rudich and R. Smolensky, The Bit Extraction Problem or t-Resilient Functions, 1985. [in PDF].
- B. Chor and O. Goldreich, On the power of two-points based sampling, 1985. [in PDF].
- B. Chor and O. Goldreich, Unbiased Bits From Sources of Weak Randomness and Probabilistic Communication Complexity, 1986.
- B. Chor and O. Goldreich, An Improved Parallel Algorithm for Integer GCD, 1990.
- B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan, Private Information Retrieval, 1995. [in PDF].
- A. Czumaj, O. Goldreich, D. Ron, C. Seshadhri, A. Shapira, and C. Sohler, Finding Cycles and Trees in Sublinear Time, April 2010.
- I. Damgard, O. Goldreich, T. Okamoto and A. Wigderson,
Honest Verifier vs Dishonest Verifier
in Public Coin Zero-Knowledge Proofs (Extended Abstract),
September 1995.
[in PDF].

See also partial version by Damgard, Goldreich, and Wigderson, November 1994. [in PDF]. - I. Damgard, O. Goldreich and A. Wigderson, Information Theory versus Complexity Theory: Another Test Case, September 1995. [in PDF].
- S. Decatur, O. Goldreich, and D. Ron, Computational Sample Complexity, April 1997. [in PDF].
- Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky, Improved Testing Algorithms for Monotonicity, 1999. [in PDF].
- G. Even, O. Goldreich, M. Luby, N. Nisan and B. Velickovic, Approximations of General Independent Distributions, 1992. [in PDF].
- S. Even and O. Goldreich, On the Security of Multi-Party Ping-Pong Protocols, 1983.
- S. Even, O. Goldreich and S. Micali, On-Line/Off-Line Digital Signatures, revised 1994. [in PDF].
- D.M. Freeman, O. Goldreich, E. Kiltz, A. Rosen, and G. Segev, More Constructions of Lossy and Correlation-Secure Trapdoor Functions, 2010.
- M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos, On Completeness and Soundness in Interactive Proof Systems, 1989. [in PDF].
- O. Goldreich, Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle is NP-Hard, 1984.
- O. Goldreich, Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme, 1986. [in PDF].
- O. Goldreich,
Randomness, Interaction, Proofs and Zero-Knowledge (a survey), 1987.

See a revised version of the part on Computational Randomness, 1987 (rev. 1997). - O. Goldreich, Towards a Theory of Average Case Complexity, 1988.

See revised Notes on Levin's Theory of Average-Case Complexity, 1997. - O. Goldreich, A Note on Computational Indistinguishability, 1989.
- O. Goldreich, Three XOR-Lemmas - An Exposition, July 1991.
- O. Goldreich, A Uniform-Complexity Treatment of Encryption and Zero-Knowledge, July 1991.
- O. Goldreich, Probabilistic Proof Systems (survey), 1995.
- O. Goldreich, The Graph Clustering Problem has a Perfect Zero-Knowledge Proof, October 1996.
- O. Goldreich, A Computational Perspective on Sampling (survey), May 1997.
- O. Goldreich, The Foundations of Cryptography - An Essay, June 1997.
- O. Goldreich, Combinatorial Property Testing - A Survey, 1997.
- O. Goldreich, Review of the AS+ALMSS papers (NP=PCP[log,O(1)]), 1999.
- O. Goldreich, Pseudorandomness (a survey), 1999. (An extended version, 2000.)
- O. Goldreich, Preface to Special Issue on General Secure Multi-Party Computation, 1999.
- O. Goldreich, On Security Preserving Reductions - Revised Terminology, Jan. 2000.
- O. Goldreich, Computational Complexity - a brief survey, 2000.
- O. Goldreich, Candidate One-Way Functions Based on Expander Graphs, 2000.
- O. Goldreich, A Taste of Randomized Computations, 1998, adapted 2001.
- O. Goldreich, Cryptography and Cryptographic Protocols (survey), 2001.
- O. Goldreich, Concurrent Zero-Knowledge With Timing, Revisited, 2001.
- O. Goldreich, Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, 2001.
- O. Goldreich, The GGM Construction does NOT yield Correlation Intractable Function Ensembles, 2002.
- O. Goldreich, Zero-Knowledge twenty years after their invention (survey), 2002.
- O. Goldreich, Preface to Special Issue on Encryption in the Bounded Storage Model, 2003.
- O. Goldreich, Foundations of Cryptography (a primer), July 2004.
- O. Goldreich, Short Locally Testable Codes and Proofs (survey), July 2004.
- O. Goldreich, On Promise Problems (a survey in memory of Shimon Even), January 2005.
- O. Goldreich, Bravely, Moderately: A Common Theme in Four Recent Results, August 2005.
- O. Goldreich, On Expected Probabilistic Polynomial-Time Adversaries - A suggestion for restricted definitions and their benefits, August 2006.
- O. Goldreich, On the Average-Case Complexity of Property Testing, July 2007.
- O. Goldreich, A Candidate Counterexample to the Easy Cylinders Conjecture, March 2009.
- O. Goldreich, On Testing Computability by Small Width OBDDs, April 2010.
- O. Goldreich, In a World of P=BPP, August 2010.
- O. Goldreich, Two Comments on Targeted Canonical Derandomizers, April 2011.
- O. Goldreich, On the Effect of the Proximity Parameter on Property Testers, Feb. 2012.
- O. Goldreich, On Multiple Input Problems in Property Testing, May 2013.
- O. Goldreich, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, May 2013.
- O. Goldreich and S. Goldwasser, On the Limits of Non-Approximability of Lattice Problems, Sept. 1997.
- O. Goldreich and S. Goldwasser, On the possibility of basing Cryptography on the assumption that P neq NP, Feb. 1998.
- O. Goldreich, S. Goldwasser and S. Halevi, Using Lattice Problems in Cryptography
- O. Goldreich, S. Goldwasser, E. Lehman, D. Ron and A. Samorodnitsky, Testing Monotinicity, 1998 (improved 1999).
- O. Goldreich, S. Goldwasser and N. Linial, Fault-tolerant Computation in the Full Information Model, revised October 1995.
- O. Goldreich, S. Goldwasser and S. Micali, How to Construct Random Functions, 1984.
- O. Goldreich, S. Goldwasser and S. Micali, Interleaved Zero-Knowledge, 1999.
- O. Goldreich, S. Goldwasser and A. Nussboim, On the Implementation of Huge Random Objects, 2003.
- O. Goldreich, S. Goldwasser and D. Ron, Property Testing and its connection to Learning and Approximation, 1996.
- O. Goldreich, S. Goldwasser, and D. Ron, On the possibilities and limitations of pseudodeterministic algorithms, Aug 2012.
- O. Goldreich, T. Gur, and I. Komargodski, Strong Locally Testable Codes with Relaxed Local Decoders, Feb. 2014.
- O. Goldreich, T. Gur, and R. Rothblum, Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs, Feb. 2015.
- O. Goldreich and J. Hastad, On the Complexity of Interactive Proof with Bounded Communication, Feb. 1996. (rev. April 1997)
- O. Goldreich, A. Herzberg, and A. Segall, A Quantitative Approach to Dynamic Networks, 1992.
- O. Goldreich, R. Impagliazzo, L.A. Levin, R. Venkatesan and D. Zuckerman, Security Preserving Amplification of Hardness, August 1990.
- O. Goldreich and R. Izsak, Monotone Circuits: One-Way Functions versus Pseudorandom Generators, Sept 2011.
- O. Goldreich, B. Juba, and M. Sudan, A Theory of Goal-Oriented Communication, Sept 2009.
- O. Goldreich and A. Kahan, How to Construct Constant-Round Zero-Knowledge Proof Systems for NP, March 1996.
- O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan, Bounds for Linear Locally Decodable Codes and Private Information Retrieval, 2001.
- O. Goldreich and T. Kaufman, Proximity Oblivious Testing and the Role of Invariances, April 2010.
- O. Goldreich and H. Krawczyk, On Sparse Pseudorandom Distributions, 1989.
- O. Goldreich and H. Krawczyk, On the Composition of Zero-Knowledge Proof Systems, revised 1994.
- O. Goldreich, M. Krivelevich, I. Newman and E. Rozenberg, Hierarchy Theorems for Property Testing, Nov. 2008.
- O. Goldreich and L.A. Levin, Hard-core Predicates for any One-way Function, 1989.
- O. Goldreich, L.A. Levin and N. Nisan, On Constructing 1-1 One-Way Functions, June 1995.
- O. Goldreich and Y. Lindell, Session-Key Generation using Human Passwords Only, 2000.
- O. Goldreich, Y. Lustig and M. Naor, On Chosen Ciphertext Security of Multiple Encryptions, 2002.
- O. Goldreich and O. Meir The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable, 2007.
- O. Goldreich and O. Meir, Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly, Feb. 2011.
- O. Goldreich and B. Meyer, Computational Indistinguishability - Algorithms vs. Circuits, December 1996.
- O. Goldreich and S. Micali, Increasing the Expansion of Pseudorandom Generators, 1984.
- O. Goldreich, S. Micali, and A. Wigderson,
Zero-Knowledge and Secure Function Computation.
- Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs. Proceeding version appeared in 27th FOCS (1986) and a journal version in JACM (1991).
- How to Solve any Protocol Problem. Proceeding version appeared in 19th STOC (1987).

- O. Goldreich, D. Micciancio, S. Safra, and J.P. Seifert, Approximating shortest lattice vectors is not harder than approximating closest lattice vectors, 1999.
- O. Goldreich, N. Nisan and A. Wigderson, On Yao's XOR-Lemma, March 1995.
- O. Goldreich and R. Ostrovsky, Software Protection and Simulation on Oblivious RAMs, revised October 1995.
- O. Goldreich and Y. Oren, Definitions and properties of Zero-Knowledge proof systems, an old version (1992?).
- O. Goldreich, R. Ostrovsky and E. Petrank, Computational Complexity and Knowledge Complexity, revised March 1995.
- O. Goldreich and E. Petrank, Quantifying Knowledge Complexity, revised July 1996.
- O. Goldreich and E. Petrank, The Best of Both Worlds: Guaranteeing Termination in Fast Randomized Byzantine Agreement Protocols, October 1990.
- O. Goldreich, B. Pfitzmann, and R.L. Rivest, Self-Delegation with Controlled Propagation, September 1997.
- O. Goldreich and D. Ron, A Universal Learning Algorithm, June 1996.
- O. Goldreich and D. Ron, Property Testing in Bounded-Degree Graphs, 1997.
- O. Goldreich and D. Ron, A Sublinear Bipartite Tester for Bounded Degree Graphs, 1997.
- O. Goldreich and D. Ron, On Testing Expansion in Bounded-Degree Graphs, March 2000.
- O. Goldreich and D. Ron, On Estimating the Average Degree of a Graph, 2004.
- O. Goldreich and D. Ron, Approximating Average Parameters of Graphs, 2005.
- O. Goldreich and D. Ron, Algorithmic Aspects of Property Testing in the Dense Graphs Model, April 2008.
- O. Goldreich and D. Ron, On Proximity Oblivious Testing, April 2008.
- O. Goldreich and D. Ron, On Sample-Based Testers, Aug. 2013.
- O. Goldreich and D. Ron, On Learning and Testing Dynamic Environments, Mar. 2014.
- O. Goldreich, D. Ron and M. Sudan, Chinese Remaindering with Errors, 1998.
- O. Goldreich and R. Rothblum, Enhancements of Trapdoor Permutations, 2011.
- O. Goldreich and V. Rosen, On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators, 2000.
- O. Goldreich, R. Rubinfeld and M. Sudan, Learning polynomials with queries: the highly noisy case, 2000 [in PDF].
- O. Goldreich, and S. Safra, A Combinatorial Consistency Lemma with application to the PCP Theorem, 1996.
- O. Goldreich, A. Sahai and S. Vadhan, Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge, 1998.
- O. Goldreich, A. Sahai and S. Vadhan, Can Statistical Zero-Knowledge be Made Non-Interactive? or On the Relationship of SZK and NISZK, 1998.
- O. Goldreich and O. Sheffet, On the randomness complexity of property testing, Feb. 2007.
- O. Goldreich and I. Shinkar, Two-Sided Error Proximity Oblivious Testing, Mar. 2012.
- O. Goldreich and M. Sudan, Computational Indistinguishability: A Sample Hierarchy, March 1998.
- O. Goldreich and M. Sudan, Locally Testable Codes and PCPs of Almost-Linear Length, August 2002.
- O. Goldreich, M. Sudan and L. Trevisan, From logarithmic advice to single-bit advice, 2004.
- O. Goldreich and A. Tal, Matrix Rigidity of Random Toeplitz Matrices, May 2015.
- O. Goldreich and L. Teichner, Super-Perfect Zero-Knowledge Proofs, July 2014.
- O. Goldreich and L. Trevisan, Three Theorems regarding Testing Graph Properties, 2001.
- O. Goldreich and S. Vadhan, Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of this Class, 1998.
- O. Goldreich, S. Vadhan, and A. Wigderson, Simplified derandomization of BPP using a hitting set generator, Dec. 1999.
- O. Goldreich, S. Vadhan, and A. Wigderson, On Interactive Proofs with a Laconic Prover, 2001.
- O. Goldreich and R. Vainish, How to Solve any Protocol Problem - An Efficiency Improvement, 1987.
- O. Goldreich, E. Viola, and A. Wigderson, On Randomness Extraction in AC0, January 2015.
- O. Goldreich and A. Wigderson, Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing, 1994.
- O. Goldreich and A. Wigderson, On the Circuit Complexity of Perfect Hashing, July 1996.
- O. Goldreich and A. Wigderson, Improved derandomization of BPP using a hitting set generator, May 1999.
- O. Goldreich and A. Wigderson, On Pseudorandomness with respect to Deterministic Observers, May 2000.
- O. Goldreich and A. Wigderson, Deradomization that is rarely wrong from short advice that is typically good, 2002.
- O. Goldreich and A. Wigderson, Computational Complexity (survey), 2004.
- O. Goldreich and A. Wigderson, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, March 2013.
- O. Goldreich and A. Wigderson, On Derandomizing Algorithms that Err Extremely Rarely, Nov. 2013.
- O. Goldreich and D. Zuckerman, Another proof that BPP subseteq PH (and more), September 1997.

Back to Oded Goldreich's homepage or to the top of this page.