Avi Wigderson
Meer info
- Instelling
- Institute for Advanced Study, Princeton
- Bekend van
- Zero-knowledge-bewijzen voor NP, het GMW-protocol, derandomisatie
Israëlische complexiteitstheoreticus die aantoonde dat elke NP-bewering te bewijzen is zonder iets anders prijs te geven, en in 2023 de Turingprijs ontving.
In 1986 toonde Wigderson samen met Oded Goldreich en Silvio Micali aan dat zero-knowledge-bewijzen bestaan voor elk probleem in NP, niet alleen voor een paar handgekozen gevallen. Een jaar later volgde het GMW-protocol: een algemene manier waarop meerdere partijen samen een functie berekenen zonder elkaar hun invoer te tonen. Met Ben-Or en Shafi Goldwasser gaf hij in 1988 een informatietheoretische variant.
Het grootste deel van zijn werk gaat echter over de rol van willekeur in berekeningen: wanneer die nodig is en wanneer deterministische constructies volstaan. Die lijn leverde hem in 2021 de Abelprijs op, gedeeld met László Lovász, en de Turingprijs, waarvan de motivering cryptografie noemt als een van meerdere toepassingen.