Next:
Preface
Work and Publications
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 ...
Oded Goldreich
2003-07-30
