Protocole de preuve sans connaissance c. Preuve de connaissance nulle. Que résulte-t-il de tout cela ?

Une belle terminologie est l’un des avantages de la cryptographie moderne. Les noms de groupes punk ou les surnoms Tumbl sont ce à quoi ressemblent des termes cryptographiques comme « prédicat hardcore », « fonction de trappe » ou « cryptanalyse différentielle impossible ». Il me semble qu'un terme comme " zéro connaissance".

Mais la beauté du terme « connaissance zéro » conduit à ses abus. Les gens pensent immédiatement que zéro connaissance devient synonyme de « très, très sécurisé ». Pour cette raison, ces mots sont ajoutés aux noms des systèmes de sécurité et réseaux anonymes– ce qui n’a en réalité rien à voir avec le protocole de connaissance zéro.

Nous avons dit tout cela pour souligner l'essentiel : preuve avec zéro connaissance(preuve de connaissance nulle) est l'un des plus des outils puissants cryptographie jamais développée. Mais malheureusement, il a été relativement peu étudié. Essayons de donner une explication non mathématique de ce qui rend ZK (zéro connaissance) si spécial. Nous parlerons ici de certains protocoles ZK actuels.

Origine du savoir zéro

Avant Goldwasser et d’autres, la plupart des travaux dans ce domaine se concentraient sur les systèmes de preuve d’exactitude. Autrement dit, dans les cas où un attaquant - le testeur - tente de tromper le contrôleur en lui glissant une fausse valeur. Mais Goldwasser, Micali et Rakoff ont regardé le côté opposé de ce problème. Au lieu de se soucier uniquement du testeur, ils ont demandé : que se passe-t-il si vous ne faites pas confiance au contrôleur ?

Ils étaient particulièrement préoccupés par la possibilité de fuites d'informations. Plus précisément, ils ont demandé combien Informations Complémentaires le contrôleur recevra-t-il au cours de la preuve que la déclaration est vraie ?

Il est important de noter qu’il ne s’agit pas là d’un simple intérêt théorique. Il existe des applications réelles et pratiques dans lesquelles ces éléments sont importants.

En voici une : imaginez que le client est dans monde réel souhaite se connecter au serveur Web à l'aide d'un mot de passe. L'approche standard du « monde réel » du problème consiste à stocker une version hachée du mot de passe sur le serveur. La connexion à un tel système est considérée comme une sorte de « confirmation » que le hachage du mot de passe fourni est la sortie de la fonction de hachage. mot de passe actuel. Et, plus important encore, comme « confirmation » que le client connaît réellement le mot de passe.

La plupart des systèmes du monde réel implémentent cette « confirmation » de la pire manière possible. Le client transmet simplement le mot de passe d'origine au serveur, qui recalculera hachage du mot de passe et le compare avec la valeur stockée. Le problème ici est évident : le serveur reçoit mon mot de passe sous la forme la plus attractive pour les pirates, « texte brut ». Et l’utilisateur ne peut que prier pour que la sécurité du serveur ne soit pas compromise.

Ce que Goldwasser, Micali et Rakoff proposaient, c'était l'espoir de nouvelles méthodes de confirmation. Si elles sont entièrement mises en œuvre, les preuves sans connaissance pourront fournir une preuve du problème décrit ci-dessus. Sans divulguer la moindre information qui corresponde au fait que « cette affirmation est vraie ».

Exemple du « monde réel »

Jusqu’à présent, nous avons parlé de choses plutôt abstraites. Allons-y et apportons exemple réel(un peu fou) pour un protocole zéro connaissance.

Pour m'aider à expliquer cet exemple, imaginons que je suis un magnat des télécommunications et que je suis en train de déployer un nouveau réseau cellulaire. La structure de mon réseau est présentée ci-dessous dans ce graphique. Chaque sommet du graphique représente un émetteur mobile et les lignes de connexion (bords) montrent où deux cellules se chevauchent. Dans ces endroits, les émetteurs interféreront les uns avec les autres. La bonne nouvelle est que la structure de mon réseau permet à chaque tour d'être configurée dans l'une des trois bandes de fréquences pour éviter une telle influence.

Ainsi, la tâche de déployer mon réseau revient à attribuer sa propre voie à chaque tour de manière à ce que les cellules ne se croisent pas. Si nous utilisons des couleurs pour représenter les bandes de fréquences, nous pouvons rapidement développer une solution à ce problème :

