Preuve de connaissance sans apport d'information

Preuve de connaissance sans apport d'information

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 Preuve de connaissance sans apport d'information de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Preuve a divulgation nulle de connaissance — 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

  • Preuve 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

  • 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… …   Wikipédia en Français

  • information — [ ɛ̃fɔrmasjɔ̃ ] n. f. • 1274; lat. informatio I ♦ Dr. Ensemble des actes qui tendent à établir la preuve d une infraction et à en découvrir les auteurs. ⇒ instruction (préparatoire). Ouvrir une information. Information contre X. Information… …   Encyclopédie Universelle

  • Gestion de la connaissance — Gestion des connaissances La gestion des connaissances (en anglais Knowledge Management) est l ensemble des initiatives, des méthodes et des techniques permettant de percevoir, d identifier, d analyser, d organiser, de mémoriser, et de partager… …   Wikipédia en Français

  • Ingénierie de la connaissance — Gestion des connaissances La gestion des connaissances (en anglais Knowledge Management) est l ensemble d initiatives, des méthodes et des techniques permettant de percevoir, d identifier, d analyser, d organiser, de mémoriser, et de partager des …   Wikipédia en Français

  • ZKIP — 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 — 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 — 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

  • Droit d'auteur — Propriété intellectuelle Propriété littéraire et artistique Droit d auteur et copyright Droits voisins Propriété industrielle Créations utilitaires: Brevet Secret industriel et …   Wikipédia en Français

Share the article and excerpts

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