Une preuve à divulgation nulle de connaissance ( ou en anglais, parfois simplement ZKP) est un protocole cryptographique permettant l'authentification sécurisée d'informations. Dans le cadre de ce protocole, une entité, nommée « fournisseur de preuve » ou prouveur peut démontrer à une autre partie, appelée le vérificateur, qu'une déclaration est vraie, sans révéler aucune information supplémentaire à son sujet. Ces preuves jouent un rôle essentiel dans la garantie de la confidentialité et de la sécurité de divers systèmes cryptographiques modernes.

En pratique, ces schémas se présentent souvent sous la forme de protocoles de type « défi/réponse » (). Le vérificateur et le fournisseur de preuve s'échangent des informations et le vérificateur contrôle si la réponse finale est positive ou négative. Il existe également des variantes sans interaction (non-interactive zero-knowledge proof) qui peuvent être construites dans le modèle de l'oracle aléatoire par l'heuristique de Fiat-Shamir.

Les preuves à divulgation nulle reposent sur trois propriétés fondamentales :

Complétude : si la déclaration est vraie et que le prouveur suit le protocole, le vérificateur sera convaincu. Robustesse : si la déclaration est fausse, un prouveur malveillant ne pourra pas convaincre un vérificateur honnête. Zéro-connaissance : le vérificateur n'acquiert aucune information supplémentaire sur la déclaration, au-delà de sa véracité.

Les ZKP peuvent être utilisées pour cacher des informations dans un registre distribué (comme une blockchain), tout en permettant la validation de ces informations. Cela est particulièrement utile dans des systèmes où les parties n'ont pas totalement confiance les unes envers les autres, tout en évitant la nécessité d'une tierce partie de confiance.

Définition formelle des preuves à divulgation nulle

Nous pouvons utiliser la notion de relation en mathématique pour définir les preuves à divulgation nulle de connaissance un peu plus rigoureusement. Ces preuves permettent à un prouveur P de convaincre un vérificateur V qu'il connaît un témoin w lié à une déclaration x telle que (x,w) ∈ R, où R est une relation bien définie. Un exemple classique est la preuve de connaissance d’un logarithme discret. Un problème difficile peut donc être vu comme une relation R dite difficile : il existe un algorithme efficace pour générer des paires (x,w)∈R et il est difficile (en pratique infaisable) de déterminer w connaissant uniquement x.

Exemples

La grotte d'Ali Baba Jean-Jacques Quisquater et Louis Guillou publient en 1989 un article intitulé How to explain zero-knowledge protocols to your children (en français : « Comment expliquer à vos enfants les protocoles sans apport de connaissance » ). On y trouve une introduction pédagogique à la notion de preuve à divulgation nulle de connaissance, basée sur le conte « Ali Baba et les quarante voleurs ». On considère deux personnes : Peggy (prouveur) et Victor (vérificateur). On considère aussi une grotte avec une bifurcation : A et B. On peut passer de A à B ou de B à A en ouvrant une porte à l'aide d'un mot magique. Peggy veut prouver à Victor qu'elle connaît le mot magique pour ouvrir la porte mais ne veut pas que Victor l'apprenne. Il s'agit d'une « preuve de connaissance » (Peggy prouve à Victor qu'elle connaît la clé) mais sans « apport d'information » (Peggy conserve son secret). Pour ce faire, Peggy et Victor vont répéter plusieurs fois le scénario suivant. Engagement. Victor (en vert) attend à l'entrée de la caverne et ne voit pas l'intérieur du tunnel. Peggy (en violet) s'introduit dans la galerie et choisit aléatoirement le cul-de-sac à gauche ou à droite, par exemple en lançant un dé ou une pièce de monnaie. Défi. Victor entre dans le tunnel et attend à la bifurcation. Il lance une pièce de monnaie. Selon le côté sur lequel tombe la pièce, Victor crie « A » ou « B ». Réponse. Peggy doit prouver maintenant qu'elle est en possession de la preuve, elle doit apparaître vers la sortie demandée par Victor.