Bien sûr, beaucoup d’entre vous l’ont déjà remarqué. Ce que j'ai décrit ici est seulement cas particulier fameux problème théorique. C’est ce qu’on appelle le « problème de coloration des graphiques en trois couleurs ». Vous connaissez peut-être aussi un très fonctionnalité intéressante ce problème. Pour certains graphiques, il est très difficile de trouver une solution ou même de déterminer qu’une telle solution existe. Le problème de la coloration d'un graphique en trois couleurs (et de la recherche d'une réponse à la question de savoir si une telle solution existe pour ce cas), comme on le sait, appartiennent à la catégorie des problèmes NP-complets.

Il va sans dire que les énigmes de jouets ci-dessus sont faciles à résoudre. Et si ce n’était pas si simple ? Par exemple, imaginez que mon réseau communications cellulairesétait très vaste et complexe. Dans ce cas, je n’aurais pas assez de puissance de calcul pour trouver une solution. Dans ce cas, il serait conseillé de déléguer le problème à quelqu'un d'autre. À ceux qui disposent de suffisamment de puissance de calcul. Par exemple, je pourrais demander à Google de résoudre ce problème.

Mais il y a un problème.

Supposons que Google me donne toute la puissance de calcul dont j'ai besoin pour trouver une solution à la coloration correcte de mon graphique. Je ne vais certainement pas les payer tant que je ne serai pas sûr qu'ils aient cette solution. Dans le même temps, Google ne me fournira pas de copie de la décision tant que je ne l'aurai pas payée. Nous sommes dans une impasse.

DANS la vraie vie bon sens nous donne la réponse à ce dilemme, qui inclut les services d'avocats et de comptes séquestres. Mais ici, nous ne parlons pas de la vie réelle, mais de cryptographie. Et si vous avez déjà lu les travaux des cryptographes, vous savez déjà que le seul moyen trouver une solution à un problème - proposer quelque chose de complètement fou solution technique. Solution technique folle (avec des chapeaux)

Imaginons que des employés de Google consultent Silvio Micali du MIT, et qu'il interroge ses collègues Oded Goldreich et Avi Wigderson. Après consultation, ils ont développé un protocole si beau qu’il ne nécessite même pas d’ordinateurs. Un grand entrepôt avec une réserve de crayons de couleur et de papier sera utilisé. Vous aurez également besoin d'un grand nombre de chapeaux.

Voyons comment ça marche

Tout d'abord, je vais entrer dans un entrepôt et recouvrir le sol de papier pour créer un espace représentant mon réseau cellulaire. Ensuite, je quitterai l'entrepôt. Google peut désormais intervenir, mélanger la collection de crayons et choisir trois couleurs (comme rouge/bleu/violet, comme dans cet exemple) ainsi que la couleur pour représenter la solution. Notez que la couleur spécifique utilisée n’a pas d’importance.

Avant de quitter l'entrepôt, Google recouvre chaque haut d'un chapeau. À mon retour, c'est tout ce que je verrai :

Évidemment, cette approche protégera parfaitement le secret de Google. Mais cela ne m'aidera pas du tout. Il est possible que Google remplisse les couleurs de manière aléatoire, ce qui signifie dans le mauvais ordre. Ou peut-être qu’ils n’ont rien rempli du tout.

Pour me convaincre que le problème a bien été résolu, Google me donne la possibilité de « vérifier » le résultat de la coloration de ses graphiques. J'ai le droit de choisir, dans un ordre aléatoire, une face de ce graphe (c'est-à-dire le long d'une ligne entre deux chapeaux adjacents). Google supprimera ces deux chapeaux, me montrant une petite partie de la solution :

Veuillez noter que mon expérience a deux résultats possibles :

Si deux sommets affichés ont la même couleur (ou pas de couleur du tout !), alors je sais avec certitude que Google me ment. Dans ce cas, je ne paierai même pas un centime à Google. Si les deux sommets affichés ont des couleurs différentes, alors Google ne me trompe pas dans ce cas.

J'espère que la première affirmation est évidente. La seconde nécessitera une explication plus détaillée. Le problème est que même si l’expérience réussit, Google peut toujours me tromper. Pourtant, je n’ai regardé que sous deux chapeaux. S'il y a E arêtes distinctes dans le graphique, Google fournira probablement une solution incorrecte. Par exemple, après un test, ils me trompent avec la probabilité (E-1)/E (qui pour 1000 arêtes serait de 99,9 %).

Heureusement, Google a la réponse à cette question. Nous allons simplement exécuter à nouveau le protocole !

Nous prenons du papier vierge pour créer une nouvelle copie du graphique. Google lance désormais un nouveau mélange aléatoire de trois crayons de couleur. Ensuite, ils remplissent le graphique la bonne décision, mais en utilisant un nouvel ensemble aléatoire de trois couleurs.

Encore une fois, nous effectuons l'opération avec des chapeaux. J'y retourne et sélectionne au hasard de nouveaux sommets. Revenons à la logique décrite ci-dessus. Cette fois, si tout se passe bien, je serai beaucoup plus sûr que Google me dise la vérité. En effet, pour me tromper, Google devrait avoir deux fois de la chance.

Un tel événement peut se produire, mais sa probabilité sera encore plus faible. La chance que Google me trompe deux fois de suite est (E-1)/E*(E-1)/E (soit environ 99,8 % de chance pour notre exemple à 1 000 bords).

Heureusement, nous ne devons pas nous arrêter à deux tentatives. Nous essaierons encore et encore jusqu’à ce que nous soyons convaincus que Google dit, avec un degré de probabilité élevé, la vérité.

Je vous exhorte à ne pas me croire sur parole. Essayez ce Javascript et voyez par vous-même.

Notez que je ne suis jamais complètement sûr que Google soit honnête – il y a toujours une infime chance qu’il me trompe. Mais, après grande quantité itérations (E^2, comme dans notre cas), j'arriverai finalement au point où Google me trompe avec une probabilité négligeable - suffisante pour une application pratique. Après cela, je peux facilement donner l'argent à Google.

Il est important que Google soit également protégé dans ce cas. Si j'essaie d'apprendre quelque chose en enregistrant et en analysant des notes entre les exécutions du protocole, j'échouerai parce que Google utilise des couleurs aléatoires à chaque itération. Informations limitées, ce que je peux obtenir ne me donnera rien. Je n’ai aucun moyen de relier ces données ensemble.

Qu’est-ce qui fait que cet exemple est « zéro connaissance » ?

J'essaie de vous convaincre que ce protocole ne permet pas de fuite d'informations Solution Google. Mais vous n’êtes pas obligé de me croire sur parole ! La première règle des cryptographes est de ne jamais croire de telles choses sans preuves.

Goldwasser, Micali et Rakoff ont proposé trois critères auxquels doit répondre tout protocole à connaissance nulle. De manière informelle, ils peuvent être décrits comme suit :

Complétude. Si Google me dit la vérité, alors je devrais en avoir des preuves solides (preuves à haute probabilité). Fiabilité. Google ne peut me convaincre que s'il dit réellement la vérité. « Zéro divulgation » (ce critère s’appelle en réalité ainsi). Je n'ai rien d'autre à découvrir que la solution Google dont je dispose.

Nous avons déjà discuté des arguments en faveur de l'exhaustivité. Le protocole finira par me convaincre (avec un risque d'erreur négligeable) si je l'exécute suffisamment de fois. La fiabilité est également assez facile à démontrer. Si Google essaie de me tromper, je le détecterai dans la grande majorité des cas.

La propriété la plus difficile reste « zéro connaissance ». Pour le comprendre, faisons une expérience de pensée plutôt étrange.

Expérience de pensée avec des machines à voyager dans le temps

Tout d’abord, commençons par une hypothèse folle. Imaginons que les ingénieurs de Google ne soient pas aussi intelligents qu'on le pense. Ils travaillent sur ce problème semaine après semaine et ne trouvent pas de solution. Douze heures avant la date limite, Google se désespère. Ils décident de me tromper et disent qu'ils ont un livre de coloriage pour le Comte (même s'ils n'en ont pas réellement).

Leur idée est de s'arrêter à l'atelier GoogleX et d'emprunter le prototype de la machine à voyager dans le temps de Google. Le plan initial était de remonter quelques années en arrière et d’utiliser le temps de travail supplémentaire pour trouver de nouvelles solutions au problème. Malheureusement, comme de nombreux autres prototypes de Google, la machine à voyager dans le temps présentait un certain nombre de limitations. Plus important encore, elle ne peut voyager dans le temps que quatre minutes et demie.

Ainsi, il n’est pas nécessaire d’utiliser une machine à voyager dans le temps pour augmenter le temps nécessaire à la réalisation d’un travail. Mais il s’avère quand même que cette technologie très limitée peut être utilisée pour me tromper.

Je ne sais vraiment pas ce qui se passe ici. Mais il semble que cela serait utile.

Le plan s’est avéré diablement simple. Si Google ne sait pas comment le graphique doit être coloré, il colore simplement le papier de manière aléatoire, puis couvre les sommets avec des chapeaux. Si, par chance, les sommets s'avèrent être de couleurs différentes, nous pousserons tous un soupir de soulagement et continuerons à travailler, croyant que tout va bien.

Supposons que j'enlève une paire de chapeaux et que je découvre deux sommets de la même couleur. Si le protocole est mis en œuvre de la manière habituelle, Google échouera dans ce cas. Mais nous utilisons une machine à voyager dans le temps. Chaque fois que Google se trouve dans une position délicate, il corrige simplement la situation. Autrement dit, un employé de Google spécialement désigné appuie sur l'interrupteur, le temps est reculé de quatre minutes et demie et l'équipe de Google peint le graphique avec une toute nouvelle solution aléatoire. Après cela, ils avancent rapidement et réessayent.

Essentiellement, la machine à voyager dans le temps permet à Google de « réparer » tout échec de connexion sans que je me doute de quoi que ce soit. Étant donné que de mauvais résultats ne se produiront que 1/3 du temps, le temps d'exécution attendu du protocole (du point de vue de Google) n'est que légèrement plus long que si le protocole était exécuté de manière équitable. De mon point de vue, je ne sais même pas si ce voyage dans le temps a lieu.

Ce dernier point est le plus important. De mon point de vue, j'interagis avec le protocole de la même manière, qu'il y ait ou non une machine à voyager dans le temps. Et pourtant, il convient de le noter encore une fois : dans la version Time Machine, Google n'a absolument aucune information sur la façon de colorer le graphique.

Et qu’est-ce qui en découle ?

