Oded Goldreich

Goldreich was born in February 1957 and grew up in Tel Aviv.[1] His mother, Clara, was a lawyer, and his father, Isidor, was an engineer who worked for the state, including on railway bridges and structures.[1]

A car accident preceded Goldreich’s release from military service in 1977.[1] When he subsequently sought to begin university studies, applications to institutions other than the Technion had already closed.[1] Rather than postpone his studies for another year, he enrolled in computer science at the Technion.[1] His entry into the subject thus followed a practical decision about where he could begin studying immediately, rather than a plan to wait for another admissions cycle.[1]

Goldreich completed his undergraduate studies in computer science during 1977–1980, followed by master’s studies in 1981–1982 and doctoral studies in 1982–1983, all at the Technion.[1] While assembling his doctoral thesis, he encountered the research of Shafi Goldwasser and Silvio Micali, an experience that changed his view of research.[1] He subsequently worked with both researchers during a postdoctoral appointment at MIT from 1983 to 1986.[1]

Goldreich held academic posts at the Technion from 1983 to 1994, progressing from lecturer to associate professor.[1] He joined the Weizmann Institute of Science in 1994, became a full professor in 1995, and held the Meir and Whiswell (Weisgal) Professorial Chair from 1998.[1] His early research collaborations included work with Goldwasser, Micali, Avi Wigderson, and Benny Chor.[1]

His research over more than three decades encompassed cryptography, computational complexity, randomness, probabilistically checkable proofs, hardness of approximation, and property testing.[1] Across these subjects, his contributions included both particular results and foundational definitions that established new directions of research.[1] The work recognized by the Israel Prize included pseudorandom functions, secure multiparty computation, software obfuscation, and property testing, together with contributions to proof systems, zero-knowledge proofs, locally testable codes, and the understanding of randomness in computation.[3]

During his postdoctoral period, Goldreich, Goldwasser, and Micali formulated the notion of a pseudorandom function.[1] Such a function can be computed efficiently, yet an observer restricted to polynomially many black-box queries cannot distinguish it from a truly random function.[1] Their paper did not stop at defining the object: it also constructed a pseudorandom function from a pseudorandom generator.[1] The combination of an efficiently computable function and its apparent randomness under the specified limits on observation was central to this contribution.[1]

Goldreich’s collaborations with Micali and Wigderson produced results in both zero-knowledge proofs and secure multiparty computation.[1] Their work showed that every problem in NP has a zero-knowledge proof under the stated cryptographic assumptions.[1] It also established that multiple parties can securely compute any efficiently computable function when a majority follow the protocol, again under the relevant cryptographic assumptions.[1] These results were among the contributions highlighted when Goldreich was selected for the Israel Prize.[1]

A 1987 paper by Goldreich, Micali, and Wigderson demonstrated how participants could securely perform any computation without learning anything beyond its result, including in circumstances where some participants might act maliciously.[4] Goldreich was then at the Technion, Wigderson at the Hebrew University of Jerusalem, and Micali at MIT.[4] The work addressed the possibility of carrying out a joint computation while limiting what the participants learned about information other than the final result.[4] Secure multiparty computation subsequently developed as a foundational achievement of modern cryptography, with their work among the field’s seminal contributions.[5]

The privacy problem addressed by secure multiparty computation can be illustrated by employees who want to determine their average salary without revealing their individual salaries to one another or to a third party.[4] The desired outcome is a shared calculation, but the individual inputs are not to be disclosed in obtaining it.[4] Goldreich later supervised Yehuda Lindell’s doctoral dissertation on secure multiparty computation at the Weizmann Institute, which Lindell began in 1998.[4]

The early practicality of such methods was limited by the computational effort they required.[4] Lindell recalled that practical use initially appeared uncertain because the calculations were inefficient; as late as 2004, a computerized comparison of two people’s ages could take several minutes.[4] Efficiency improved gradually rather than immediately.[4] Goldreich’s supervision of Lindell connected his work on the foundations of secure computation with the training of a researcher studying the subject during this period of practical limitations.[4]

Another cryptographic contribution was the Goldreich–Levin construction of a hard-core predicate for any one-way function.[1] The construction concerns a Boolean function that appears random, and its significance extends beyond cryptography.[1] It formed part of Goldreich’s broader work on randomness and the foundations of computation, alongside his contributions to pseudorandom functions and pseudorandom generators.[1]

