Preuve à divulgation nulle de connaissance

Une preuve à divulgation nulle de connaissance (Zero Knowledge Interactive proof ou ZKIP en anglais) 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 », prouve mathématiquement à une autre entité, le « vérificateur », qu'une proposition est vraie sans révéler d'autres informations que la véracité de la proposition.

En pratique, ces schémas se présentent souvent sous la forme de protocoles de type « défi/réponse » (challenge-response). 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.

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 » (ou « 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.

Peggy choisit aléatoirement le chemin A ou B; Victor attend dehors

Victor crie un des deux chemins (A ou B)

Peggy apparaît sur le chemin demandé par Victor

1. 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.
2. 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 ».
3. 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 ${\frac {1}{2^{N}}}~$.

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 ^{[source détournée]}.

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 :

1. Camille choisit un nombre secret (ex. 123 123) et le chuchotte à Peggy
2. Peggy ajoute le nombre secret à son propre code secret, puis chuchotte le résultat à Victor
3. 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

Parmi les preuves cryptographiques qui existent, on peut citer :

• Le protocole de Schnorr, pour prouver la connaissance d'un logarithme discret $x$ d'un élément de groupe public $h=g^{x}$;
• Le protocole de Guillou-Quisquater, qui permet de prouver la connaissance d'un message clair derrière un chiffré RSA.

Propriétés

Trois propriétés doivent être satisfaites :

• consistance (completeness) : si le fournisseur de preuve et le vérificateur suivent le protocole alors le vérificateur doit toujours accepter la preuve.
• robustesse (soundness) : si la proposition est fausse, aucun fournisseur de preuve malveillant ne peut convaincre un vérificateur « honnête » que la proposition est vraie et ceci avec une forte probabilité.
• aucun apport d'information (zero knowledge) : le vérificateur n'apprend de la part du fournisseur de preuve rien de plus que la véracité de la proposition, il n'obtient aucune information qu'il ne connaissait déjà sans l'apport du fournisseur de preuve. Si le vérificateur ne suit pas la procédure, cette définition reste valable aussi longtemps que le fournisseur de preuve suit la procédure.

Les deux premières propriétés sont les mêmes qui servent à définir un système de preuve interactive, qui est un concept plus général. C'est la troisième propriété qui fait le zero knowledge.

Sécurité

La sécurité des preuves peut être classée en plusieurs catégories, suivant la sécurité attendue par les différentes notions de sécurité précédemment définies, c'est-à-dire la robustesse et le non-apport de connaissance. On parle alors de :

• preuve « calculatoire » : impossibilité pour un observateur de distinguer en un temps polynomial une preuve authentique d'une preuve forgée ou aléatoire
• preuve « statistique », ou parfaite : la distribution des preuves authentiques est la même que celle des preuves aléatoires ou forgées. Cela peut se voir de la même manière que pour les preuves calculatoires, en donnant une puissance de calcul infinie (ou non bornée) au distingueur.

La première ne rejette pas l'existence d'une méthode (mais celle-ci, si elle existe, n'aura pas une complexité polynomiale) alors que la preuve parfaite assure qu'aucune méthode n'existe (d'après la théorie de l'information).

De manière similaire, si la robustesse est statistique, le terme « preuve » sera utilisé, autrement si elle est calculatoire, le terme « argument » sera utilisé pour désigner la preuve.

Construction générale

Une méthode pour construire des preuves sans divulgation de connaissances utilise ce qu'on appelle des protocoles Σ (ainsi nommés en raison de la communication en trois échanges qui fait penser à la lettre grecque Sigma). Un protocole Σ est un protocole interactif entre un prouveur et un vérifieur mettant en jeu trois échanges :

• L’engagement, qui est un premier message envoyé par le prouveur au vérifieur ;
• Le défi, qui est une réponse envoyée par le vérifieur ;
• La réponse, qui est le dernier message envoyé par le prouveur.

La sécurité d'un protocole Σ est très proche de celle d'une preuve sans divulgation de connaissance : la consistance, la robustesse spéciale et l'apport nul d'information avec un vérifieur honnête. La construction générale consiste alors à imposer l'honnêteté au vérifieur en l'obligeant à générer son défi indépendamment de l’engagement par le biais d’un schéma de mise en gage cryptographique.

De multiples preuves sans divulgation de connaissances reposent sur cette construction, par exemple le protocole de Schnorr, ou le schéma d'identification de Guillou-Quisquater. Une des raisons pouvant être qu'il est plus aisé de travailler sur les protocoles Σ, qui possèdent en plus des bonnes propriétés de régularité : il existe des constructions pour effectuer la conjonction et la disjonction de protocoles Σ. Propriétés que l'on n'a pas sur les preuves sans divulgation de connaissances génériques.

Histoire

Ce sont Shafi Goldwasser, Silvio Micali et Charles Rackoff qui ont utilisé, pour la première fois en 1985, le terme « preuve à divulgation nulle de connaissance », ou plus précisément sa forme anglaise, « zero knowledge proof », dans leur article fondateur. Shafi Goldwasser et Silvio Micali ont reçu le prix Turing en 2012 pour leurs travaux.

Ce sont Oded Goldreich, Silvio Micali et Avi Wigderson qui ont découvert qu'en supposant l'existence de primitives cryptographiques, un système de preuve à divulgation nulle de connaissance pour le problème de la 3-coloration de graphe peut être créé. Ceci implique que tous les problèmes dans NP ont un tel système de preuve.

Shafi Goldwasser met aujourd’hui ses travaux en application au sein de QED-it, qui a fait du ZKIP son cœur de métier.

Annexes

Articles connexes

• Gestion des documents d'archives
• Heuristique de Fiat-Shamir
• Preuves interactives (classe de complexité)

Bibliographie

• [Quisquater et Guillou 1989] (en) Jean-Jacques Quisquater et Louis Guillou, « How to Explain Zero-Knowledge Protocols to Your Children », Crypto, lNCS,‎ 1989 (lire en ligne)
  Co-signé avec la famille des auteurs.
• [Goldwasser, Micali et Rackoff 1985] (en) Shafi Goldwasser, Silvio Micali et Charrles Rackoff, « The knowledge complexity of interactive proof-systems », Symposium of the Theory of Computation (STOC),‎ 1985
• [Goldreich, Micali et Wigderson 1991] (en) Oded Goldreich, Sivlio Micali et Avi Wigderson, « Proofs that yield nothing but their validity », Journal of the ACM, vol. 38,‎ 1991, p. 680-728
• [Groth et Sahai 2008] (en) Jens Groth et Amit Sahai, « Efficient Non-interactive Proof Systems for Bilinear Groups », Eurocrypt,‎ 2008 (DOI 10.1007/978-3-540-78967-3_24, lire en ligne)

Liens externes

• [Dodis et De Souza 2009] (en) Yevgeniy Dodis et Bianca De Souza, « Advanced Cryptography », Notes de cours [PDF], 14 octobre 2009.
• [Damgård 2010] (en) Ivan Damgård, « On Σ-Protocols », Notes de cours [PDF],‎ 2010