Avi Wigderson
Plus d'infos
- Affiliation
- Institute for Advanced Study, Princeton
- Connu pour
- Preuves à divulgation nulle pour NP, protocole GMW, dérandomisation
Théoricien israélien de la complexité qui a montré que tout énoncé NP peut être prouvé sans rien révéler d'autre, et lauréat du prix Turing 2023.
En 1986, Wigderson, avec Oded Goldreich et Silvio Micali, démontre qu'il existe des preuves à divulgation nulle de connaissance pour tout problème de NP, et pas seulement pour quelques cas choisis avec soin. L'année suivante vient le protocole GMW : une méthode générale pour que plusieurs parties calculent ensemble une fonction sans se montrer leurs entrées. Avec Ben-Or et Shafi Goldwasser, il en donne en 1988 une version à sécurité inconditionnelle.
L'essentiel de son œuvre porte pourtant sur le rôle de l'aléa dans le calcul : quand il est nécessaire, et quand on peut le remplacer par des constructions déterministes. Ce travail lui a valu le prix Abel 2021, partagé avec László Lovász, et le prix Turing, dont l'attendu cite la cryptographie parmi plusieurs applications.