MIT · Department of Mathematics

The Goldwasser
Group at MIT

We study what can be proven, what can be hidden, and what can be verified — and increasingly, how to apply all three to ensure robust and trustworthy machine learning systems.

Prover self-proving model LLM Verifier ALG question answer + proof query response accept / reject answer
  • p = 2²⁵⁵ − 19 Primality verification
  • √x mod p Modular square root
  • Universal prover
A self-proving model is trained to do two things at once: compute an answer, and prove that answer correct through a short interaction with a verification algorithm that never has to trust it. Machine learning ordinarily measures accuracy on average over a distribution; a proof holds for the input in front of you.

01 — What we work on

Research interests

Foundations of cryptography, complexity theory, proof systems, probabilistic algorithms, and trustworthy ML.

Current directions

Cryptographic thinking, applied to machine learning

For half a century the mission of modern cryptography has been to model, define and achieve private communication and computation, authentication, and correctness in interactions between parties who do not trust one another. The premise organizing our group's current work is that much of that thinking transfers to machine learning — and that where it fails to transfer, we need to know.

Trust in a deployed model presently rests on empirical evidence: benchmarks, evaluations, and the reputation of whoever trained it. We want something stronger. Can a learner prove it trained on the data and with the algorithm it claims? Can a model prove, for a particular query rather than on average, that this answer is correct? Can privacy survive training and inference, at the scale models are now built? And when a backdoor can provably not be detected, can its effects still be removed?

The same problem appears well outside computing. Courts face verification dilemmas, where proving a fact requires disclosing far more than the fact. Regulations are written in legal language that cannot be matched against any cryptographic technique until someone states them mathematically. And the experimental sciences have spent a decade pursuing replication when what they may need is verification — which is not the same thing.

Foundations

Cryptography, complexity, and proof

The classical core that everything below is built on: semantic security and probabilistic encryption, pseudorandom functions, digital signatures, information-theoretically secure multi-party computation, interactive and zero-knowledge proofs, multi-prover systems and the route they opened to the PCP theorem and hardness of approximation, combinatorial property testing, delegation of computation, leakage resilience, and pseudo-deterministic algorithms. Each of these opened a field that we still work on — see bodies of work.

Privacy

Privacy across the ML pipeline

Homomorphic encryption, secure multi-party computation, and federated learning applied to training as well as inference. Classification over encrypted data is by now well developed; training at scale is the open problem. Recent work has carried genome-wide association studies and collaborative oncological analysis to real scale. Next: closing the type gap, by building secure computation that works on floating-point numbers directly instead of approximating them over finite fields.

Verification

Verifying that learning was done right

Delegation of computation is a mature field, but its techniques do not carry over to ML, which is randomized, massively parallel, defined against distributions rather than a known ground truth, native to the reals, and trained on data the trainer selected. PAC verification asks whether a hypothesis from an untrusted learner is approximately correct, using far less data than training required. Self-proving models go further: a model trained to produce, alongside each answer, an interactive proof that the answer is right — a per-input guarantee where ML normally offers only an average-case one.

Robustness

Backdoors, mitigation, and abstention

A malicious learner can plant a backdoor no inspection will find, short of breaking cryptography. Detection being impossible, the question becomes mitigation: using the compromised predictor as a labeling resource to retrain a clean one, on far less data than training from scratch. Alongside this, classifiers permitted to abstain, achieving low error on arbitrarily chosen test distributions — and extending abstention to language models facing harmful prompts, which first requires saying formally what makes a prompt harmful.

Law and policy

The verification dilemma

Proving a fact about your identity, knowledge, or conduct usually means disclosing much more than the fact. The alternative — declining to disclose — excludes people from opportunities and defeats public oversight. Zero-knowledge proofs offer a third option, and we have built working prototypes: accountable electronic surveillance at the scale of the federal judiciary, and hidden investigative software able to answer a defense expert's challenge without being revealed. Ahead: giving regulations such as the GDPR, and the AI rules now arriving, mathematical statements that technology can be held to.

Quantum

Quantum answers to classical impossibilities

Cryptographic tasks proven impossible classically may become possible when the algorithm itself is quantum. Deniable encryption is the clearest case: a quantum procedure can erase the randomness it used, making coercion impossible even before encryption takes place. Also under way — one-time programs without the self-destructing-hardware assumption, and leakage resilience re-proven against quantum adversaries.

