Professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel.
Thèmes de recherche : His main research interests are :
- The interplay of randomness and computation. Specific examples include : the study of various notions of pseudorandomness, the study of various types of probabilistic proof systems, the study of property testing, a notion of approximation for decision problems. This research tends to be classified as belonging to complexity theory, but at times it is very relevant to the design of algorithms.
- The foundations of cryptography (study of known paradigms (resp. approaches and techniques), directed towards a better understanding and utilization of the latter ; discovery of new paradigms (resp. approaches and techniques) that overcome inherent (or seemingly inherent) limitations of the existing paradigms ; formulation of new cryptographic problems and studying them using known or new paradigms (resp. approaches and techniques).
His most important research contributions are:
- Showing (together with Silvio Micali and Avi Wigderson) how to construct zero-knowledge proof systems for NP: Zero-knowledge proofs are probabilistic and interactive proofs that efficiently demonstrate the validity of an assertion without conveying any additional knowledge. This work shows the wide applicability of zero-knowledge proofs. Most importantly, assuming the existence of one-way functions, it is shown that every set of NP-assertions (e.g., the satisfiability of propositional formulae) has a zero-knowledge proof system. [See a PR poster.]
- Showing (together with Silvio Micali and Avi Wigderson) how to solve any multi-party protocol problem: Assuming the existence of trapdoor permutations, it is shown how to construct protocols for securely computing any desirable multi-party functionality. This result either requires a majority of honest players or allows dishonest players to suspend the execution (while being detected as bad). Loosely speaking, in both cases, the protocol emulates a trusted party in an environment in which no party can be trusted.
Presenting (together with Leonid Levin) a generic hard-core predicate for any one-way function: A hard-core predicate of the function f is a polynomial-time computable predicate of x that is hard to approximate from f(x). It is proved that any one-way function of the form f(x,r)=(f'(x),r) has a hard-core predicate (specifically, the inner-product mod 2 of x and r).
- Showing (together with Shafi Goldwasser and Silvio Micali) how to construct pseudorandom functions: Extending the notion of pseudorandomness to functions, it is shown how to construct pseudorandom functions, using an arbitrary pseudorandom (bit) generator. This means that a black box that stores only k secret bits can implement a function from k bit strings to k bit strings that cannot be distinguished from a random function by any poly(k)-time observer that can ``query'' the function on arguments of its choice.
Sélection de publications : N. Alon, O. Goldreich Y. Mansour, Almost $k$-wise independence versus $k$-wise independence, 2002
E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan, Robust PCPs of Proximity, Shorter PCPs and Applications to Coding, March 2004.
E. Ben-Sasson, O. Goldreich and M. Sudan, Bounds on 2-Query Codeword Testing, 2003.
R. Canetti, O. Goldreich, S. Halevi, On the random-oracle methodology as applied to length-restricted signature schemes, July 2003.
O. Goldreich, The GGM Construction does NOT yield Correlation Intractable Function Ensembles, 2002.
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, S. Goldwasser and A. Nussboim, On the Implementation of Huge Random Objects, 2003.
O. Goldreich, Y. Lustig and M. Naor, On Chosen Ciphertext Security of Multiple Encryptions, 2002.
O. Goldreich and D. Ron, On Estimating the Average Degree of a Graph, 2004.
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. Wigderson, Deradomization that is rarely wrong from short advice that is typically good, 2002.
Books and lecture notes :
- Foundations of Cryptography:
A two-volume textbook (Vol1, 2001; Vol2, 2004).
- Modern Cryptography, Probabilistic Proofs and Pseudorandomness (1998).
- Introduction to Complexity Theory - Lecture Notes (1999 and 2002).
- Randomized Methods in Computation - Lecture Notes (2001).
GOLDREICH, ODED 