Preuve à divulgation nulle de connaissance

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

Vous avez de nouveaux messages (diff^?).

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 « stimulation/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évation ZKIP pour Zero Knowledge Interactive proof.

Sommaire

1 Propriétés
- 1.1 Preuves calculatoires et parfaites
2 Exemple
3 Histoire
4 Références
5 Voir aussi
- 5.1 Liens internes
- 5.2 Liens externes

[modifier] 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
solidité (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.

[modifier] Preuves calculatoires et parfaites

Les preuves peuvent être classées en deux catégories :

preuve « calculatoire » : impossibilité pour un observateur de distinguer en un temps polynomial une preuve authentique d'une preuve forgée ou aléatoire
preuve « parfaite » : impossibilité pour un observateur de distinguer une preuve authentique d'une preuve forgée ou aléatoire

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

[modifier] Exemple

Jean-Jacques Quisquater et Louis Guillou publient en 1990 un papier 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 explication simple basée sur le conte « Ali Baba et les quarante voleurs ».

Soit 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 :

[modifier] Première étape

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.

[modifier] Deuxième étape

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

[modifier] Troisième étape

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

Plusieurs cas de figures 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 $\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.

[modifier] Histoire

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 premier fois dans leur article fondateur. ^[1]

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éé.^[2] Ceci implique que tous les problème dans NP ont un tel système de preuve.

[modifier] Références

↑ Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems. Proceedings of 17th Symposium on the Theory of Computation, Providence, Rhode Island. 1985. Draft. Extended abstract
↑ Oded Goldreich, Silvio Micali, Avi Wigderson. Proofs that yield nothing but their validity. Journal of the ACM, volume 38, issue 3, p.690-728. July 1991.