Translation

Unsupervised translation and animal communication

What would it take to translate a language with no parallel corpus, no bilingual speakers, and little shared world — sperm whale codas, for instance? A theory of unsupervised translation, developed with the Cetacean Translation Initiative, gives conditions under which the problem is solvable at all and bounds on the data any solution would need.

02 — Selected work

Bodies of work

Grouped by the line of research each opened rather than listed by date. A complete bibliography is on DBLP.

  • 1982 – 1986

    Cryptographic foundations

    Probabilistic encryption and the definition of semantic security; digital signatures secure against adaptive chosen-message attack; and pseudorandom functions indistinguishable from truly random ones, built from any one-way function. These are the definitions the field still uses.

    Goldwasser–Micali, JCSS 1984 · Goldwasser–Micali–Rivest, SICOMP 1988 · Goldreich–Goldwasser–Micali, JACM 1986

  • 1985 – 1988

    Probabilistic and interactive proof systems

    Zero-knowledge interactive proofs, now the mechanism behind verified smart contracts, and multi-prover interactive proofs, later shown equivalent to probabilistically checkable proofs and central to the quantum result MIP* = RE. Gödel Prize, 1993.

    Goldwasser–Micali–Rackoff, SICOMP 1989 · Ben-Or–Goldwasser–Kilian–Wigderson, STOC 1988

  • 1988

    Information-theoretically secure multi-party computation

    Unconditionally secure protocols for general multi-party computation, assuming only secure channels between pairs of users. Because their efficiency does not degrade with the difficulty of a hardness assumption, these remain the backbone of MPC as it is actually deployed.

    Ben-Or–Goldwasser–Wigderson, STOC 1988

  • 1986

    Primality proving

    Elliptic curves used to construct the most succinct NP proofs of primality known, and, at the time, the first primality proof finder running in expected polynomial time.

    Goldwasser–Kilian, JACM 1999

  • 1992 – 1998

    Hardness of approximation

    Connected the complexity of multi-prover proofs to the intractability of approximating NP-hard problems, opening the decade of work that produced the PCP theorem — and, in the other direction, limited the approximate hardness of the shortest and closest vector problems on lattices by placing them in AM ∩ coAM.

    Feige–Goldwasser–Lovász–Safra–Szegedy, JACM 1996 · Goldreich–Goldwasser, JCSS 2000

  • 1998 – 2000

    Combinatorial property testing

    Founded graph and combinatorial property testing — deciding global properties of enormous objects from a handful of queries. Now a field with its own conferences and workshops. Gödel Prize, 2001.

    Goldreich–Goldwasser–Ron, JACM 1998 · Goldreich–Goldwasser–Lehman–Ron–Samorodnitsky, Combinatorica 2000

  • 2008

    Delegating computation

    Doubly efficient delegation for NC computations, in which the honest prover costs roughly what the computation itself costs. Since reduced to practice in several implementations.

    Goldwasser–Kalai–Rothblum, JACM 2015 (STOC 2008)

  • 2009 – 2012

    Leakage resilience

    Launched the theoretical study of encryption, authentication, and secure computation that stay secure when private keys partially leak, so long as some entropy remains hidden.

    Akavia–Goldwasser–Vaikuntanathan, TCC 2009 · Boyle–Goldwasser–Jain–Kalai, STOC 2012 · Goldwasser–Rothblum, SICOMP 2015

  • 2011 – 2021

    Pseudo-determinism

    Probabilistic algorithms for search problems that return the same solution on the same input whatever randomness they draw — achieved for perfect matching in NC, and extended to streaming and to interactive proofs in which a prover helps a verifier find a provably canonical solution. Because outputs are almost independent of the randomness, that randomness can be recycled. A question posed in this line was recently settled by a pseudo-deterministic construction of large primes.

    Gat–Goldwasser 2011 · Goldwasser–Grossman, ICALP 2017 · Goldwasser–Grossman–Holden, ITCS 2018 · Goldwasser–Grossman–Mohanty–Woodruff, ITCS 2020 · Goldwasser–Impagliazzo–Pitassi–Santhanam, CCC 2021

Recent

Since 2015

