Avi Wigderson
More info
- Affiliation
- Institute for Advanced Study, Princeton
- Known for
- Zero-knowledge proofs for NP, the GMW protocol, derandomisation
Israeli complexity theorist who showed that any NP statement can be proven without revealing anything else, and received the 2023 Turing Award.
In 1986 Wigderson, together with Oded Goldreich and Silvio Micali, showed that zero-knowledge proofs exist for every problem in NP, not just a few hand-picked ones. The next year brought the GMW protocol: a general way for several parties to jointly compute a function without showing each other their inputs. With Ben-Or and Shafi Goldwasser he gave an information-theoretic version in 1988.
Most of his work, though, is about the role of randomness in computation — when it is needed and when it can be replaced by deterministic constructions. That line earned him the 2021 Abel Prize, shared with László Lovász, and the Turing Award, whose citation listed cryptography as one of several applications.