Ce que nous venons de montrer est un exemple théorique. Dans un monde où le temps ne fait qu'avancer et où personne ne peut me tromper avec une machine à voyager dans le temps, le protocole du chapeau fonctionne correctement. Après E^2 tours d'exécution, je devrais être sûr (pas complètement, mais avec une probabilité négligeable de tricher) que le graphique est correctement coloré et que Google a fourni les informations correctes.

Si le temps peut être manipulé (en particulier si Google peut « rebobiner le temps »), alors il peut simuler le protocole, même s'il ne dispose d'aucune information sur la façon dont le graphique doit être coloré.

De mon point de vue, quelle est la différence entre ces deux protocoles ? Ils ont le même distribution statistique et virer le même montant informations utiles.

Croyez-le ou non, cela prouve quelque chose de très important.

En particulier, cela suppose que j'ai (le vérificateur) une sorte de stratégie qui me permettra "d'extraire" des informations utiles sur la façon dont Google effectue la coloration si j'exécute un protocole honnête. Alors ma stratégie devrait tout aussi bien fonctionner si je me laisse tromper par la machine à voyager dans le temps. Les exécutions du protocole sont, de mon point de vue, statistiquement identiques. Physiquement, je ne peux pas montrer la différence.

Ainsi, la quantité d'informations que je recevrai dans la « vraie expérience » et dans « l'expérience de la machine à voyager dans le temps » est complètement identique. La quantité d’informations que Google met dans l’expérience Time Machine est exactement nulle. Par conséquent, même dans le monde réel, il n’y aura aucune fuite d’informations. Il ne reste plus qu'à montrer que les informaticiens disposent d'une machine à voyager dans le temps (chut, c'est un secret).

Comment se débarrasser des chapeaux et des machines à remonter le temps

Bien sûr, nous ne voudrions pas réellement exécuter le protocole en utilisant des chapeaux. Et même Google (très probablement) ne dispose pas de machine en temps réel.

Pour relier toutes ces choses ensemble, nous devons introduire ce protocole dans le monde numérique. Pour ce faire, nous avons besoin d’un équivalent numérique d’un « chapeau » : quelque chose qui cache le sens numérique, et en même temps « lie » le sens et son créateur (créant un « engagement »), afin qu’il ne puisse pas changer d’avis. .

Heureusement, nous disposons d'un excellent outil pour cette application. C'est ce qu'on appelle un programme d'engagement numérique. Un système d'engagement permet à une partie de créer un « engagement » pour un message, en le gardant secret, puis d'ouvrir « l'engagement » pour voir ce qu'il contient. Ils peuvent être construits à partir de divers composants, notamment de puissantes fonctions de hachage cryptographique.

Une fois que nous avons eu le plan d’engagement, nous avons assemblé tous les composants pour exécuter électroniquement le protocole sans connaissance. Le testeur code d'abord la coloration des sommets sous la forme d'un ensemble de messages numériques (par exemple, les nombres 0, 1, 2), puis génère des obligations numériques pour chacun. Ces obligations sont transmises au Responsable du traitement. Lorsque le contrôleur ouvre un bord, le testeur révèle les valeurs des obligations qui correspondent aux deux sommets.

C'est ainsi que nous avons réussi à nous débarrasser des chapeaux. Mais comment prouver que ce protocole est une connaissance nulle ?

Mais nous sommes désormais dans le monde numérique. Nous n’avons donc pas besoin d’une machine à voyager dans le temps pour confirmer que le protocole fonctionne. L’astuce clé est que le protocole ne fonctionnera pas entre deux personnes, mais entre deux programmes informatiques différents (ou, plus formellement, deux machines de Turing probabilistes.)

Nous pouvons maintenant prouver le théorème suivant : si le contrôleur doit extraire des informations utiles lorsque démarrage normal protocole, il recevra la même quantité d'informations utiles qu'avec un lancement « trompeur » du protocole, où le testeur n'a investi aucune information dès le début.

Nous parlons de programmes informatiques, et ils peuvent « remonter le temps ». Par exemple, envisagez d'utiliser une machine virtuelle capable de prendre des instantanés. Exemple de "temps de rembobinage" utilisant machines virtuelles. Initialement, la machine virtuelle suit un chemin, retourne à état d'origine, puis l'exécution bifurque vers un nouveau chemin.

Même si l'on ne considère pas les machines virtuelles, n'importe quel programme informatique peut être « rembobiné » pour état précédent, simplement en exécutant le programme depuis le tout début et en envoyant les mêmes données en entrée. À condition que les intrants (y compris les intrants) nombres aléatoires), sont corrigés, le programme suivra toujours le même chemin d'exécution. Nous pouvons ainsi rembobiner le programme, en le démarrant depuis le début et en « bifurquant » son exécution lorsque le programme atteint un certain point souhaité.

En fin de compte, ce que nous obtenons peut être représenté comme un théorème. Si pour le contrôleur il y a programme informatique, qui extrait avec succès des informations utiles du testeur (en interagissant avec le protocole), le testeur peut alors utiliser l'astuce de rembobiner le programme, alimentant le contrôleur en solutions aléatoires. Il utilise la même logique que celle que nous avons déjà appliquée ci-dessus : si le contrôleur parvient à extraire des informations en exécutant un protocole réel, alors il obtiendra la même quantité d'informations en exécutant un faux protocole basé sur le rembobinage du programme. Mais comme le faux protocole ne transmet aucune donnée utile, aucune information ne peut être extraite. Ainsi, les informations que le Contrôleur peut extraire sont toujours nulles.

Que résulte-t-il de tout cela ?

En résumé, on peut dire que le protocole est complet et fiable. On peut parler de fiabilité dans toute situation dans laquelle les deux parties ne cherchent pas à se tromper.

Dans le même temps, le protocole n’a aucune connaissance. Pour le prouver, nous avons montré qu’un programme exécuté par le contrôleur pour extraire des informations sera capable d’extraire des données d’un programme qui ne possède aucune donnée significative. Cela conduit à une contradiction évidente, qui nous dit que le protocole, dans aucune situation, ne divulgue d'informations.

Cela nous donne des avantages importants. Puisque n'importe qui peut créer une fausse transcription (comme l'exemple de Google où ils ont essayé de me convaincre qu'ils avaient une solution), je ne peux pas relire la transcription pour prouver mon cas à quelqu'un d'autre (comme un juge). Le juge dira qu'il n'est pas sûr que l'enregistrement ait été réalisé honnêtement et qu'il n'ait pas été édité (comme dans l'exemple de Google et de l'utilisation de la machine à voyager dans le temps). Cela signifie que la transcription elle-même ne contient aucune information. Le protocole n’a de sens que si j’y participe moi-même et si je peux être sûr que tout s’est passé en temps réel.

Des preuves pour tous les IP !

Pour ceux qui sont arrivés jusqu'ici, j'ai nouvelle importante. La tâche de colorer un réseau cellulaire en trois couleurs est intéressante en soi, mais ce n'est pas tout. La chose vraiment intéressante à propos du problème des trois couleurs est qu’il est NP-complet. Cela signifie que tout autre problème appartenant à la classe NP peut être réduit à celui-ci.

En termes simples, Goldrich, Micali et Widgerson ont prouvé qu'il existe des ZK « efficaces » pour une large classe de problèmes utiles. Beaucoup d’entre eux sont bien plus intéressants que le problème de l’attribution des fréquences dans un réseau cellulaire.

Il vous suffit de trouver l'énoncé (en NP) que vous souhaitez tester et de le traduire en un problème de coloration de graphiques en trois couleurs. À partir de ce point, vous pouvez exécuter une version numérique de notre protocole avec des chapeaux.