Plusieurs cas de figure se présentent :

Peggy connaît le mot magique : si elle se trouve en A et que Victor dit « A », elle satisfait la requête ; si elle se trouve en B et que Victor dit « B », elle satisfait la requête ; si elle se trouve en A et que Victor dit « B », elle satisfait la requête en passant de A à B avec le mot magique ; si elle se trouve en B et que Victor dit « A », elle satisfait la requête en passant de B à A avec le mot magique.

Peggy ne connaît pas le mot magique : si elle se trouve en A et que Victor dit « B », elle ne satisfait pas la requête ; si elle se trouve en B et que Victor dit « A », elle ne satisfait pas la requête ; si elle se trouve en A et que Victor dit « A », elle satisfait la requête ; si elle se trouve en B et que Victor dit « B », elle satisfait la requête.

Si Peggy ne connaît pas le mot magique, il se peut que Victor soit induit en erreur dans les cas où sa requête correspond à la position actuelle de Peggy. En partant du principe qu'elle suit le protocole (critère de consistance), une erreur de Peggy sera considérée comme une preuve de non-connaissance. Victor peut de suite arrêter, il est assuré que Peggy ne connaît pas le mot magique.

En recommençant plusieurs fois à partir de la première étape, Victor peut collecter suffisamment d'informations pour être quasiment sûr que Peggy est en possession du mot magique. À chaque nouvel essai, il améliore son assurance. Si Peggy n'est pas en possession du mot magique, il y a 50 % de chance pour qu'elle commette une erreur. Avec N essais, la probabilité pour que Victor affirme que Peggy possède le secret alors qu'elle ne le possède pas est de .

Pour mettre ceci en parallèle avec des primitives cryptographiques dans le cadre d'un protocole « stimulation/réponse », il y a toujours une chance, aussi infime soit-elle, que la réponse donnée par le fournisseur de preuve soit tirée au hasard et qu'elle corresponde à ce qui était attendu par le vérificateur.

Le daltonien et les boules colorées

Dans cet exemple, on considère deux objets identiques, ayant cependant une caractéristique qui les différencie, ainsi deux boules semblables, mais de couleurs différentes. L'exemple provient de Oded Goldreich, qui utilisa deux cartes de deux couleurs différentes..

L’exemple se fonde sur une situation fictive où deux personnes interviennent : l'une est daltonienne et l'autre distingue les couleurs. Il y a deux boules indistinguables hors les couleurs, rouge et verte. Pour la daltonienne, elles sont parfaitement identiques. L'objectif est de prouver à la daltonienne que la personne qui voit les couleurs est capable de distinguer les boules grâce à leurs couleurs, mais sans que jamais leurs couleurs (rouge ou verte) soient révélées.

La personne daltonienne place les boules derrière son dos, puis prend une des boules et la montre à l’autre personne. Elle la remet dans son dos puis choisit de montrer une des boules, soit la même, soit l'autre avec une probabilité de 50 %. Elle demande alors « ai-je changé de boule ? ». Le processus est répété autant de fois qu'il le faut. Si le protocole est répété suffisamment de fois et si la personne non daltonienne donne toujours la bonne réponse, la personne daltonienne sera convaincue avec une très forte probabilité que son partenaire est effectivement capable de distinguer les boules par leur couleur. C'est un protocole de preuve à divulgation nulle de connaissance puisqu’il ne révèle jamais la couleur des boules.

La grille de Sudoku

Dans cet exemple, Peggy veut prouver à Victor qu'elle connaît la solution d'une grille standard de Sudoku. .