Where the cryptographic questions above meet machine learning, law, and medicine.

  1. 2026

    Sum-Check Protocol for Approximate Computations

    with Dor Bitan, Zachary DeStefano, Yuval Ishai, Yael Tauman Kalai and Justin Thaler · Eurocrypt — Carrying verification over to computation on real numbers rather than finite fields.

  2. 2026

    Private Proofs of When and Where

    with Uma Girish, Greg Gluch, Tal Malkin, Leo Orshansky and Henry Yuen · CRYPTO

  3. 2026

    The Computational Intractability of Filtering for AI Alignment

    with Sarah Ball, Greg Gluch, Frauke Kreuter, Omer Reingold and Guy Rothblum · ICLR — Why safety filters built outside the model cannot work.

  4. 2026

    Learning Randomized Reductions and Program Properties

    with Ferhat Erata, Orr Paradise, Timos Antonopoulos, ThanhVu Nguyen and Ruzica Piskac · ICML — Spotlight

  5. 2026

    Efficient Public Verification of Private ML via Regularization

    with Zoë Ruha Bell, Anvith Thudi, Olive Franzese-McLaughlin and Nicolas Papernot · ICML

  6. 2026

    Proofs of Ownership for Machine Learning Models

    with Ran Canetti and Or Zamir · Preprint

  7. 2026

    Investigating the Development of Task-Oriented Communication in Vision-Language Models

    with Boaz Carmeli, Orr Paradise, Yonatan Belinkov and Ron Meir · Preprint

  8. 2025

    A Theory for Worst-Case vs. Average-Case Guarantees for LLMs

    with Noga Amit, Orr Paradise and Guy Rothblum · NeurIPS — Self-proving models: training a model to accompany each answer with an interactive proof of its correctness, so the guarantee holds for the input in front of you rather than on average.

  9. 2025

    Oblivious Defense in ML Models: Backdoor Removal Without Detection

    with Jonathan Shafer, Neekon Vafa and Vinod Vaikuntanathan · STOC — The counterpart to the undetectability result: backdoors whose effects can be removed even though they cannot be found.

  10. 2025

    Unsupervised Translation of Emergent Communication

    with Ido Levy, Orr Paradise, Boaz Carmeli, Ron Meir and Yonatan Belinkov · AAAI — Translating a code that a population of agents invented for itself.

  11. 2025

    A Cryptographic Perspective on Mitigation vs. Detection in Machine Learning

    with Greg Gluch · Preprint — Detecting an adversarial input and repairing it are equivalent for classification, and provably are not for generation.

  12. 2024

    Certifying Private Probabilistic Mechanisms

    with Zoë Ruha Bell, Michael P. Kim and Jean-Luc Watson · CRYPTO — Proving that a mechanism really did add the randomness it claims.

  13. 2023

    Collaborative Privacy-Preserving Analysis of Oncological Data Using Multiparty Encryption

    with R. Geva and colleagues · PNAS — Encrypted analysis at clinical scale.

  14. 2022

    Planting Undetectable Backdoors in Machine Learning Models

    with Michael P. Kim, Vinod Vaikuntanathan and Or Zamir · FOCS — A backdoor that cannot be found without breaking cryptography, even given full access to the predictor.

  15. 2022

    Deniable Encryption in a Quantum World

    with Andrea Coladangelo and Umesh Vazirani · STOC — Quantum encryption makes coercion impossible even before the message is sent.

  16. 2022

    Verification Dilemmas in Law and the Promise of Zero-Knowledge Proofs

    with Kenneth Bamberger, Ran Canetti, Rebecca Wexler and Evan Zimmerman · Berkeley Technology Law Journal

  17. 2022

    Using Zero-Knowledge to Reconcile Law Enforcement Secrecy and Fair Trial Rights

    with Dor Bitan, Ran Canetti and Rebecca Wexler · CSLAW — A working prototype, built on real cases.

  18. 2021

    Interactive Proofs for Verifying Machine Learning

    with Guy Rothblum, Jonathan Shafer and Amir Yehudayoff · ITCS — PAC verification: checking an untrusted learner’s hypothesis with far less data than training took.

  19. 2021

    Universal Adaptability: Target-Independent Inference That Competes with Propensity Scoring

    with Michael P. Kim, Christoph Kern, Frauke Kreuter and Omer Reingold · PNAS — Statistical inference without random samples of the target population, via multi-calibration.

  20. 2020

    Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples

    with Omar Montasser, Adam Kalai and Yael Tauman Kalai · NeurIPS — Classifiers that may abstain, with no restriction on the test distribution.

  21. 2020

    Formalizing Data Deletion in the Context of the Right to Be Forgotten

    with Sanjam Garg and Prashant Nalini Vasudevan · Eurocrypt — A mathematical statement of a GDPR provision, and ways to satisfy it.

  22. 2020

    Secure Large-Scale Genome-Wide Association Studies Using Homomorphic Encryption

    with Marcelo Blatt, Alexander Gusev and Yuriy Polyakov · PNAS

  23. 2018

    Practical Accountability of Secret Processes

    with Jonathan Frankle, Sunoo Park, Daniel Shaar and Daniel Weitzner · USENIX Security — Accountable electronic surveillance at the scale of the federal court system.

  24. 2015

    Machine Learning Classification over Encrypted Data

    with Raphael Bost, Raluca Ada Popa and Stephen Tu · NDSS — The first treatment of ML classification on encrypted inputs.