Au lieu de résultats

Bien sûr, il serait incroyablement stupide de commencer immédiatement à utiliser ce protocole dans la pratique. Son coût de calcul comprendra la taille totale de la déclaration et des preuves originales, plus le coût de traduction du problème en graphique et 2 autres exécutions du protocole nécessaires pour vérifier l'exactitude de la solution. En théorie, c'est "efficace", mais comme coût total la preuve sera un polynôme de la longueur de l'entrée ; en pratique, cela n'est pas applicable.

Nous avons donc seulement prouvé jusqu’à présent que de telles preuves étaient possibles. Reste à trouver des preuves suffisamment pratiques pour une utilisation réelle.

Remarques

* Formellement, le but d'une preuve interactive est de convaincre le contrôleur qu'une certaine chaîne appartient à un langage particulier. En règle générale, le testeur dans les tâches a une puissance illimitée et le contrôleur est limité dans sa capacité à effectuer des calculs.

** Cet exemple est basé sur la solution originale de Goldwasser, Micali et Rakoff, et sur un exemple de didacticiel utilisant des chapeaux de Silvio Micali.

****** Un exemple simple d'engagement peut être construit à l'aide d'un exemple de fonction de hachage. Pour créer un engagement sur la valeur "x", nous générons simplement une chaîne (suffisamment longue) de nombres aléatoires, que nous appelons "sel", et l'engagement de sortie est C = hash(salt || x). Pour ouvrir un engagement, il vous suffit d'ouvrir "x" et "sel". N'importe qui peut vérifier que l'engagement initial est valide en recalculant à nouveau le hachage. Ce méthode sûre sous certaines hypothèses modérément fortes sur la fonction elle-même.

L'un des meilleurs côtés la cryptographie moderne est sa belle terminologie. Vous pouvez créer autant de groupes punk que vous le souhaitez avec des noms comme Hardcore Predicate, Trapdoor Function ou Impossible Differential Cryptanalysis. Il existe pourtant un terme qui surpasse tous les autres. Ceci est une preuve de connaissance zéro - "preuve de connaissance zéro".

Le terme « connaissance zéro » est si séduisant qu’il entraîne des problèmes. Les gens l’utilisent de manière incorrecte, en supposant que zéro connaissance est synonyme "sécurité très, très fiable". Pour cette raison, il est utilisé avec tout ce qui n'a en réalité rien à voir avec les protocoles à connaissance nulle, y compris les systèmes de cryptage et les réseaux d'anonymisation.

J'écris ceci pour souligner que les preuves sans connaissance sont parmi les outils les plus puissants jamais inventés par les cryptographes. Malheureusement, ils sont tout aussi mal compris. Dans cette série d’articles, je vais essayer de décrire clairement ce que sont les preuves de connaissance nulle et ce qui les rend si spéciales. Nous examinerons également certains protocoles à connaissance nulle utilisés dans le monde réel.

Histoire de zéro connaissance

Le concept de « connaissance zéro » a été proposé pour la première fois dans les années 1980 par les chercheurs du MIT Shafi Goldwasser, Silvio Micali et Charles Rackoff. Ils ont étudié les problèmes associés aux systèmes de preuve interactifs – des systèmes théoriques dans lesquels une partie (le « Prouveur ») échange des messages avec une deuxième partie (le « Vérificateur ») essayant de la convaincre de la véracité d'une affirmation mathématique.*

Avant Goldwasser et ses collègues, les travaux dans ce domaine se concentraient principalement sur l'exactitude du système de preuve. En d’autres termes, les scientifiques ont examiné des situations dans lesquelles un démontrant maléfique tentait de « tromper » le vérificateur en lui faisant croire à une fausse déclaration. Goldwasser, Micali et Rekoff ont renversé le problème. Au lieu de s'inquiéter uniquement du Prouveur, ils ont décidé de considérer ce qui se passe si vous ne faites pas confiance À l'inspecteur.

Le problème spécifique qu'ils posaient était fuite d'informations. Les scientifiques se demandent quelle quantité d’informations supplémentaires le vérificateur apprend au cours d’une preuve au-delà du fait que la déclaration est vraie.

Il est important de noter que cela n’a pas été fait uniquement par intérêt théorique : de tels problèmes ont des applications dans le monde réel. Voici un de ces scénarios : imaginez qu'un utilisateur dans le monde réel souhaite se connecter à un serveur Web à l'aide d'un mot de passe. L'approche « réaliste » standard de ce problème consiste à stocker une version hachée du mot de passe sur le serveur. Ainsi, la connexion au serveur peut être considérée comme une sorte de « preuve » que le hachage du mot de passe est le résultat de l'application d'une fonction de hachage à un mot de passe et que le client est en fait sait mot de passe.

Majorité systèmes réels implémentez cette « preuve » de la pire des manières : le client transmet simplement le mot de passe d'origine au serveur, qui calcule un hachage du mot de passe et le compare avec la valeur stockée. L’inconvénient de cette approche est évident : le serveur a appris le mot de passe non crypté du client. Ainsi, l’hygiène moderne des mots de passe repose en grande partie sur l’hypothèse que le serveur n’est pas compromis.

Ce que Goldwasser, Micali et Rekoff ont proposé un espoir renouvelé pour la mise en œuvre de preuves sans connaissance qui ne disent rien aucune informationà l'exception d'un bit qui signifie « cette affirmation est vraie ».

Exemple du « monde réel »

Notre discussion est assez abstraite pour l'instant, alors regardons un exemple « du monde réel » d'un protocole (un peu fou) à connaissance nulle.

Imaginez que je suis un magnat des télécommunications déployant un nouveau réseau cellulaire. La structure de mon réseau est présentée dans la figure ci-dessous. Chaque sommet de ce graphique représente une tour radio et les bords du graphique indiquent les emplacements où les cellules chevaucher, c'est-à-dire là où la réception du signal peut être difficile. Heureusement, pour éviter les interférences, je peux attribuer à chaque tour l'une des trois bandes de fréquences différentes.

Le problème du déploiement du réseau est donc de savoir comment attribuer des bandes de fréquences aux tours afin qu'aucune cellule superposée ne partage la même fréquence. Présentation des gammes de fréquences différentes couleurs, nous pouvons rapidement proposer une des solutions au problème :

Bien sûr, beaucoup d’entre vous ont déjà réalisé qu’il ne s’agit là que d’un exemple du fameux problème théorique de la coloration d’un graphique avec trois couleurs. Ce problème est intéressant car pour certains graphes il est difficile de trouver une solution voire de savoir est-ce que ça existe il. En fait, la tricoloration – plus précisément, découvrir s’il est possible de colorer un graphique particulier avec trois couleurs – appartient à la classe de complexité NP.

Évidemment, notre exemple de jouet est facile à résoudre à la main, mais que se passe-t-il si ce n'est pas le cas ? Imaginez, par exemple, que mon réseau cellulaire soit très vaste et complexe – à tel point que les ressources informatiques dont je dispose sont insuffisantes pour trouver une solution. Dans ce cas, il serait souhaitable externaliser le problèmeà quelqu'un d'autre qui dispose de plus de ressources informatiques. Par exemple, je peux demander à mes amis chez Google de le résoudre pour moi selon les spécifications.

Mais cela pose un problème.

Supposons que Google consacre une partie importante de son infrastructure informatique à trouver un moyen de colorer mon graphique. Bien sûr, je ne les paierai pas tant que je ne saurai pas qu'ils ont réellement trouvé un tel moyen, mais en même temps Heure Google ne me donnera pas de copie de la décision tant que je ne les aurai pas payés. Nous sommes dans une impasse.