Pour cela, après avoir résolu la grille de Sudoku elle découpe sa grille soigneusement aux ciseaux. Elle se retrouve donc avec 81 petits carrés de papier sur lesquels sont écrits les chiffres de la grille de sudoku résolue. Elle retourne tous les bouts de papier face cachée, sauf les chiffres de départ de la grille (ceux présents avant d'avoir commencé à résoudre la grille). La procédure de la preuve peut commencer.

Victor peut alors choisir n'importe quelle ligne, colonne, ou carré 3x3. Peggy prend les 9 carrés de papier correspondants, les mélange soigneusement, et les donne à Victor. Victor peut alors vérifier qu'il y a bien les chiffres de 1 à 9. Ensuite, Peggy remet les petits carrés à leur place face cachée sur la grille. Victor répète la procédure jusqu’à avoir vérifié les 9 lignes, 9 colonnes, et les 9 carrés 3x3 de la grille de Sudoku.

À la fin de la procédure, Victor a la preuve que Peggy a la solution de la grille de Sudoku sans la connaître.

Code secret à vérifier à l'aide d'un tiers Dans cet exemple, Peggy et Victor veulent s'assurer qu'ils possèdent chacun un même code secret sans pour autant le révéler. On peut imaginer une situation dans laquelle deux agents doivent se rencontrer et confirmer leur identité à l'aide d'un code unique qui leur a été préalablement transmis parallèlement.

Imaginons que Victor connaît le code (ex. 314 091) et souhaite vérifier que Peggy possède le même sans que l'un ou l'autre le révèle. La présence d'une tierce personne de confiance, Camille, permet de vérifier, à l'aide de la méthode suivante :

Camille choisit un nombre secret (ex. 123 123) et le chuchotte à Peggy ; Peggy ajoute le nombre secret à son propre code secret, puis chuchotte le résultat à Victor ; Victor soustrait son code secret au résultat qu'il a reçu, puis le chuchotte à Camille.

Si les codes de Peggy et Victor sont identiques, Camille doit alors recevoir le nombre secret choisi au départ (123 123). Ainsi Camille peut affirmer si les codes de Victor et de Peggy sont identiques, sans pour autant le connaître : en effet, le code 314 091 n'est explicitement transmis dans aucun échange. Cette méthode permet aux personnages présents de prouver l'unicité du code secret sans le divulguer tout au long du test.

D'autres exemples pratiques Parmi les preuves cryptographiques qui existent, on peut citer :

Preuve d'un logarithme discret d'une valeur donnée Le protocole de Schnorr, pour prouver la connaissance d'un logarithme discret d'un élément de groupe public .

Supposons que Peggy souhaite prouver à Victor qu'elle connaît un secret x tel que , où est un grand nombre premier et un générateur du groupe multiplicatif modulo . Peggy veut prouver qu’elle connaît sans le révéler.

Le protocole interactif se déroule comme suit :

Initialisation Peggy et Victor s'accordent sur un grand nombre premier et un générateur du groupe multiplicatif .

Peggy choisit un secret , calcule , puis transmet la valeur à Victor.

Répétition des étapes du protocole (un grand nombre de fois) Engagement : Peggy choisit un nombre aléatoire et calcule . Elle envoie à Victor.

Défi : Victor choisit aléatoirement l'un des deux défis suivants :

Soit il demande à Peggy de révéler , Soit il demande à Peggy de révéler .

Réponse : Selon le défi, Peggy répond comme suit :

Si Victor demande , Peggy lui transmet , et Victor vérifie que .

Si Victor demande , Peggy lui transmet cette valeur, et Victor vérifie que

Sécurité du protocole

Si Peggy connaît effectivement , elle pourra toujours répondre correctement à l’un des deux défis. Si Peggy tente de tricher (sans connaître ), elle ne peut anticiper quel défi Victor choisira, et sa probabilité de réussir est de à chaque itération. En répétant le protocole plusieurs fois, cette probabilité devient arbitrairement faible.

Zéro-connaissance : Le protocole ne divulgue aucune information sûre, car le protocole ne divulgue aucune information sur , car

La valeur r est aléatoire et indépendante de x. La valeur peut être vue comme une version chiffrée de à l’aide d’un masque aléatoire (analogue au chiffrement par masque jetable ou one-time pad).