Oded Goldreich

Oded Goldreich (Hebrew: עודד גולדרייך‎; b. 1957) is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation and are, specifically, the interplay of randomness and computation, the foundations of cryptography, and computational complexity theory. He won the Knuth Prize in 2017[1] and was selected in 2021 to receive the Israel Prize in mathematics.

Oded Goldreich
עודד גולדרייך
Oded Goldreich.jpg
Oded Goldreich, 2006
Born (1957-02-04) 4 February 1957 (age 64)
Alma materTechnion,
Weizmann Institute
Known forZero-knowledge proof
Spouse(s)Dana Ron
AwardsKnuth Prize (2017)
Scientific career
Doctoral advisorShimon Even
Doctoral studentsBoaz Barak
Ran Canetti
Yehuda Lindell


Goldreich has contributed to the development of pseudorandomness,[2][3]zero knowledge proofs,[4] secure function evaluation,[5] property testing,[6] and other areas in cryptography[7][8] and computational complexity.[9][10][11]

Goldreich has also authored several books including: Foundations of Cryptography[12] which comes in two volumes (volume 1 in 2001[13] and volume 2 in 2004), Computational Complexity: A Conceptual Perspective[14] (2008), and Modern Cryptography, Probabilistic Proofs and Pseudorandomness[15] (1998).[13]


Goldreich received the Knuth prize in 2017 for "fundamental and lasting contributions to theoretical computer science in many areas including cryptography, randomness, probabilistically checkable proofs, inapproximability, property testing as well as complexity theory in general. Goldreich has, in addition to his outstanding research contributions, advanced these fields through many survey articles and several first class textbooks. He has contributed eminent results, new basic definitions and pointed to new directions of research. Goldreich has been one of the driving forces for the theoretical computer science community for three decades."[1]

Israel Prize and controversyEdit

In 2021 he was selected by an Israel Prize committee to win the Israel Prize in mathematics. Education Minister Yoav Galant vetoed his selection over Goldreich's alleged support of the boycott, divestment and sanctions movement (BDS) against Israel. One of the reasons for the decision was a letter signed by Goldreich calling German parliament not to equate BDS with Anti-Semitism.[16] [17] However, according to Goldreich, he did not support BDS but instead signed a petition calling for the halt of EU funding for the Israeli Ariel University on the occupied West Bank.[18] The prize committee petitioned to the Supreme Court of Israel to ensure that Goldreich will win the prize.[19] On 8 April 2021 Israel's Supreme Court of Justice ruled in favor of Galant's petition so that Goldreich cannot receive the prize this year and gave Galant a month to further examine the issue.[20] On 11 April 2021 a former Israeli Prize Award winner, in 2004[21] Professor David Harel, decided to share his award with Professor Goldreich, as a petition act against the official governmental authorities' decision - not awarding the prize in 2021 for Professor Goldreich.[22] In August 2021 the Supreme Court voided Galant's decision to deny Goldreich the Israel Prize and ruled that the matter should be resolved by the new Minister of Education Yifat Shasha-Biton.[23] In November 2021, Shasha-Biton announced that she would block Goldreich from receiving the prize.[24]

In an editorial, the Jerusalem Post wrote that Goldreich's "[c]alling for the boycott of professional colleagues ... is a red line that shouldn't be crossed".[25] A Haaretz editorial said that Shasha-Biton's decision meant "the most prestigious prize awarded by Israel will not be the mark of scientific excellence but of loyalty to the government".[26]

Personal lifeEdit

He is married to Dana Ron, who is a computer scientist at Tel Aviv University, and has collaborated with Ron on approximation algorithms.[6]