Project CETI

Listening to sperm whales

Shafi Goldwasser leads the theoretical analysis group of the Cetacean Translation Initiative, a nonprofit founded in 2020 that applies machine learning, robotics, and underwater acoustics to record and interpret the communication of sperm whales, working from a field site in Dominica.

The theoretical question is what makes translation possible at all when there is no parallel corpus, no bilingual speaker, and very little shared world between the two parties — which conditions must hold for the problem to be solvable, and how much data any method would need. The answers depend on what the recordings actually contain, so the theoretical work runs alongside the acoustic and behavioural analysis coming off the water in Dominica.

03 — Who we are

People

Principal investigator

Shafi Goldwasser

Leighton Family Professor of Mathematics

Shafi Goldwasser is the Leighton Family Professor of Mathematics at MIT. She served as Director of the Simons Institute for the Theory of Computing at Berkeley, where she now co-directs the Research Pod on Resilience in Brain, Natural, and Algorithmic Systems. She is a co-founder and chief scientist of Duality Technologies.

She holds a BS in applied mathematics from Carnegie Mellon (1979) and an MS and PhD in computer science from UC Berkeley (1984). She received the ACM A.M. Turing Award in 2012.

Postdoctoral researchers and instructors

Postdoctoral researcher · PhD, Columbia University

Miranda Christ

Cryptography for AI-generated content. Her work on undetectable watermarks for language models, and on the pseudorandom error-correcting codes underlying them, established that provenance marking need not cost output quality.

UC Berkeley (Simons Institute), hosted at MIT · PhD, EPFL

Greg Gluch

AI safety and resilience from a cryptographic angle, together with adversarial robustness, generalization, and quantum complexity theory and its links to physics. A member of the Resilience Research Pod at the Simons Institute.

C.L.E. Moore Instructor from Fall 2026 · PhD, UC Berkeley

Sam Gunn

Quantum cryptography and its classical consequences: commitments to quantum states, one-time protection of randomized algorithms, certified randomness, and pseudorandom codes. Most recently, data deletion — predicting how a trained model would have behaved had some of its training data been withheld. Mentored in the department by Shafi Goldwasser.

UC Berkeley (Simons Institute), hosted at MIT · PhD, Weizmann Institute

Tal Herman

Interactive proofs for data science and distribution testing — verifying statistical claims about an unknown distribution using far fewer samples than computing them would take.

Doctoral students

PhD student, MIT · co-advised with Guy Rothblum

Noga Amit

Self-proving models — training a language model to accompany each answer with an interactive proof of its correctness, and establishing when a per-input guarantee is achievable at all. Previously at UC Berkeley.

PhD student, UC Berkeley · co-advised with Avishay Tal

Zoë Ruha Bell

Cryptographic guarantees for privacy mechanisms: proving that a mechanism really did add the randomness it claims, and making privately trained models publicly verifiable without exposing what they were trained on.

PhD student, UC Berkeley · co-advised with John Wright

Angelos Pelecanos

Quantum learning and complexity: how much of a quantum state can be recovered from a limited number of copies. Recent results establish that a state's spectrum can be estimated well below the cost of full tomography, that mixed-state tomography reduces to the pure-state case, and give an unbiased estimator for full tomography. Alongside this, cryptography — approximate k-wise independent permutations built from random reversible circuits.

04 — Teaching

Courses and reading groups