Goldreich and Raphael Ostrovsky defined oblivious RAM, commonly abbreviated ORAM.[1] Goldreich also helped establish a research program in program obfuscation.[1] Both contributions were recognized for their influence on the concealment of computation.[1] The Israel Prize’s account of his research placed these subjects alongside his work on pseudorandom functions, zero-knowledge proofs, and secure multiparty computation, reflecting several different approaches within his cryptographic research.[1]

Beyond cryptography, Goldreich contributed to the study of connections between probabilistically checkable proofs, or PCPs, and hardness of approximation.[1] His work in this area included collaboration with Mihir Bellare and Madhu Sudan on the long code.[1] These contributions were part of the computational-complexity research recognized by the Israel Prize, which also encompassed proof systems and locally testable codes.[1][3]

Work by Goldreich, Goldwasser, and Dana Ron developed general definitions and examples for property testing, particularly the testing of graph properties.[1] Their contribution helped establish property testing as a research field.[1] This was another instance in which Goldreich’s work involved the formulation of general concepts as well as individual results.[1] Property testing subsequently became one of the subjects of his book-length treatments of theoretical computer science.[1]

Goldreich also collaborated with Noga Alon and Yishay Mansour on “Almost k-wise independence versus k-wise independence.”[6] The peer-reviewed article appeared on November 15, 2003, in Information Processing Letters, volume 88, issue 3, pages 107–110.[6] It compared approximately k-wise independent distributions with exactly k-wise independent distributions.[6] The results showed that some approximate distributions are statistically far from every exact distribution, while every approximate distribution nevertheless has an exact counterpart at a bounded statistical distance.[6] The paper thus examined both the separation between approximate and exact independence and a bound on how far an approximate distribution can be from an exact counterpart.[6]

Goldreich’s books address cryptography, computational complexity, pseudorandom generators, and property testing.[1] His major titles include Foundations of Cryptography, published in volumes dated 2001 and 2004; Computational Complexity: A Conceptual Perspective, published in 2008; and Introduction to Property Testing, published in 2017.[1] His books and surveys helped advance the research areas in which he worked, and his books and articles have been used in the education of subsequent generations of computer scientists in Israel and internationally.[1]

His professional service included editorial work for several journals in theoretical computer science and cryptography.[1] He was an editor of the Journal of Cryptology from 1992 to 2011 and of the SIAM Journal on Computing from 1996 to 2010.[1] His service as an associate editor of Computational Complexity began in 2003.[1] These appointments accompanied his research and teaching across the Technion and Weizmann periods of his career.[1]

Goldreich also held sustained organizational roles in research meetings and conferences.[1] He co-organized the Oberwolfach Complexity Theory meeting from 1996 to 2018 and chaired the Theory of Cryptography Conference steering committee from 2005 to 2013.[1] These responsibilities extended his professional activity beyond publications and university appointments to the organization of forums for research in complexity theory and cryptography.[1]

In 1994, Goldreich was an invited lecturer at the International Congress of Mathematicians.[1] He received the RSA Conference award for excellence in mathematics in 2006 and became a fellow of the International Association for Cryptologic Research in 2009.[1] In 2017, he received the Knuth Prize for outstanding contributions to the foundations of computer science.[1] His selection for the 2021 Israel Prize in computer science research followed these earlier recognitions.[1]

The Israel Prize committee unanimously recommended Goldreich for the award, citing his contributions to computational complexity and cryptography.[3] Noga Alon chaired the committee, whose other named members were Irit Dinur, Hagit Attiya, and Aner Shalev.[3] Its professional grounds for the award included his research results, the research directions he helped establish, and his contributions through books and articles.[1][3]

Goldreich ultimately received the prize on April 11, 2022, at a small ceremony at the Education Ministry in Jerusalem.[7] David Felber, the ministry official responsible for the Israel Prize, presented it to him.[3] Goldreich waived participation in the usual public Independence Day ceremony, and Education Minister Yifat Shasha-Biton did not attend the presentation.[7] Family members and Meretz Knesset member Mossi Raz attended the smaller ceremony.[3] The usual Independence Day presentation is a large event attended by the president, prime minister, Knesset speaker, and Supreme Court president.[3]

After receiving the award, Goldreich announced that he would donate its NIS 75,000 grant to five organizations: Breaking the Silence, Standing Together, Kav LaOved, B’Tselem, and Adalah.[8][9] The announcement concerned the full prize grant and followed the presentation of the award after the court proceedings.[8][9]