See alsoEdit


  1. ^ a b "2017 Knuth prize is Awarded to Oded Goldreich" (PDF) (Press release). ACM Special Interest Group on Algorithms and Computation Theory. Archived from the original (PDF) on 22 June 2017. Retrieved 23 June 2017.
  2. ^ Oded Goldreich, Shafi Goldwasser, and Silvio Micali. "How to Construct Random Functions" Journal of the ACM, Vol. 33, No. 4, Oct. 1986, pages 792-807.
  3. ^ Oded Goldreich and Leonid Levin. Hard-core Predicates for any One-Way Function. In the proceedings of the 21st ACM Symp. on Theory of Computing, pages 25-32, 1989.
  4. ^ Oded Goldreich, Silvio Micali, and Avi Wigderson. "Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs" Journal of the ACM, Vol. 38, No. 3, July 1991, pages 691-729.
  5. ^ Oded Goldreich, Silvio Micali, and Avi Wigderson. How to Play any Mental Game or a Completeness Theorem for Protocols with Honest Majority. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 218-229, ACM, 1987.
  6. ^ a b Oded Goldreich, Shafi Goldwasser, and Dana Ron. 1998 Property Testing and its connection to Learning and Approximation. Journal of the ACM, pages 653-750.
  7. ^ Chor B. (1998). "Private Information Retrieval". Journal of the ACM. 45 (6): 965–982. CiteSeerX doi:10.1145/293347.293350. S2CID 544823.
  8. ^ Goldreich O. (1996). "Software Protection and Simulation on Oblivious RAMs" (PDF). Journal of the ACM. 43 (3): 431–473. doi:10.1145/233551.233553. hdl:1721.1/103684. S2CID 7502114.
  9. ^ B. Chor and O. Goldreich. Unbiased Bits From Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM J. Comp., Vol. 17, No. 2, April 1988, pages 230-261.
  10. ^ Mihir Bellare, O. Goldreich and M. Sudan. Free Bits, PCPs and Non-Approximability -- Towards Tight Results. SIAM J. Comp., Vol. 27, No. 3, pages 804-915, June 1998.
  11. ^ Goldreich O., Sudan M. (2006). "Locally Testable Codes and PCPs of Almost-Linear Length". Journal of the ACM. 53 (4): 558–655. CiteSeerX doi:10.1145/1162349.1162351. S2CID 2179438.
  12. ^ "Foundations of Cryptography - a two-volume book [Goldreich]". www.wisdom.weizmann.ac.il.
  13. ^ a b Landau, Susan (2004). "Review of Foundations of Cryptography: Basic Tools by Oded Goldreich and Modern Cryptography, Probabilistic Proofs and Pseudorandomness by Oded Goldreich and 8 other books by various authors" (PDF). Bull. Amer. Math. Soc. (N.S.). 41 (3): 357–367. doi:10.1090/s0273-0979-04-01011-0.
  14. ^ "Computational Complexity: A Conceptual Perspective [Goldreich]". www.wisdom.weizmann.ac.il.
  15. ^ "Modern Cryptography, Probabilistic Proofs, and Pseudorandomness [Goldreich]". www.wisdom.weizmann.ac.il.
  16. ^ i24NEWS. "Israel Prize Committee Files Petition Against Edu. Minister For Meddling In Award Decision". I24news. Retrieved 20 November 2021.
  17. ^ https://www.haaretz.com/embeds/pdf_upload/2019/20190516-185634.pdf
  18. ^ Ben Zion, Ilan (9 April 2021). "Israeli Computer Scientist Won't Receive Prize After Signing Petition". manufacturing.net. Retrieved 1 May 2021.
  19. ^ "Israel Prize committee petitions top court over minister's veto of math winner". timesofisrael.com. 30 March 2021. Members object to Education Minister Gallant’s efforts to prevent award from going to Oded Goldreich over his alleged BDS support
  20. ^ "Israel's Supreme Court says pro-BDS professor ineligible to receive prestigious prize". i24news.tv. 8 April 2021.
  21. ^ "נימוקי השופטים". cms.education.gov.il. Retrieved 12 April 2021.
  22. ^ "הפרופ' למתמטיקה קיבל פסלון מחתן 2004: "לשר יש זכות לשלול את פרס הליכוד"". ynet (in Hebrew). 11 April 2021. Retrieved 12 April 2021.
  23. ^ "בג"ץ ביטל את החלטתו של גלנט למנוע מפרופ' עודד גולדרייך את פרס ישראל". Maariv (in Hebrew). 12 August 2021. Retrieved 12 August 2021.
  24. ^ "Education minister withholds Israel Prize from academic accused of backing boycott". The Times of Israel. 18 November 2021. Retrieved 18 November 2021.
  25. ^ "Goldreich crossed a red line by calling for boycott - editorial". The Jerusalem Post. Retrieved 1 December 2021.
  26. ^ "The Israel Prize Is Not About Excellence, but Government Loyalty". Haaretz. Retrieved 1 December 2021 – via Haaretz.

External linksEdit