Preuve à divulgation nulle de connaissance

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Une preuve à divulgation nulle de connaissance est un concept utilisé 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 une autre information que la véracité de la proposition.

En pratique, ce schéma se présente souvent sous la forme d'un protocole 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.

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

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 malicieux 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é 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éatoire ou forgée. 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[1].

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 Σ[2] (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[2].

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.

Exemple[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 explication simple basée sur le conte « Ali Baba et les quarante voleurs ».

Soient deux personnes : Alice et Bob. Alice veut prouver à Bob qu'elle connaît le mot magique pour ouvrir la porte mais ne veut pas que Bob l'apprenne. On est donc bien en présence d'une « preuve de connaissance » (Alice 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 :

Première étape : l’engagement[modifier | modifier le code]

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.

Zkip alibaba1.png

Deuxième étape : le défi[modifier | modifier le code]

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 ».

Zkip alibaba2.png

Troisième étape : la réponse[modifier | modifier le code]

Alice doit prouver maintenant qu'elle est en possession de la preuve, elle doit se diriger vers la sortie demandée par Bob.

Zkip alibaba3.png

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.

Exemples en cryptographie[modifier | modifier le code]

Parmi les preuves cryptographiques qui existent, on peut citer :

Histoire[modifier | modifier le code]

Ce sont Shafi Goldwasser, Silvio Micali et Charles Rackoff qui ont utilisé le terme pour « preuve à divulgation nulle de connaissance » usité en anglais pour la première fois dans leur article fondateur[4].

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

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

Annexes[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, série 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 yeld nothing but their validity », Journal of the ACM, vol. 38,‎ , p. 680-728

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]