Il existe probablement un moyen réel de sortir de cette impasse, notamment en faisant appel à des avocats et en utilisant des comptes séquestres, mais ce n'est pas un blog sur la vraie vie, mais sur la cryptographie. Si vous avez déjà lu des recherches sur la cryptographie, vous comprendrez que la bonne façon de résoudre ce problème est trouver une solution technique absolument folle.

Solution technique folle (avec des chapeaux !)

Notez que je ne serai jamais absolument sûr que Google est honnête – il y aura toujours au moins une infime chance que Google me trompe. Cependant, après un grand nombre d'itérations (à savoir E^2 ) ma confiance augmentera au point où la probabilité que Google soit trompé sera négligeable - assez faible, pour qu'en chacun problèmes pratiques elle pourrait être négligée. De cette façon, je peux donner mon argent à Google en toute sécurité.

Nous devons également savoir que Google est sécurisé. Même si j'essaie d'apprendre quelque chose sur la solution de Google en prenant des notes entre les exécutions du protocole, cela ne devrait pas avoir d'importance. Je suis perplexe face à Google randomise choix des couleurs dans différentes itérations du protocole. Les informations limitées que je reçois sont inutiles et je n'ai aucun moyen cravate données provenant de différentes itérations.

Qu’est-ce qui fait ce « zéro connaissance » ?

J'ai déjà déclaré que ce protocole empêche la fuite de la décision de Google, mais ne me laissez pas m'en tirer aussi facilement ! La première règle de la cryptographie moderne est ne fais jamais confiance aux gens qui font de telles affirmations sans preuve.

Goldwasser, Micali et Rekoff ont proposé trois propriétés que tout protocole à connaissance nulle doit satisfaire. De manière informelle, ils peuvent être exprimés comme suit :

1. exhaustivité (exhaustivité). Si Google dit la vérité, il finira par me convaincre (en au moins, avec une forte probabilité).
2. Exactitude (solidité). Google peut me convaincre de la bonne décision seulement dans ce cas Si dit effectivement la vérité.
3. Zéro connaissance (zéro— connaissance) . Je n'entends plus rien sur la décision de Google.