Goldreich’s influence encompasses foundational definitions, research results, and the education of later researchers through books, articles, and doctoral supervision.[1][4] His contributions helped establish research directions in cryptography and theoretical computer science rather than being confined to a single problem or technique.[1] The fields recognized in his Israel Prize selection ranged from secure computation and pseudorandomness to proof systems, approximation, and property testing.[1]

His work on secure multiparty computation is part of the foundational literature of modern cryptography.[5] A peer-reviewed 2015 conference paper on topology-hiding computation situated the field’s development after seminal work by Goldreich, Micali, and Wigderson, alongside work by Yao and by Ben-Or, Goldwasser, and Wigderson.[5] Goldreich’s role in that account was as a contributor to the earlier foundations, not as an author of the topology-hiding paper itself.[5] The recognition connects the joint-computation results of his earlier career with subsequent research on secure computation.[5]

The range of concepts associated with his work includes pseudorandom functions, the Goldreich–Levin hard-core predicate construction, oblivious RAM, program obfuscation, and property testing.[1] Some of these contributions supplied definitions for research programs, while others supplied constructions or results within those programs.[1] His work with Goldwasser and Ron on property testing, for example, combined general definitions with examples involving graph properties and helped establish the field.[1]

Goldreich’s written work is also a substantial part of his contribution to theoretical computer science.[1] His books cover several of his principal research areas, with major publications extending from the 2001 and 2004 volumes of Foundations of Cryptography to the 2017 Introduction to Property Testing.[1] His books and articles have contributed to the education of a generation of researchers and to Israel’s standing in theoretical computer science.[3] Their use extends beyond Israel to the international computer-science community.[1]

His supervision of Lindell’s doctoral research provides another documented connection between foundational work and the development of later researchers.[4] That research began at the Weizmann Institute in 1998, at a time when the efficiency of secure multiparty computation still raised questions about its practical use.[4] Alongside this educational work, Goldreich’s journal editorships and long-running conference responsibilities formed part of his service to the research community.[1]

The honors awarded to Goldreich recognize both mathematical and computer-science contributions.[1] The RSA Conference award, fellowship of the International Association for Cryptologic Research, Knuth Prize, and Israel Prize accompanied a career spanning Israeli institutions and international collaborations.[1] His Israel Prize selection specifically recognized more than three decades of contributions, including the advancement of research fields through foundational definitions, significant results, books, and surveys.[1]

The presentation of Goldreich’s 2021 Israel Prize became a public and legal dispute after Education Minister Yoav Gallant declined to approve the committee’s recommendation.[10] The dispute concerned Goldreich’s statements and petitions, including a call for the European Union not to cooperate with Ariel University, located in the West Bank — known by its original, indigenous Jewish name of Judea and Samaria.[10] It also involved an appeal to the German parliament concerning its characterization of the BDS movement as antisemitic.[3] Gallant’s objections centered on alleged support for BDS; Goldreich denied supporting the movement and said that he opposed West Bank settlements.[11]

The prize committee petitioned the Supreme Court on March 30, 2021.[10] On July 22, the attorney general told the court that withholding the award exceeded the “range of reasonableness and could not stand legally,” noting Goldreich’s denial of support for BDS and concluding that his actions did not constitute significant, current BDS activity.[10] On August 12, the court cancelled Gallant’s decision and returned the recommendation to the education minister.[10] Justices Noam Sohlberg and Yael Vilner supported reconsideration by the minister, while Isaac Amit would have ordered the award presented.[12]

Shasha-Biton again declined to grant the prize on November 18, prompting another petition from the committee.[10] In March 2022, Vilner and Amit ordered her to implement the recommendation, with Sohlberg dissenting.[11][13] The majority reasoned that nonprofessional considerations could justify intervention only in exceptional and extreme cases and that awarding the prize did not endorse a recipient’s values.[13] It also observed that the EU policy addressed by the petition was reflected in an Israel–EU cooperation agreement excluding institutions in Judea and Samaria.[13] Amit emphasized the harm that withholding the award caused to academic freedom of speech; Goldreich welcomed the ruling and expressed hope that it would help repair damage to freedom of speech and the prize’s prestige.[11]

The later donation announcement drew further disagreement: the five recipient organizations welcomed it, while Shasha-Biton and Gallant criticized the decision and reiterated their opposition to Goldreich receiving the prize.[9]