Preuve à divulgation nulle de connaissance

Un article de Wikipédia, l'encyclopédie libre.

Une preuve à divulgation nulle de connaissance est une brique de base utilisée en cryptologie dans le cadre de l'authentification et de l'identification. Cette expression désigne un protocole sécurisé dans lequel une entité, nommée « fournisseur de preuve », prouve mathématiquement à une autre entité, le « vérificateur », qu'une proposition est vraie sans toutefois 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)[1]. 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.

Les anglophones utilisent l'abréviation ZKIP pour Zero Knowledge Interactive proof.

Il existe également des variantes sans interaction (non-interactive zero-knowledge proof)[2]. Celles-ci peuvent-être construites dans le modèle de l'oracle aléatoire par l'heuristique de Fiat-Shamir.

Exemples[modifier | modifier le code]

La grotte d'Ali Baba[modifier | modifier le code]

Jean-Jacques Quisquater et Louis Guillou publient en 1989 un article intitulé « How to explain zero-knowledge protocols to your children »[3] (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 : Alice (prouveur) et Bob (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. Alice veut prouver à Bob qu'elle connaît le mot magique pour ouvrir la porte mais ne veut pas que Bob l'apprenne. Il s'agit d'une « preuve de connaissance » (Alice prouve à Bob qu'elle connaît la clé) mais sans « apport d'information » (Alice conserve son secret). Pour ce faire, Alice et Bob vont répéter plusieurs fois le scénario suivant.

Alice choisit aléatoirement le chemin A ou B; Bob attend dehors
Bob crie un des deux chemins (A ou B)
Alice apparaît sur le chemin demandé par Bob
  1. Engagement. Bob (en vert) attend à l'entrée de la caverne et ne voit pas l'intérieur du tunnel. Alice (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. Bob 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, Bob crie « A » ou « B ».
  3. Réponse. Alice doit prouver maintenant qu'elle est en possession de la preuve, elle doit apparaître vers la sortie demandée par Bob.

Plusieurs cas de figure se présentent :

  • Alice connaît le mot magique :
    • si elle se trouve en A et que Bob dit « B », elle satisfait la requête
    • si elle se trouve en B et que Bob dit « A », elle satisfait la requête
    • si elle se trouve en A et que Bob dit « A », elle satisfait la requête
    • si elle se trouve en B et que Bob dit « B », elle satisfait la requête
  • Alice ne connaît pas le mot magique :
    • si elle se trouve en A et que Bob dit « B », elle ne satisfait pas la requête
    • si elle se trouve en B et que Bob dit « A », elle ne satisfait pas la requête
    • si elle se trouve en A et que Bob dit « A », elle satisfait la requête
    • si elle se trouve en B et que Bob dit « B », elle satisfait la requête

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

En recommençant plusieurs fois à partir de la première étape, Bob peut collecter suffisamment d'informations pour être quasiment sûr qu'Alice est en possession du mot magique. À chaque nouvel essai, il améliore son assurance. Si Alice 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 Bob affirme qu'Alice 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[modifier | modifier le code]

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

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[modifier | modifier le code]

Dans cet exemple, Alice veut prouver à Bob qu'elle connaît la solution d'une grille standard de Sudoku[6].

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.

Bob peut alors choisir n'importe quelle ligne, colonne, ou carré 3x3. Alice prend les 9 carrés de papier correspondants, les mélange soigneusement, et les donne à Bob. Bob peut alors vérifier qu'il y a bien les chiffres de 1 à 9. Ensuite, Alice remet les petits carrés à leur place face cachés sur la grille. Bob 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, Bob a la preuve qu'Alice a la solution de la grille de Sudoku sans la connaître.

D'autres exemples[modifier | modifier le code]

Parmi les preuves cryptographiques qui existent, on peut citer :

Propriétés[modifier | modifier le code]

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é[modifier | modifier le code]

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[7].

Construction générale[modifier | modifier le code]

Une méthode pour construire des preuves sans divulgation de connaissances utilise ce qu'on appelle des protocoles Σ[1] (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[1].

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[modifier | modifier le code]

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[8]. 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éé[9]. 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[10].

Notes et références[modifier | modifier le code]

  1. a b et c Damgård 2010.
  2. Groth et Sahai 2008.
  3. Quisquater et Guillou 1989.
  4. Cet exemple est dû à Konstantinos Chalkias et Mike Hearn , conférence su la blockchain, [1] .
  5. (en) « Showing without Telling », sur https://wis-wander.weizmann.ac.il/, (consulté le )
  6. (en) Ronen Gradwohl, Moni Naor, Benny Pinkas et Guy N. Rothblum, « Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles », Theory Comput. Syst., vol. 44, no 2,‎ , p. 245-268 (lire en ligne)
  7. Dodis et De Souza 2009.
  8. Goldwasser, Micali et Rackoff 1985.
  9. Goldreich, Micali et Wigderson 1991.
  10. « HighTech. Née en Israël, QED-it est une start-up en Blockchain "BtoB". - Israelvalley », sur www.israelvalley.com (consulté le )

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • [Quisquater et Guillou 1989] (en) Jean-Jacques Quisquater et Louis Guillou, « How to Explain Zero-Knowledge Protocols to Your Children », Crypto, lNCS,‎ (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),‎
  • [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,‎ , p. 680-728
  • [Groth et Sahai 2008] (en) Jens Groth et Amit Sahai, « Efficient Non-interactive Proof Systems for Bilinear Groups », Eurocrypt,‎ (DOI 10.1007/978-3-540-78967-3_24, lire en ligne)

Liens externes[modifier | modifier le code]