**Oded Goldreich**

**July 30, 2003**

- Preface
- Graduate School (1981-83)
- The Minimum Length Generator Sequence is NP-Hard
- DES-Like Functions Can Generate the Alternating Group
- On the NP-Completeness of Certain Network-Testing Problems
- A Randomized Protocol for Signing Contracts
- On The Security of Multi-Party Ping-Pong Protocols
- A Simple Protocol for Signing Contracts
- Electronic Wallet
- On the Power of Cascade Ciphers
- On Concurrent Identification Protocols

- The Post-Doctoral Period (1983-86)
- How to Construct Random Functions
- Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle is NP-Hard
- The Weakest Pseudo-Random Generator Implies the Strongest One
- On the Number of Monochromatic and Close Beads in a Rosary
- RSA/Rabin Functions: Certain Parts are As Hard As the Whole
- On the Cryptographic Applications of Random Functions
- On the Power of Two-Point Based Sampling
- On the Complexity of Global Computation in the Presence of Link Failures - The Case of a Ring
- Electing a Leader in a Ring with Link Failures
- Unbiased Bits From Sources of Weak Randomness and Probabilistic Communication Complexity
- The Bit Extraction Problem or t-Resilient Functions
- An Improved Parallel Algorithm for Integer GCD
- A Fair Protocol for Signing Contracts
- On the Security of Ping-Pong Protocols when Implemented Using the RSA
- The Bit Security of Modular Squaring given Partial Factorization of the Modulus
- Two Remarks Concerning the GMR Signature Scheme
- Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs
- Towards a Theory of Software Protection and Simulation by Oblivious RAMs
- How to Play any Mental Game or a Completeness Theorem for Protocols with Honest Majority
- Everything Provable is Provable in Zero-Knowledge

- The Technion Period (1986-94)
- On the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization
- Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection
- How to Solve any Protocol Problem - An Efficiency Improvement
- On Completeness and Soundness in Interactive Proof Systems
- A Trade-off between Information and Communication in Broadcast Protocols
- Definitions and Properties of Zero-Knowledge Proof Systems
- On the Existence of Pseudorandom Generators
- A Perfect Zero-Knowledge Proof for a Decision Problem Equivalent to Discrete Logarithm
- On-line/Off-line Digital signatures
- Hard-core Predicates for any One-Way Function
- On the Theory of Average Case Complexity
- The Best of Both Worlds: Guaranteeing Termination in Fast Randomized Byzantine Agreement Protocols
- On the Composition of Zero-Knowledge Proof Systems
- A Note on Computational Indistinguishability
- Quantifying Knowledge Complexity
- On Sparse Pseudorandom Ensembles
- How to Construct Constant-Round Zero-Knowledge Proof Systems for NP
- Source to Destination Communication in the Presence of Faults
- A Uniform Complexity Treatment of Encryption and Zero-Knowledge
- A Quantitative Approach to Dynamic Networks
- Security Preserving Amplification of Hardness
- Simple Constructions of Almost k-wise Independent Random Variables
- Bounds on Tradeoffs between Randomness and Communication Complexity
- Randomness in Interactive Proofs
- The Random Oracle Hypothesis is False
- Fault-tolerant Computations without Assumptions: the Two-party Case
- Approximations of General Independent Distributions
- Towards a Computational Theory of Statistical Tests
- On the Complexity of Global Computation in the Presence of Link Failures: the case of Unidirectional Faults
- On Defining Proofs of Knowledge
- Proofs of Computational Ability
- Asynchronous Secure Computation
- Lower Bounds for Sampling Algorithms for Estimating the Average
- Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing
- Knowledge Complexity and Computational Complexity

- The First 1.5 Years at Weizmann (1994-96)
- Incremental Cryptography: the Case of Hashing and Signing
- A Combinatorial Consistency Lemma with application to the PCP Theorem
- Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs
- On Yao's XOR-Lemma
- On Constructing 1-1 One-way Functions
- Incremental Cryptography and Application to Virus Protection
- Private Information Retrieval
- Free Bits, PCPs and Non-Approximability - Towards Tight Results
- Learning polynomials with queries: the highly noisy case
- Adaptively Secure Multi-party Computation

- Sabbatical at MIT (1996-1998)
- Property Testing and its connection to Learning and Approximation
- On the Complexity of Interactive Proofs with Bounded Communication
- On the Circuit Complexity of Perfect Hashing
- On Universal Learning Algorithms
- Collision-Free Hashing from Lattice Problems
- Property Testing in Bounded Degree Graphs
- The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
- Public-Key Cryptosystems from Lattice Reduction Problems
- Computational Indistinguishability - Algorithms vs. Circuits
- Computational Sample Complexity
- Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop
- Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem
- Uniform Generation of NP-witnesses using an NP-oracle
- Another proof that BPP subseteq PH (and more)
- Computational Indistinguishability: A Sample Hierarchy
- On the Limits of Non-Approximability of Lattice Problems
- A Sublinear Bipartitness Tester for Bounded Degree Graphs
- The Random Oracle Methodology, Revisited
- Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge
- Testing Monotinicity
- Deterministic Amplification of Space Bounded Probabilistic Algorithms
- Can Statistical Zero-Knowledge be Made Non-Interactive? or On the Relationship of SZK and NISZK
- Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK
- Beyond the Birthday Barrier, Without Counters
- Chinese Remaindering with Errors

- Back at Weizmann (1998-2003)
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
- Improved Testing Algorithms for Monotonicity
- Improved Derandomization of BPP using a Hitting Set Generator
- Interleaved Zero-Knowledge in the Public-Key Model
- Resettable Zero-Knowledge
- Simplified Derandomization of BPP using a Hitting Set Generator
- On Pseudorandomness with respect to Deterministic Observers
- On Testing Expansion in Bounded-Degree Graphs
- Session-Key Generation using Human Passwords Only
- Candidate One-Way Functions Based on Expander Graphs
- On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators
- On the (Im)possibility of Software Obfuscation
- Three Theorems regarding Testing Graph Properties
- On interactive proofs with a laconic provers
- Resettably-Sound Zero-Knowledge and its Applications
- Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval
- Concurrent Zero-Knowledge With Timing, Revisited
- Universal arguments and their applications
- Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- On Chosen Ciphertext Security of Multiple Encryptions
- Locally Testable Codes and PCPs of Almost-Linear Length
- Derandomization that is rarely wrong from short advice that is typically good
- Almost k-wise independence versus k-wise independence
- The GGM Construction does NOT yield Correlation Intractable Function Ensembles
- Bounds on 2-Query Codeword Testing
- On the Implementation of Huge Random Objects
- On the random-oracle methodology as applied to length-restricted signature schemes

- Sabbatical at Radcliffe/Harvard (2003-2004)
- About this document ...