Cryptography and machine learning have started asking each other's questions. Both of these are attempts to teach that intersection while it is still forming.

  • Spring 2026

    Cryptography and Machine Learning: Foundations and Frontiers

    6.S976 / 18.S996 · with Vinod Vaikuntanathan

    Cryptography is a playbook for building trust on platforms nobody trusts. The course applies that playbook to machine learning: privacy-preserving algorithms, interactive proofs, and debate protocols used to give ML systems privacy, verifiability, and reliability. It covers data and model privacy, methods for verifying average-case quality and certifying worst-case correctness, and strategies for robustness and alignment in both discriminative and generative models — with the aim of marking out the contours of a field that does not quite exist yet, and naming concrete problems in it.

    Modules and guest lecturers

    • The six modules

      • 1 · Foundations — ML basics and access models; crypto basics, pseudorandomness, and learning impossibility from cryptographic hardness
      • 2 · Watermarking — undetectable watermarks for language and image models, pseudorandom codes, robustness, open problems
      • 3 · Verification — interactive proofs and zero knowledge, PAC verification, self-proving models, and Lean as a different route to the same goal
      • 4 · Robustness and alignment — robust statistics, backdoors and their removal, alignment
      • 5 · Privacy and security — model stealing, subliminal learning, homomorphic encryption, private information retrieval, encrypted linear algebra
      • 6 · Project presentations

    • Guest lecturers

      • Jonathan Shafer · Adam Kalai · Orr Paradise · Cameron Freer · Sam Hopkins · Neekon Vafa · Greg Gluch · Abhishek Shetty · Alexandra Henzinger

    Course site — slides, scribe notes, problem sets, and a full reading list for every lecture.

  • Tuesdays

    ML + Cryptography Seminar

    Organizer · with Yael Kalai, Jonathan Shafer, Neekon Vafa and Vinod Vaikuntanathan

    A reading group and seminar where the two fields are put in the same room each week. Stata Center, Room 32G-575, Tuesdays 1:30–3:30. Open to anyone at MIT and beyond — join the mailing list for announcements, or write to Jonathan Shafer or Neekon Vafa.

    Talks, 2025–26
    • Spring 2026
      • Odelia Melamed (Weizmann) — A theoretical point of view on machine unlearning and privacy
      • Sam Gunn (UC Berkeley) — How to sketch a learning algorithm
      • Yael Tauman Kalai (MIT) — Consensus sampling for safer generative AI
      • Abhishek Shetty (MIT) — Subliminal transfer in training data and low logit rank
      • Ayush Sekhari (Chan Zuckerberg Initiative) — The space complexity of machine unlearning
      • Connor Wagaman (BU) — Refereed learning
    • Fall 2025
      • Noah Golowich (Microsoft Research) — Sequences of logits and the low-rank structure of language models
      • Adam Tauman Kalai (OpenAI) — Why language models hallucinate
      • Neekon Vafa (MIT) — Statistically undetectable backdoors in deep neural networks
      • Greg Gluch (Simons Institute) — What can cryptography tell us about AI?
      • Ankur Moitra (MIT) — Model stealing: recent results and open problems
      • Tal Herman (MIT) — Proofs for distribution properties
      • Miranda Christ (Columbia) — A survey of cryptographic watermarks for AI-generated content

    Seminar site — abstracts, slides, and the current schedule.

05 — Activities

Convening and leadership

