Imaginez que vous ayez des connaissances utiles - peut-être une recette secrète ou la clé d'un chiffrement. Pourriez-vous prouver à un ami que vous aviez cette connaissance, sans rien révéler à ce sujet ? Les informaticiens ont prouvé il y a plus de 30 ans que c'était possible, si vous utilisiez ce qu'on appelle une preuve de connaissance nulle.
Pour comprendre simplement cette idée, supposons que vous vouliez montrer à votre ami que vous savez comment traverser un labyrinthe, sans divulguer aucun détail sur le chemin. Vous pouviez simplement traverser le labyrinthe dans un délai limité, alors que votre ami n'avait pas le droit de regarder. (La limite de temps est nécessaire parce qu'avec suffisamment de temps, n'importe qui peut éventuellement s'en sortir par essais et erreurs.) Votre ami saurait que vous pouvez le faire, mais il ne saurait pas comment.
Les preuves à connaissance nulle sont utiles aux cryptographes, qui travaillent avec des informations secrètes, mais aussi aux chercheurs en complexité computationnelle, qui traitent de la classification de la difficulté de différents problèmes. "Une grande partie de la cryptographie moderne repose sur des hypothèses de complexité - sur l'hypothèse que certains problèmes sont difficiles à résoudre, il y a donc toujours eu des liens entre les deux mondes", a déclaré Claude Crépeau, informaticien à l'Université McGill. "Mais [ces] preuves ont créé tout un monde de connexion."
Les preuves à connaissance nulle appartiennent à une catégorie connue sous le nom de preuves interactives, donc pour savoir comment fonctionnent les premières, il est utile de comprendre les secondes. Première décrit dans un article de 1985 par les informaticiens Goldwasser Shafi, Silvio Micali et Charles Rackoff, les preuves interactives fonctionnent comme une interrogation : au cours d'une série de messages, une partie (le prouveur) essaie de convaincre l'autre (le vérificateur) qu'un énoncé donné est vrai. Une preuve interactive doit satisfaire deux propriétés. Premièrement, une affirmation véridique finira toujours par convaincre un vérificateur honnête. Deuxièmement, si l'énoncé donné est faux, aucun démonstrateur - même un prétendant posséder certaines connaissances - ne peut convaincre le vérificateur, sauf avec une probabilité négligeable.
Les preuves interactives sont de nature probabiliste. Le prouveur pourrait répondre correctement à une ou deux questions simplement par chance, il faut donc un nombre suffisant de défis, que le prouveur doit tous relever, pour que le vérificateur devienne confiant que le prouveur sait en fait que l'énoncé est vrai.
Cette idée d'interactions est venue lorsque Micali et Goldwasser – alors étudiants diplômés de l'Université de Californie à Berkeley – se sont interrogés sur la logistique du jeu de poker sur un réseau. Comment tous les joueurs peuvent-ils vérifier que lorsque l'un d'eux obtient une carte du jeu virtuel, le résultat est aléatoire ? Les preuves interactives pourraient ouvrir la voie. Mais alors, comment les joueurs peuvent-ils vérifier que l'ensemble du protocole - l'ensemble complet des règles - a été suivi correctement, sans révéler la main de chaque joueur en cours de route ?
Pour atteindre cet objectif, Micali et Goldwasser ont ajouté une troisième propriété aux deux nécessaires pour une preuve interactive : la preuve ne doit rien révéler sur la connaissance elle-même, seulement la véracité de l'énoncé. "Il y a une notion de passer par un protocole, à la fin duquel vous pensez que [les joueurs de poker] ne savent rien de plus que ce qu'ils sont censés savoir", a déclaré Goldwasser.
Prenons l'exemple classique. Alice veut prouver à Bob qu'un certain graphique G - une collection unique de sommets (points) reliés par des arêtes (lignes) - a un "cycle hamiltonien". Cela signifie que le graphique a un chemin qui visite chaque point exactement une fois et se termine au même point de départ. Alice pourrait le faire en montrant simplement à Bob le chemin qui fait cela, mais bien sûr, il connaîtrait aussi le chemin.
Voici comment Alice peut convaincre Bob qu'elle sait qu'un tel chemin existe, sans le lui montrer. Elle dessine d'abord un nouveau graphique, H, ça ne ressemble pas G mais est similaire d'une manière cruciale : il a le même nombre de sommets, connectés de la même manière. (Si G a vraiment un cycle hamiltonien, cette similitude signifie H sera aussi.) Puis, après avoir couvert chaque bord de H avec du masking tape, elle verrouille H dans une boîte et donne la boîte à Bob. Cela l'empêche de le voir directement mais l'empêche aussi de le modifier. Bob fait alors un choix : Soit il peut demander à Alice de montrer que H ressemble vraiment à G, ou il peut lui demander de lui montrer le cycle hamiltonien en H. Les deux demandes devraient être faciles pour Alice, en supposant que H est vraiment assez similaire à G, et qu'elle connaît vraiment le chemin.
Bien sûr, même si Alice ne connaît pas le cycle hamiltonien en G, elle peut essayer de tromper Bob, soit en dessinant des graphiques qui ne ressemblent pas à G, ou en soumettant des graphiques dont elle ne connaît pas le chemin. Mais après avoir joué plusieurs tours, la chance qu'Alice trompe Bob à chaque fois devient infime. Si elle obtient tout droit, finalement Bob sera convaincu qu'Alice connaît un cycle hamiltonien dans le graphique G, sans que Bob ne l'ait jamais vu.
Après l'article initial qui a décrit pour la première fois de telles preuves, Micali et deux mathématiciens - Oded Goldreich et Avi Wigderson - ont découvert une conséquence inattendue avec des effets considérables. Il s'agit d'une grande catégorie de problèmes de difficulté à peu près égale, connue sous le nom de NP. Ces problèmes sont difficiles à résoudre, mais leurs solutions sont faciles à vérifier. Les trois chercheurs constaté que, si cryptage vraiment sécurisé est possible, alors la solution de chaque problème de NP peut également être prouvée avec une preuve à connaissance nulle. Cette étude a aidé les chercheurs concevoir des variantes de preuves à connaissance nulle qui ne nécessitent même pas de cryptage sécurisé en premier lieu ; celles-ci sont connues sous le nom de preuves interactives multi-prouveurs.
Et en 1988, Micali et d'autres montré que si un prouveur et un vérificateur partagent une courte chaîne de bits aléatoires, aucune interaction n'est nécessaire. Cela signifiait théoriquement que les preuves à connaissance nulle n'avaient pas besoin d'être interactives, ce qui impliquerait qu'une communication constante entre deux parties n'est pas nécessaire. Cela les rendrait beaucoup plus utiles aux chercheurs, mais ce n'est qu'après le tournant du 21e siècle que de telles preuves ont décollé.
"À la fin des années 2000, nous avons commencé à voir l'évolution de techniques efficaces pour construire des preuves sans connaissance", a déclaré Matthieu D. Green, cryptographe à l'université John Hopkins. "Nous sommes arrivés au point où nous avons réalisé, 'Attendez une seconde, il pourrait en fait y avoir un moyen d'utiliser cela dans la pratique.'"
Désormais, un prouveur pourrait envoyer un seul message à un vérificateur sans que les deux aient à être en ligne, et les chercheurs pourraient créer une preuve très courte qui pourrait être rapidement vérifiée, même pour des problèmes très compliqués. Cela a conduit à plusieurs utilisations pratiques, telles que la possibilité de vérifier rapidement la blockchain après une transaction de crypto-monnaie tout en masquant les détails de la transaction. Et en 2016, un groupe de physiciens montré comment les preuves à connaissance nulle peuvent aider au désarmement nucléaire : Sans révéler le moindre secret sur la conception de son ogive nucléaire, un pays pourrait désormais prouver aux inspecteurs nucléaires si l'ogive est active ou inactive.
Plus récemment, les progrès de l'informatique quantique ont obligé Crépeau à tester les recherches antérieures pour s'assurer que les protocoles à connaissance zéro sont toujours viables. En 2021, il a aidé démontrer que les preuves interactives multi-prouveurs conservent leur secret même lorsque des ordinateurs quantiques sont impliqués, mais atteindre le même niveau de sécurité rend le protocole beaucoup plus lent. La découverte était une bonne nouvelle, a-t-il dit, mais de nouvelles préoccupations surgiront à mesure que la technologie progressera.
"Chaque type de calcul que nous pourrions faire à l'avenir impliquera des ordinateurs quantiques", a déclaré Crépeau. "Ainsi, en tant que bons cryptographes paranoïaques, chaque fois que nous évaluons la sécurité d'un système, nous voulons nous assurer que notre système est sûr."
NDLR : Shafi Goldwasser a reçu un financement de la Fondation Simons, qui finance également ce publication indépendante de la rédaction. Les décisions de financement de la Fondation Simons n'ont aucune influence sur notre couverture.