Nous avons déjà discuté de l’argument de l’exhaustivité. Le protocole est tel qu'après suffisamment d'itérations, Google finira par me convaincre (avec un risque d'erreur négligeable). Démontrer l’exactitude de ce protocole est également assez simple. Si jamais Google essaie de me tromper, je découvrirai presque certainement la trahison.

C’est la troisième propriété qui pose problème ici, mais pour la comprendre, nous devons faire une expérience de pensée très étrange.

Expérience de pensée (avec des machines à voyager dans le temps)

Commençons par une hypothèse folle. Imaginez que les ingénieurs de Google ne soient pas aussi compétents qu'il y paraît. Ils travaillent sur mon problème depuis des semaines et des mois, mais ils ne trouvent pas de solution. Lorsqu’il reste 12 heures avant la vérification, les Googleurs deviennent désespérés. Ils décident tromper moi pour que je pense qu'ils ont une coloration graphique alors qu'en fait ce n'est pas le cas.

Leur idée est d'infiltrer un atelier GoogleX et d'emprunter le prototype de la machine à voyager dans le temps de Google. Ils prévoient initialement de voyager dans le temps de plusieurs années pour utiliser le temps de travail supplémentaire pour résoudre le problème. Malheureusement, comme la plupart des prototypes de Google, la machine à remonter le temps présente certaines limites : elle permet uniquement de voyager dans le temps en quatre minutes et demie.

Ainsi, la possibilité d'utiliser une machine à remonter le temps pour obtenir du temps de travail supplémentaire est éliminée. Cependant, il s’avère que même cette technologie très limitée peut encore être utilisée pour me tromper.

Je n'ai aucune idée de ce qui se passe ici, mais je pensais que l'image convenait.

Le plan est sacrément simple. Parce que Google je ne sais pas vraiment coloration graphique valide, Google colore simplement le papier avec des couleurs aléatoires, puis ramasse les chapeaux. Si par pur hasard nous rencontrons une paire de sommets de couleurs différentes, tout le monde poussera un soupir de soulagement et nous continuerons à suivre le protocole. Jusqu'ici, tout va bien.

Cependant, je vais inévitablement tôt ou tard lever une paire de chapeaux, découvrir deux sommets un couleurs et attraper Google en train de tricher. Et c’est là qu’intervient la machine à voyager dans le temps. Lorsque Google se retrouve dans cette situation étrange, il l’élimine tout simplement. En d'autres termes, un « Googleur » spécial actionne l'interrupteur à bascule, « rembobine » le temps d'environ quatre minutes et l'équipe de Google recolore complètement le graphique avec une nouvelle solution aléatoire. Après cela, ils recommencent le temps, me permettant de réessayer.

Essentiellement, la machine à voyager dans le temps permet à Google de "se remettre" de toute mauvaise chose qui se produit lors de l'exécution de son faux protocole, ce qui me donne l'impression que tout est normal. Étant donné qu'une tentative réussie de contestation du protocole ne se produit que dans environ 1/3 des tentatives, le temps d'exécution attendu du protocole (du point de vue de Google) n'est que modérément plus long que le temps d'exécution du protocole équitable. Quant à moi, je ne soupçonne même pas qu'un voyage dans le temps ait lieu.

Le dernier point est le plus important. En fait, de mon point de vue, ne pas savoir qu'une machine à voyager dans le temps est impliquée conduit à exactement la même interaction que la réalité. Statistiquement, ils sont identiques. Et pourtant, encore une fois, il convient de noter que dans la version avec la machine à voyager dans le temps àGoogle Il n'y a absolument aucune information sur la façon de colorer un graphique.

A quoi ça sert tout ça ?

Ce que nous venons de voir est un exemple simulation. Notez que dans un monde où le temps ne fait qu'avancer et où personne ne peut me tromper avec une machine à remonter le temps, protocole avec des chapeaux correct, c'est-à-dire après E^2 tours, je dois être convaincu (au-delà d'une probabilité négligeable) que le graphique peut effectivement être coloré et que Google a une solution valable.

Nous venons de montrer que si le temps ne s'écoule pas simplement - plus précisément, si Google peut « rembobiner » mon idée du temps - alors Google peut simuler le fonctionnement réel du protocole. même sans informations sur la coloration réelleegraphique.

De mon point de vue, quelle est la différence entre les deux options de protocole ? Si l’on considère leur répartition statistique, il n’y a aucune différence : les deux rapportent à peu près la même quantité d’informations utiles.

Croyez-le ou non, cela prouve quelque chose de très important.

Disons que j'ai (le vérificateur) une stratégie qui "extrait" des informations utiles sur la coloration de Google après avoir observé l'exécution du protocole de la foire. Ensuite, ma stratégie devrait fonctionner tout aussi bien dans les cas où je suis trompé par la machine à voyager dans le temps. De mon point de vue, les exécutions du protocole sont statistiquement identiques – je ne peux physiquement pas faire la différence.

Ainsi, si la quantité d'informations que je peux extraire dans « l'expérience réelle » et dans « l'expérience de machine à voyager dans le temps » est identique, mais que la quantité d'informations fournies par Google dans « l'expérience de machine à voyager dans le temps » est exactement nulle, cela suggère que même dans le Dans le monde réel, le protocole ne devrait produire aucune information utile. Il ne reste plus qu’à montrer que les informaticiens disposent de machines à voyager dans le temps. Oui, nous les avons ! (C'est un secret bien gardé.)

Se débarrasser des chapeaux (et des machines à voyager dans le temps)

Bien sûr, nous ne voulons pas réellement utiliser le protocole Hat et même Google n'a pas de machine temps réel (probablement).

Pour tout relier, nous devons d’abord introduire notre protocole dans le monde numérique. Cela nous oblige à construire l'équivalent numérique d'un « chapeau » - quelque chose qui à la fois cache la signification numérique et pourtant « lie » le créateur à celui-ci (« oblige ») afin qu'il ne puisse pas changer d'avis après coup.

Heureusement, nous disposons de l’outil parfait pour cela, appelé tableau d’engagement numérique. Un système d'engagement permet à une partie de « s'engager » à message spécifique, en le conservant dans une « enveloppe secrète », puis en « ouvrant » plus tard l'enveloppe de promesse de don pour révéler ce qu'il y a à l'intérieur. Les engagements peuvent être créés à partir de divers ingrédients, notamment de (fortes) fonctions de hachage cryptographique.***

Avec un système d’engagement, nous avons tout ce dont nous avons besoin pour exécuter électroniquement un protocole sans connaissance. Le prouveur code d'abord les couleurs des sommets sous la forme d'un ensemble de messages numériques (par exemple, en utilisant les nombres 0, 1, 2), puis génère des obligations numériques pour chacun d'eux. Ces obligations sont transmises au réviseur. Lorsque le Vérificateur conteste une décision pour une arête, le Prouveur publie simplement les valeurs des engagements correspondant aux deux sommets.

Nous avons donc éliminé les chapeaux, mais comment pouvons-nous prouver qu’il s’agit d’un protocole à connaissance nulle ?

Heureusement, nous sommes désormais dans le monde numérique et nous n'avons pas besoin d'une machine à temps réel pour prouver les affirmations concernant ce protocole. L'astuce principale est d'indiquer que le protocole ne fonctionnera pas entre personnes, et entre deux différents programmes informatiques(ou, en termes plus formels, des machines probabilistes de Turing).

Nous pouvons maintenant démontrer le théorème suivant. S'il était possible de créer un programme informatique (pour le vérificateur) ​​qui extrait des informations utiles après avoir participé à une exécution de protocole, une "machine à voyager dans le temps" pourrait être utilisée avec ce programme afin que le programme extraie la même quantité d'informations utiles de un "faux" protocole exécuté alors que le prouveur ne fournit aucune information.

Et puisque nous parlons maintenant de programmes informatiques, évidemment, rembobiner le temps n’est pas du tout une possibilité extraordinaire. En fait, nous rembobinons constamment les programmes informatiques. Prenons, par exemple, un logiciel pour machines virtuelles doté d'une fonction de snapshot.

Un exemple de rembobinage d'instantanés de machines virtuelles. La VM d'origine est lue, rétablie à l'instantané d'origine, puis une autre branche est exécutée.

Même si vous ne disposez pas d'un logiciel de machine virtuelle sophistiqué, n'importe quel programme informatique peut être « rembobiné » à un état antérieur en l'exécutant simplement à nouveau depuis le début et en lui donnant exactement la même entrée. Si l'entrée - y compris tous les nombres aléatoires - est fixe, le programme suivra toujours le même chemin d'exécution. Vous pouvez rembobiner un programme en le démarrant simplement depuis le début et en « bifurquant » son exécution lorsqu'il atteint un point souhaité.

En fin de compte, nous obtenons le théorème suivant. S'il existe un programme informatique Verifier qui réussit à extraire des informations en exécutant ce protocole de manière interactive avec un Prover, nous pouvons simplement utiliser l'astuce du rembobinage pour exprimer un engagement à solution aléatoire, puis « tromper » le testeur en rembobinant le programme jusqu'à ce que nous réussissions le test. La même logique s'applique que ci-dessus : si un tel vérificateur parvenait à extraire des informations après avoir exécuté le protocole lui-même, il pourrait alors extraire la même quantité d'informationsà partir d'un protocole de rembobinage simulé. Mais comme aucune information n’est transmise au protocole simulé, il n’y a rien à extraire. Par conséquent, la quantité d’informations que le vérificateur peut extraire est nulle.

D'accord, alors qu'est-ce que tout cela signifie ?

Ainsi, grâce à l’analyse ci-dessus, nous savons que le protocole est complet et correct. L'argument en faveur de l'exactitude est valable chaque fois que nous savons que personne ne manipule le temps, c'est-à-dire que le programme du vérificateur s'exécute normalement et que personne ne rembobine son exécution.

Dans le même temps, le protocole ne fournit également aucune connaissance. Pour le prouver, nous avons montré que tout programme Verifier qui réussit à extraire des informations doit également être capable d'extraire des informations d'un protocole de rembobinage exécuté lorsque aucune information n’est initialement disponible. Cela conduit à une contradiction évidente et nous indique que la fuite d’informations lors de l’exécution d’un tel protocole est impossible dans les deux situations.

Tout cela présente un avantage important. Étant donné que n'importe qui peut facilement « falsifier » une transcription même après que Google m'a prouvé qu'il a une solution, je ne peux pas relire la transcription pour prouver quoi que ce soit à quelqu'un d'autre (par exemple, un juge). En effet, le juge n'aurait aucune garantie que la vidéo a été enregistrée équitablement et que je n'ai pas édité de la même manière que le système Google pourrait le faire à l'aide d'une machine à voyager dans le temps. Cela signifie que l'entrée du journal elle-même ne contient aucune information. Le protocole n’a de sens que si j’y ai moi-même participé et si je suis sûr qu’il s’est déroulé en temps réel.

Des preuves pour tous les IP !

Si vous avez lu jusqu'ici, je suis sûr que vous êtes prêt à découvrir de grandes nouvelles. À savoir, vous êtes sur le point d’apprendre que les réseaux cellulaires tricolores ne constituent pas un problème si intéressant, du moins pas en eux-mêmes.

Le problème des 3 couleurs est intéressant principalement parce qu’il appartient à la classe des NP-complets. D'un point de vue informel, ce qui est surprenant dans ces problèmes, c'est que tout autre problème de la classe NP peut être converti en une instance de ce problème.

Ce résultat, d'un seul coup - grâce à Goldreich, Micali et Widjerson - prouve qu'il existe des preuves « efficaces » de connaissance nulle pour une large classe d'énoncés utiles, dont beaucoup bien plus intéressant que d’attribuer des fréquences aux réseaux cellulaires. Vous trouvez simplement l'instruction (dans la classe NP) que vous souhaitez prouver, comme notre exemple de fonction de hachage ci-dessus, puis la convertissez en une instance du problème des 3 couleurs. Après cela, vous exécutez simplement la version numérique du protocole avec des chapeaux.

Résumons-le

Bien sûr, exécuter ce protocole pour des déclarations intéressantes serait très étrange et stupide, car cela nécessiterait une énorme quantité de travail. En théorie, cela est « efficace » car le coût total de la preuve augmenterait de manière polynomiale avec la taille des données d'entrée, mais en pratique, ce serait complètement différent.

Ainsi, nous avons seulement montré jusqu’ici que de telles preuves possible. La recherche de preuves suffisamment pratiques pour être utilisées dans le monde réel nous appartient.

Dans d'autres articles, je parlerai de certains d'entre eux, à savoir efficace preuves de diverses déclarations utiles. Je vais donner quelques exemples (tirés d'applications réelles) où de telles techniques ont été utilisées. Aussi, à la demande d'un des lecteurs, je vais vous expliquer pourquoi je n'aime pas tellement le protocole SRP (Secure Remote Password).

Remarques

* Formellement, le but d'une preuve interactive est de convaincre le vérificateur qu'une chaîne particulière appartient à un langage. Généralement, le Prover est très (illimité) puissant et le Verifier est limité en ressources informatiques.

** Cet exemple est basé sur la solution originale de Goldwasser, Micali et Rekoff, et l'exemple du didacticiel avec des chapeaux est basé sur l'explication donnée par Silvio Micali. Je suis uniquement responsable des erreurs, le cas échéant.

*** Un exemple simple d'engagement peut être construit à l'aide d'une fonction de hachage. Pour créer un engagement pour la valeur "x", générez simplement une chaîne (suffisamment longue) de nombres aléatoires, que nous appellerons "sel", et imprimez l'engagement. C = Hacher(sel || x) . Pour rendre public un engagement, il vous suffit d'afficher un « x » et un sel. N'importe qui peut vérifier que l'engagement initial est valide en recalculant le hachage. Il est sûr tant que certaines exigences (modérément strictes) concernant la fonction elle-même sont remplies.

Matthieu Vert

Preuve de connaissance nulle) est un protocole interactif qui permet à l'une des parties (le vérificateur) de vérifier la fiabilité d'une déclaration (généralement mathématique), sans recevoir aucune autre information de l'autre partie (le prouveur).

Une preuve sans connaissance doit avoir trois propriétés :

1. exhaustivité: si la déclaration est vraiment vraie, alors le prouveur en convaincra le vérificateur.
2. Exactitude: Si la déclaration est fausse, alors même un prouveur malhonnête ne sera pas en mesure de convaincre le vérificateur sauf avec une probabilité négligeable.
3. Zéro connaissance: si la déclaration est vraie, alors tout vérificateur, même malhonnête, ne saura rien d'autre que le fait même que la déclaration est vraie.

Structure générale des preuves à connaissance nulle

Chaque cycle ou accréditation de preuves consiste en trois étapes. Ils peuvent être schématiquement représentés comme suit :

D'abord UN sélectionne dans un ensemble prédéterminé un élément qui devient son secret (clé privée). A partir de cet élément, une clé publique est calculée puis publiée. Connaître un secret détermine de nombreuses questions auxquelles UN sera toujours en mesure de donner les bonnes réponses. Alors UN sélectionne un élément aléatoire dans l'ensemble, selon certaines règles(en fonction de l'algorithme spécifique) calcule preuve puis le renvoie B. Après cela B en choisit une parmi l'ensemble des questions et demande UN réponds-y ( appel). Selon la question, UN envoie Réponse B. Informations reçues B suffisant pour vérifier si UN possède le secret. Les tours peuvent être répétés autant de fois que nécessaire jusqu'à ce que la probabilité que UN Les réponses « deviner » ne seront pas assez basses.

Cette technique est également appelée « couper et choisir ».

Exemple

Appelons le côté vérificateur Petya, et le côté prouvant Dima (dans la littérature anglophone, les paires Peggy (de prouveur) et Victor (de vérificateur). Supposons que Dima connaisse un cycle hamiltonien dans un grand graphique G. Petya connaît le comte G, mais il n'y connaît pas le cycle hamiltonien. Dima veut prouver à Petya qu'il connaît le cycle hamiltonien, sans divulguer ni le cycle lui-même ni aucune information à son sujet (peut-être que Petya veut acheter ce cycle hamiltonien à Dima, mais avant cela, assurez-vous que Dima l'a vraiment).

Pour ce faire, Petya et Dima effectuent conjointement plusieurs tours du protocole :

À chaque tour, Petya choisit un nouveau bit aléatoire, inconnu de Dima, donc pour que Dima réponde aux deux questions, il faut que Hétait bien isomorphe G et Dima devrait connaître le cycle hamiltonien dans H(et donc aussi dans G). Par conséquent, après un nombre suffisant de tours, Petya peut être sûr que Dima a réellement un cycle hamiltonien dans G. En revanche, Dima ne révèle aucune information sur le cycle hamiltonien dans G. De plus, il sera difficile pour Petya de prouver à quelqu'un d'autre que lui ou Dima connaissent le cycle hamiltonien dans G.

Supposons que Dima n'ait pas de cycle hamiltonien dans G et il veut tromper Petya. Alors Dima a besoin d'un non isomorphe G graphique G", dans lequel il connaît encore le cycle hamiltonien. À chaque tour, il peut passer à Petya soit H"- isomorphe G", ou H- isomorphe G. Si Petya demande à prouver l'isomorphisme et a été réussi H, alors la tromperie ne sera pas révélée. De même, s’il demande à montrer un cycle hamiltonien et qu’on lui donne H". Dans ce cas, la probabilité que Dima trompe encore Petya après n tours est égal à 1/2 n, qui peut être inférieur à toute valeur prédéterminée étant donné un nombre de tours suffisant.

Supposons que Petya ne reconnaisse pas le cycle hamiltonien, mais veuille prouver à Vasya que Dima le connaît. Si Petya, par exemple, a filmé toutes les étapes du protocole, il est peu probable que Vasya le croie. Vasya peut supposer que Petya et Dima sont de mèche et à chaque tour Petya a informé Dima à l'avance de son choix d'un morceau aléatoire afin que Dima puisse lui transmettre H pour les contrôles d'isomorphisme et H" pour vérifier le cycle hamiltonien. Ainsi, sans la participation de Dima, on ne peut prouver qu’il connaît le cycle hamiltonien qu’en prouvant que des bits véritablement aléatoires ont été choisis à tous les tours du protocole.

Abus

Plusieurs manières d’abuser de la preuve de connaissance nulle ont été proposées :

Voir aussi

• Protocole Gillu-Kiskatra

Littérature

• A. Menezes, P. van Oorschot, S. Vanstone. Manuel de cryptographie appliquée. - Presses CRC, 1996. - 816 p. -ISBN0-8493-8523-7
• Schneier B. Cryptographie appliquée. Protocoles, algorithmes, textes sources en langage C = Cryptographie Appliquée. Protocoles, Algorithmes et Code Source en C.-M. : Triumph, 2002. - 816 p. - 3000 exemplaires.

-ISBN5-89392-055-4

• Fondation Wikimédia.
• 2010.

Fonvizina, Natalia Dmitrievna

Tchoujoumovo Voyez ce qu’est « Zero Knowledge Proof » dans d’autres dictionnaires :

preuve de connaissance nulle d'informations confidentielles- Preuve impénétrable de connaissance; preuve de possession de toute information, sans divulguer cette information. Sujets : protection des informations EN preuve de connaissance zéro…

preuve itérative sans connaissance d'informations sensibles- — Thèmes sécurité de l'information EN zéro connaissance preuve itérativeZKIP … Sujets : protection des informations EN preuve de connaissance zéro…

Guide du traducteur technique preuve non itérative et sans connaissance d'informations sensibles

- NDNR - [] Sujets protection de l'information Synonymes NDNR EN non itératif zéro connaissance preuveNIZK ...- Cette page est une liste d'informations. Article principal : Algorithme Vous trouverez ci-dessous une liste d'algorithmes regroupés par catégorie. Des informations plus détaillées sont données dans la liste des structures de données et ... Wikipedia

Cryptographe- Machine de cryptographie allemande Lorenz, utilisée pendant la Seconde Guerre mondiale pour chiffrer les messages les plus secrets. Cryptographie (du grec κρυπτός caché et γράφω écrire) la science de méthodes mathématiques assurer la confidentialité... ... Wikipédia

Algorithmes programmables- Une liste de services d'articles créés pour coordonner les travaux sur le développement du sujet. Cet avertissement n'est pas défini... Wikipédia

PDS- Secure Remote Password Protocol (SRPP) est un protocole d'authentification par mot de passe résistant aux écoutes clandestines et Attaque MITM et ne nécessitant pas un tiers partie de confiance. SRP contient certains éléments d'autres protocoles d'échange de clés et d'identification... Wikipédia

Protocole Fiat- Le protocole Fiat Shamir est l'un des protocoles d'identification à connaissance nulle les plus connus (Zero knowledge protocol). Le protocole a été proposé par Amos Fiat et Adi Shamir Let A... ... Wikipédia.

Protocole Fiat-Shamir- Le protocole Fiat Shamir est l'un des protocoles d'identification à connaissance nulle les plus connus (Zero knowledge protocol). Le protocole a été proposé par Amos Fiat et Adi Shamir. Faites-le savoir... ... Wikipédia.

L'une des tâches principales de la cryptographie est bidirectionnelle jeu interactif, dans lequel un participant (la partie qui prouve) prouve à un autre participant (la partie qui vérifie) la véracité de la déclaration sans révéler l'essence de la preuve. Dans ce cas, le vérificateur ne peut pas évaluer de manière indépendante la véracité de la déclaration, puisqu'il ne connaît pas les informations dont dispose le prouveur. Ce jeu est appelé protocole de preuve interactif (système) ou protocole IP (preuve interactive - IP). La preuve réalisée par le protocole IP peut être qualifiée de « preuve secrète » (« preuve dans le noir »). Le secret de cette preuve réside dans le fait que, d'une part, la partie vérificatrice, étant convaincue de la véracité de la déclaration à prouver, n'est pas en mesure de répéter la preuve de manière indépendante et, d'autre part, après l'achèvement du protocole, aucun des étrangers sont capables de comprendre un seul message échangé entre la partie qui prouve et la partie qui examine.
Imaginons que l'énoncé qui doit être prouvé, sans révéler l'essence de la preuve, soit la solution à un célèbre problème mathématique non résolu. Dans ce cas, le prouveur, qui craint le plagiat, souhaitera peut-être cacher les détails techniques de la preuve à un critique potentiellement malhonnête. Pour ce faire, elle doit procéder à une preuve « secrète », convaincant le réviseur (qui joue le rôle de partie utilisatrice dans le protocole IP) de la justesse des conclusions, sans donner aucune information supplémentaire.
Dans beaucoup applications réelles il existe des raisons bien plus sérieuses de procéder à des preuves « secrètes ». Généralement, les protocoles IP sont utilisés pour authentifier les entités. Contrairement aux protocoles d'authentification conventionnels, dans lesquels les utilisateurs mettent signatures numériques Dans le protocole IP, le prouveur à authentifier ne souhaite pas que les messages soient accessibles à quiconque autre que la partie utilisatrice et effectue une authentification « secrète ». De plus, les protocoles IP sont souvent utilisés pour prouver qu'une partie informations cachées a une certaine structure. Ceci est nécessaire dans certains applications secrètes(par exemple, lors de la conduite d'enchères électroniques), dans lesquelles numéro caché(lot) doit se situer dans la fourchette acceptable (par exemple, il faut prouver que x > y sans divulguer les valeurs de et , qui représentent les offres).
Lorsque l’on considère les protocoles IP, deux problèmes doivent être pris en compte.

• Question 1. Quelle quantité d'informations le vérificateur recevra-t-il lors de la preuve interactive ?
• Question 2 : Combien de tours le prouveur doit-il effectuer pour convaincre le vérificateur ?

La réponse idéale à la première question serait « pas du tout » ou « zéro ». Protocole IP, qui possède cette propriété, est appelé protocole à connaissance nulle ou protocole ZK (zéro-connaissance - ZK). La deuxième question est importante non seulement pour les applications pratiques, mais aussi pour la théorie de la complexité computationnelle, puisque la résolution de ce problème implique d’obtenir une estimation de complexité moindre.

Histoire du développement

La preuve à connaissance nulle a été inventée et développée par les scientifiques suivants : Shafi Goldwasser, Silvio Mikali et Charles Reckoff, et publiée par eux dans l'article « Connaissance et complexité d'un système de preuve interactif » en 1985. Ce travail a présenté une hiérarchie de systèmes de preuve interactifs basée sur la quantité d'informations de preuve qui doivent être transférées du prouveur au vérificateur. Ils ont également proposé la première preuve d'une preuve de connaissance nulle spécifiquement formulée - le résidu quadratique modulo m. Développant ensuite leur travail, ils remportèrent le premier prix Gödel en 1993.
Continuation...

Zéro connaissance

Modèle informatique

Notons le modèle de base du protocole de preuve interactive par (P,V), où P est le prouveur et V est le vérificateur. En règle générale, le protocole (P,V) est conçu pour vérifier qu'une certaine phrase appartient à une langue spécifiée par l'alphabet (0,1)*.
Soit L une langue sur l'alphabet (0,1)*. Les côtés P et V reçoivent un échantillon xϵL, qui est l'entrée commune. La preuve de propriété de l’échantillon est notée (P, V)(x). Les deux parties du protocole sont reliées par un canal de communication par lequel ils échangent des informations.
Le résultat du protocole est enregistré dans le formulaire suivant: (P,V)(x) ϵ (Accepter, Rejeter).
Ces deux valeurs signifient que le vérificateur confirme ou réfute l'assertion xϵL faite par le prouveur P. Puisque le système (P,V) est probabiliste, pour chaque x le résultat (P,V)(x) est une variable aléatoire en fonction des données d'entrée générales x, des données d'entrée privées (entrée privée) de l'utilisateur P et de certaines données d'entrée aléatoires (entrée aléatoire) communes aux utilisateurs P et Q.
Puisque le protocole (P, V) est un jeu à deux faces, il est naturel de supposer que chaque camp cherche à obtenir un avantage supplémentaire. D'une part, le prouveur P doit être intéressé par le résultat de l'acceptation de x, même s'il n'appartient pas à L. Un prouveur poursuivant une telle stratégie de prouveur tricheur est noté P'. D'un autre côté, le vérificateur V doit être intéressé à divulguer des informations sur les données d'entrée privées du joueur P. Le vérificateur qui suit un tel vérificateur malhonnête est noté V'.
Supposons qu'il existe une réponse idéale à la question 1 (P, V) - un protocole à connaissance nulle, c'est-à-dire l'utilisateur V (ou V') vérifie l'exactitude de l'assertion de l'utilisateur P sans rien apprendre de nouveau sur sa contribution privée.
Pour que le protocole (P,V) ait cette propriété, il est nécessaire de limiter la puissance de calcul V (ou V') de l'utilisateur à un polynôme dépendant de la taille de ses informations d'entrée. Évidemment, sans cette restriction, la connaissance nulle ne peut être garantie, puisque l'utilisateur V, qui dispose de ressources informatiques illimitées, peut révéler indépendamment les données secrètes d'entrée de l'utilisateur R.

Définition formelle des protocoles de preuve interactive

Définissons le protocole de preuve interactive. Soit L une langue définie sur l'alphabet (0,1)*. Un protocole IP (P,V) est appelé système de preuve interactif pour le langage L si

Et

où les nombres Ɛ et ϐ sont des constantes satisfaisant les conditions Ɛϵ(1/2;1], ϐϵ)