Programs and meetings built to put cryptographers and complexity theorists in a room with the people who have the problems — neuroscientists, lawyers, linguists, and biologists.

  • Ongoing

    Research Pod on Resilience in Brain, Natural, and Algorithmic Systems

    Co-director · Simons Institute for the Theory of Computing, UC Berkeley

    A three-year interdisciplinary pod on resilience — what it is, where it fails, and how to build it in deliberately. The question runs across biological and natural systems, economies, engineered infrastructure like the cloud and the internet, and fault-tolerant algorithms. A particular focus is sustained dialogue between computer scientists and neuroscientists about the mechanisms underlying resilience in the brain.

    Directed with Venkatesan Guruswami and Daniela Kaufer. Pod page.

  • 4–5 May 2026

    Invented, constructed, and emergent languages in multi-agent AI systems

    Organizer · MIT Mathematics and the Kempner Institute, Harvard

    A two-day workshop on how new languages come into being — across humans, animals, and populations of AI agents. As agents begin developing communication systems of their own, the workshop asked what those languages look like, whether people can understand them, and what they reveal about meaning, efficiency, and expression.

    Day one at MIT, Building 2, Room 2-290; day two at the Kempner Institute, Room 6.242.

  • 24 Oct 2025

    AI and Law

    Organizer · Berkman Klein Center, Harvard

    A one-day meeting on two questions held deliberately apart: how AI is already being used inside legal systems, and what legal and regulatory tools exist to govern AI. Twenty-one speakers from law, computer science, and economics, closing with a panel on which problems are the pressing ones.

    Full program
    • 09:05

      AI use in law and legal systems, part 1

      Moderator: Shafi Goldwasser

      • Emaan Hariri — AI as used by law students
      • Scott Shapiro — Using SMT solvers for rule-based legal reasoning
      • Jens Ludwig — Predicting police misconduct
      • Paul Ohm — The plummeting costs of regulatory compliance
    • 10:30

      AI use in law and legal systems, part 2

      Moderator: Martha Minow

      • Alan Rozenshtein — The unitary artificial executive
      • Shira Gur-Arieh — Ambiguity collapse in LLMs and its implications for legal interpretation
      • Cullen O’Keefe — Law-following AI
      • Ernest Lim — Comparative judicial deployment of AI
    • 12:00 · over lunch

      Law is code: a software engineering approach to analyzing the United States Code

      Andrew Lo · Moderator: Cass Sunstein

    • 13:10

      Legal tools and regulation to affect AI, part 1

      Moderator: Cynthia Dwork

      • Jon Kleinberg — Foundation models, incentives, and backfiring effects
      • Daniel Weitzner — New wine in old bottles: what legal and technical privacy tools do we have to address AI privacy?
      • Colleen Chien — Bridging gaps between academic research and legal investigations of algorithmic discrimination
      • Sandra Wachter — Do large language models have a legal duty to tell the truth?
    • 14:35

      Legal tools and policy to affect AI, part 2

      Moderator: Paul Ohm

      • Sonia Katyal — Trade secrets and AI
      • Reuven Avi-Yonah — Taxation of autonomous AI
      • A. Feder Cooper — Extracting memorized copyrighted books from open-weight language models, and what follows for copyright law and policy
      • Pamela Samuelson — Collective licensing for AI and intellectual property
    • 16:00

      Panel: which legal and policy problems emerging from AI are the pressing ones?

      Moderator: Martha Minow

      • Sarah Schwettmann (Transluce) · Aileen Nielsen (Harvard) · Yonadav Shavit (OpenAI) · Maroussia Levesque (Harvard) · Jon Kleinberg (Cornell) · Beatriz Botero Arcila (Harvard) · Talia Gillis (Columbia)

06 — Recognition

Awards and honors

  • 2023

    Edsger W. Dijkstra Prize in Distributed Computing for “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation” (1988), with Ben-Or and Wigderson

  • 2021

    L'Oréal-UNESCO For Women in Science Award

  • 2021

    FOCS Test of Time Award 30-year award, for “Approximating Clique is Almost NP-Complete” (1991), with Feige, Lovász, Safra and Szegedy

  • 2021

    STOC Test of Time Award 30-year award, for “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation” (1988), with Ben-Or and Wigderson

  • 2018

    BBVA Foundation Frontiers of Knowledge Award

  • 2012

    ACM A.M. Turing Award with Silvio Micali, for transforming cryptography into a rigorous science

  • 2012

    Simons Foundation Investigator Award

  • 2011

    IEEE Emanuel R. Piore Award

  • 2010

    Benjamin Franklin Medal in Computer and Cognitive Science

  • 2008

    ACM Athena Lecturer Award

  • 2001

    Gödel Prize for property testing and its connection to learning and approximation

  • 1998

    RSA Award in Mathematics

  • 1996

    ACM Grace Murray Hopper Award

  • 1993

    Gödel Prize for the knowledge complexity of interactive proof systems

Elected memberships

National Academy of Sciences · National Academy of Engineering · American Academy of Arts and Sciences · Royal Society, Foreign Member · Israel Academy of Sciences and Humanities · Russian Academy of Sciences · London Mathematical Society

Honorary degrees

Oxford · Waterloo · Barnard · Carnegie Mellon · Hebrew University of Jerusalem · Tel Aviv University · University of Haifa · Ben-Gurion University of the Negev · Bar-Ilan University