Zero-knowledge

Zero-knowledge

Preuve à divulgation nulle de connaissance

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éviation ZKIP pour Zero Knowledge Interactive proof.

Sommaire

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.

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

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

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

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

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

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

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 première 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.

Références

  1. 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
  2. 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.

Voir aussi

Liens internes

Liens externes

  • Portail de la cryptologie Portail de la cryptologie
  • Portail de la sécurité informatique Portail de la sécurité informatique
Ce document provient de « Preuve %C3%A0 divulgation nulle de connaissance ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Zero-knowledge de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Zero-Knowledge — Ein Zero Knowledge Beweis oder Zero Knowledge Protokoll ist ein Protokoll aus dem Bereich der Kryptografie. Bei einem Zero Knowledge Protokoll kommunizieren zwei Parteien (der Beweiser und der Verifizierer) miteinander. Der Beweiser überzeugt… …   Deutsch Wikipedia

  • Zero Knowledge — Ein Zero Knowledge Beweis (auch kenntnisfreier Beweis) oder Zero Knowledge Protokoll (auch kenntnisfreies Protokoll) ist ein Protokoll aus dem Bereich der Kryptografie. Bei einem Zero Knowledge Protokoll kommunizieren zwei Parteien (der Beweiser… …   Deutsch Wikipedia

  • Zero knowledge — Preuve à divulgation nulle de connaissance 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 …   Wikipédia en Français

  • Zero-knowledge web application — Zero knowledge web applications are a special kind of online services that were defined and introduced by the development team at [http://www.clipperz.com Clipperz] in 2006. They dubbed their online password manager the first zero knowledge web… …   Wikipedia

  • Zero-knowledge proof — In cryptography, a zero knowledge proof or zero knowledge protocol is an interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the veracity of the statement.A… …   Wikipedia

  • Zero-Knowledge-Beweis — Ein Zero Knowledge Beweis oder Zero Knowledge Protokoll ist ein Protokoll aus dem Bereich der Kryptografie. Bei einem Zero Knowledge Protokoll kommunizieren zwei Parteien (der Beweiser und der Verifizierer) miteinander. Der Beweiser überzeugt… …   Deutsch Wikipedia

  • Zero-Knowledge-Protokoll — Ein Zero Knowledge Beweis oder Zero Knowledge Protokoll ist ein Protokoll aus dem Bereich der Kryptografie. Bei einem Zero Knowledge Protokoll kommunizieren zwei Parteien (der Beweiser und der Verifizierer) miteinander. Der Beweiser überzeugt… …   Deutsch Wikipedia

  • Zero-knowledge password proof — A zero knowledge password proof (ZKPP) refers to a password authenticated key agreement protocol that is secure against off line dictionary attacks. The terminology zero knowledge password proof is not used in the technical (cryptographic)… …   Wikipedia

  • zero-knowledge — adjective Describing situations in which the veracity of a statement may be shown to be true without revealing any other information …   Wiktionary

  • Non-interactive zero-knowledge proof — Non interactive zero knowledge proofs are a variant of zero knowledge proofs. Blum, Feldman, and Micali [1] showed that a common reference string shared between the prover and the verifier is enough to achieve computational zero knowledge without …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”