Oded Goldreich
More info
- Affiliation
- Weizmann Institute of Science
- Known for
- The GGM construction, the GMW protocol, Foundations of Cryptography
The third letter in several of theoretical cryptography's most important acronyms.
With Goldwasser and Micali, Goldreich showed in 1984 how to build a pseudorandom function from a pseudorandom generator — the GGM construction, which turns a single source of randomness into a whole family of keyed functions. With Micali and Avi Wigderson he showed in 1986 that every statement in NP has a zero-knowledge proof, and the following year that any computation can be carried out securely by parties who don't trust one another (the GMW protocol).
The Goldreich–Levin theorem (1989) extracts a hard-core bit from any one-way function. His two-volume Foundations of Cryptography is the standard reference for anyone who wants the proofs and not just the results; that it is heavy going is a known fact, not a review.