Loading
Notes d'étude
Study Reminders
Support
Text Version

Zéro-Protocoles de gestion des connaissances

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bengaluru Lecture – 57 Zero Knowledge Protocols Part I (voir Diapositive Time: 00:30) Bienvenue à cette conférence. Ainsi, lors de cette conférence, nous poursuivrons notre discussion sur les protocoles interactifs où nous voulions résoudre un problème plus important plutôt que le problème de la communication sécurisée. Ainsi, lors de cette conférence, nous allons introduire des protocoles de Zero-knowledge. Nous verrons une partie de la motivation d'abord dans les protocoles de connaissance zéro et une définition formelle. Et nous allons voir un protocole de connaissance zéro pour le problème de l'isomorphisme du graphe. (Référez-vous à l'heure de la diapositive: 00:52)Maintenant, commençons par essayer de comprendre une motivation pour les preuves de zéro-connaissances. Alors imaginez que nous avons deux parties Alice et Bob et qu'Alice a choisi deux nombres premiers aléatoires p et q disent chacun de la taille de 512 bits et qu'elle a calculé le produit de p et q pour obtenir le produit N et elle va demander à Bob que je connais les facteurs premiers de N. Maintenant si elle veut prouver à Bob qu'elle sait que les facteurs principaux de N alors une façon simple de prouver que c'est montrer les valeurs de p et q. Parce que si les valeurs de p et q sont données à Bob, Bob lui-même peut multiplier ces deux nombres et voir si ses correspondances N ou non. Mais c'est ce que nous appelons la preuve en clair. Parce que p et q sont ici le témoin d'Alice pour la déclaration qu'elle connaît les principaux facteurs de N. Une façon de prouver sa déclaration est de montrer les témoins en clair, mais ce qu'un protocole de connaissance zéro va faire ici, c'est qu'elle va permettre à Alice de convaincre Bob qu'elle connaît bien les principaux facteurs de N sans réellement montrer les témoins, à savoir p, q. Parce que p et virgule q pourraient venir des informations secrètes pour Alice et dans tout ce processus de preuve de la connaissance de zéro, fondamentalement Alice finit par convaincre Bob qu'elle sait p et q sans vraiment révéler p et q. Vous vous demandez peut-être où ce p et q est utile. Donc, si vous vous souvenez dans le contexte du cryptosystème à clé publique RSA, la valeur N n'est rien d'autre qu'une partie de la clé publique d'Alice et de p, q ne sont qu'une partie d'une clé de déchiffrement. Donc, si vraiment Alice veut convaincre Bob que N est sa clé publique et qu'elle connaît la clé secrète correspondante sans montrer les composants liés à la clé secrète, à savoir p et q ; elle nous pouvons faciliter Alice en utilisant cette preuve de zéro connaissance. (Voir Heure de la diapositive: 02:45) Voyons une autre motivation. Imaginez Alice a deux graphiques ici. Et de façon picturale, ces deux graphiques sont tracés d'une manière différente. Les noms de vertex sont différents ; les noms de bord sont différents, alors ainsi de suite. Mais il s'avère que les informations sages les deux graphiques sont isomorphes ou structuralement les graphes sont isomorphes l'un à l'autre et ce que je veux dire par les graphes isomorphes ici est que, si vous considérez ces deux graphiques, alors pour ces deux graphiques il existe une bijection de l'ensemble de vertex du premier graphe à l'ensemble de sommets du second graphe. Et cette bijection a la propriété que s'il y a un bord entre les noeuds u et v dans le premier graphe puis dans le second graphe il existe une arête entre l'ensemble de u mappé et le jeu de v mappé. Et c'est un si et seulement si une déclaration. Cela signifie de la même façon que si vous avez une arête entre le sommet u mappé et le vertex mappé dans le second graphe, alors un bord existe entre le vertex u et le vertex v dans le premier graphe. Donc, en ce sens, ces deux graphiques sont isomorphes même si pictoriellement ils sont différents. Alors imaginez Alice a deux graphes isomorphes, donc elle fait la description des deux graphiques disponibles à Bob et elle fait la déclaration qu'elle prétend à Bob que ces deux graphes sont isomorphes. C'est donc la déclaration. Encore une fois, Bob ne peut pas vérifier directement si les deux graphiques sont isomorphes ou non et vérifier la revendication Alice parce qu'il n'est pas pratique de vérifier si deux graphes sont isomorphes ou non en l'absence de la bijection qui est disponible ou qui mappe le jeu de sommets du premier graphe à l'ensemble de sommets du second graphe. Donc une façon pour Bob de vérifier la déclaration d'Alice est qu'elle peut demander à Alice de me donner votre témoin, à savoir la bijection de Π. Si vous me donnez la bijection Π, alors je peux vérifier si, en effet, pour chaque arête du graphe, le premier graphe les sommets mappés correspondants constituent également un bord dans le second graphe, et ainsi de suite. Mais cela sera une preuve claire. Donc, ce qu'une preuve de la connaissance de zéro ou un protocole de connaissance zéro permettra à Alice de faire est, elle permettra à Alice de convaincre Bob que ces deux graphiques sont isomorphes sans en fait montrer le témoin, à savoir la bijection Π. (Référez-vous à l'heure de la diapositive: 05:10) Donc, cela signifie qu'une preuve de la connaissance zéro est une sorte de protocole interactif entre deux entités, un étalon et un vérificateur qui permet à un étalon de prouver une déclaration pour vérifier sans rien montrer au sujet du témoin sous-jacent. Alors, formalisons maintenant cette déclaration. Alors imaginez R est une relation binaire et l'interprétation de cette relation est la suivante. Donc si j'ai une paire (x, w) présente dans cette relation R qui doit être interprété comme si x est une instance de quelques problèmes de calcul. Lorsque je dis que le problème informatique est difficile de manière informelle, cela signifie en poly temps qu'on ne sait pas comment résoudre ce problème. Mais là encore, c'est une déclaration très lâche, mais c'est une compréhension intuitive du problème informatique difficile ici et un w ici est une solution pour cette instance de problème x, à savoir que vous pouvez considérer le w comme un témoin de l'instance de problème x. Pour comprendre cette relation R, considérons l'isomorphisme du graphique ici. Ainsi, une paire (x, w) dans la relation isomorphe graphique RGI ressemblera à ceci { (G1 = (V1, E1), (G2 = (V2, E2)) } et l'interprétation des éléments présents dans cette relation isomorphisme du graphe doit être la suivante. La première partie est donc la description des deux graphiques, à savoir qu'il s'agit d'une instance de problème. Cela signifie que quelqu'un veut prouver ou réfute que ces deux graphiques sont isomorphes. Et le témoin correspondant n'est rien d'autre que l'isomorphe ou la bijection de l'ensemble de vertex du premier graphe à l'ensemble de sommets du second graphe. Par exemple, si vous considérez ces deux graphiques ici, ces deux graphiques sont effectivement isomorphes. Le premier graphique est le graphique G1 et le deuxième graphique est le graphique G2. Donc c'est la composante x de l'un des x, w qui pourrait être présent dans cette relation isomorphisme du graphe. Et un témoin correspondant en ce qui concerne ce graphique G1 G2 spécifique n'est rien d'autre que la bijection de l'ensemble de vertex du graphe G1 vers le sommet du graphique G2 et ainsi de suite. (Référez-vous à la diapositive: 07:18)Par contre, si je considère que ces deux graphiques sont mon G1 et G2, il s'avère que ces deux graphiques ne sont pas isomorphes l'un à l'autre et que, par conséquent, si c'est mon candidat x alors pour ce candidat x je n'ai pas de candidat w tel que x, w appartient à cette relation RGI, non. Cela signifie seulement que x, w sera présent à r où l'instance x a un témoin correspondant w. Si pour une instance x il n'existe aucun témoin w de telle sorte que x, w satisfait cette relation alors nous disons que, (x, w) n'est pas présent dans la relation R. (Référer le temps de la diapositive: 07:57) Donc, allons maintenant dans la définition formelle des preuves de "zéro connaissance". On nous donne donc une relation connue publiquement qui aura des éléments du formulaire x, w où x est une instance de quelques problèmes de calcul difficile et w est la solution ou le témoin pour cette instance. Ensuite, un système de preuve zéro pour la relation R est constitué de deux algorithmes de poly time deux algorithmes aléatoires un pour le tube étalon et l'autre pour le vérificateur. L'entrée pour le tube étalon sera une paire x, w et l'objectif du prover est de prouver qu'il connaît une w telle que x, w appartient à r alors que l'entrée pour l'algorithme du vérificateur sera l'instance de problème x. Et le but du vérificateur est de vérifier si, en effet, Alice connaît une w telle que x, w appartient à R ou non. Ainsi, dans le système de preuve zéro connaissance, le prover enverra des messages ou il interagira avec le vérificateur dans lequel les messages pour le tube étalon seront calculés selon le protocole P et le caractère aléatoire interne qui sont utilisés par le prover. Et à la fin du protocole, le prover ne produit rien alors que l'algorithme du vérificateur sera en interaction avec le prover où les messages du vérificateur seront calculés selon l'algorithme V et le caractère aléatoire interne choisi par le vérificateur et que le vérificateur va soit accepter ou rejeter la sortie. Accepter signifie qu'il accepte le fait qu'Alice connaît un certain témoin, le rejet signifie qu'il ne croit pas dans la déclaration d'Alice. Maintenant, quelles sont les propriétés dont nous avons besoin à partir d'un système de preuve de la connaissance zéro, la première propriété est la propriété de complétude qui exige que si le prover et le vérificateur sont honnêtes et s'ils connaissent un x, w de telle sorte que x, w appartient à R et que le prover et le vérificateur participent, exécute toutes leurs actions selon le protocole P et V. Ensuite, avec une probabilité très élevée, la sortie du vérificateur doit être acceptée. Cela signifie que le vérificateur doit accepter l'énoncé de l'étalon. La deuxième propriété est la propriété de Soundness que nous considérons à l'égard d'un ver corrompu. Donc ce que nous avons besoin ici, c'est que si mon prover est corrompu et qu'il n'a pas de x, w de telle sorte que x, w appartient à la relation R, alors quel que soit le protocole, la sortie du vérificateur doit être rejetée. Cela signifie un prover malveillant qui n'a pas x, w ou qui n'a pas de témoin tel que x, w appartient à la relation R avec beaucoup moins de probabilité que le prover puisse convaincre le vérificateur qu'elle connaît le témoin w. Cela signifie qu'avec une probabilité très élevée, le vérificateur devrait pouvoir attraper un ver malveillant. C'est là l'exigence de la solidité. (Référez-vous à l'heure de la diapositive: 10:50)Et la troisième propriété est une propriété de savoir zéro, à l'égard d'un vérificateur corrompu et d'un étalon honnête. Donc, la propriété de la connaissance zéro exige que si le ver est honnête et que le vérificateur est corrompu, quelle que soit la façon dont l'algorithme du vérificateur ou le vérificateur participe à ce protocole, le vérificateur n'apprend absolument rien du témoin w qui est disponible avec le tube étalon. Donc, ici, rien n'est en cours, je ne cite pas “ rien de ”. Ce n'est pas formel. Ce que nous voulons dire exactement par rien n'est appris sur le témoin. Si vous voulez un peu plus de forme nous pouvons dire cela, nous disons que le protocole a la propriété de la connaissance zéro si la distribution de probabilité des transcriptions vues par le vérificateur est indépendante du témoin réel qui est disponible avec le tube étalon. Encore une fois, je ne prouve pas formellement ce qu'il signifie exactement pour dire que la distribution de la probabilité des transcriptions vu par le vérificateur est indépendante de w. Le formalisme réel est un peu subtil et impliqué. N'allons donc pas entrer dans le détail réel, mais pour votre compréhension, vous pouvez imaginer que le vérificateur ne devrait rien apprendre du témoin si le vérificateur est corrompu en participant à ce protocole. (Référez-vous à l'heure de la diapositive: 12:06)Nous allons donc maintenant voir un système de preuve de connaissance zéro pour un problème d'isomorphisme de graphe. Donc l'entrée commune qui est disponible à la fois pour le ver et pour le vérificateur est une instance d'un problème d'isomorphisme de graphe, à savoir la description de deux graphes. Et Alice veut convaincre Bob ou le vérificateur d'ici la cuve ; la Alice est en prover et le Bob est vérificateur. Donc Alice veut prouver à Bob que ces deux graphes sont isomorphes. Et elle prétend qu'elle connaît l'isomorphisme entre ces deux graphes, ce qui signifie qu'elle prétend avoir une entrée privée qui cartographie le sommet du premier graphe au sommet du deuxième graphe par rapport auquel ces deux graphiques sont isomorphes et l'objectif ici est de concevoir un protocole qui permet à Bob d'apprendre si ces deux graphes sont effectivement isomorphes ou non sans vraiment apprendre l'isomorphisme. Et il devrait être sain dans le sens que si le ver ne sait pas que l'isomorphisme ou les graphes ne sont pas isomorphes au premier endroit, alors elle devrait être attrapée tout en donnant la preuve avec une très forte probabilité. (Référez-vous à l'heure de la diapositive: 13:07)Donc, voyons comment exactement le protocole zéro-connaissance est conçu ici. Donc ce rectangle j'ai mis en évidence les informations publiques de sorte que les informations publiques disponibles à la fois à Alice et à Bob sont la description des deux graphiques. Et les informations privées disponibles avec Alice, le prover est le témoin Π ou le mappage du sommet du premier graphe à l'ensemble de sommets du second graphe. Le premier cycle du protocole de la connaissance zéro est donc le suivant. Donc ce qu'Alice fait est, elle crée une copie isomorphe aléatoire du second graphe G2. Et c'est très facile à faire, ce qu'elle a à faire, c'est qu'elle doit essentiellement trouver une permutation aléatoire dire que σ cartographie le jeu de sommets du second graphe et que les sommets mappés résultants vont lui donner un autre graphe H. Donc une fois qu'elle calcule une copie isomorphe aléatoire du second graphe, elle envoie la description de la copie isomorphe aléatoire du second graphe à Bob. C'est donc une sorte d'engagement. Donc je souligne que σ est choisi au hasard et n'est connu qu'à Alice ici. Maintenant ce que Bob fait, Bob choisit une pièce aléatoire et avec probablement 1/2 la pièce aléatoire pourrait donner la sortie 1 ou avec la probabilité 1/2 qu'elle pourrait donner la sortie 2. Et maintenant ce que Bob ’ défie, Bob remet Alice à Alice pour montrer un isomorphisme entre le graphe et le nouveau graphe H qu'Alice a commis. Donc si i = 1 alors, en gros, Bob défie Alice de montrer un isomorphisme entre le graphe G1 et le nouveau graphe H alors que si i = 2, alors Bob défie Alice de montrer un isomorphisme entre le graphe G2 et le nouveau graphe H. Je souligne ici que quand Alice a commis le graphe H, elle ne sait pas bien à l'avance si elle sera mise au défi de montrer un isomorphisme entre G1 et H ou entre G2 et H. Elle ne le sait pas à l'avance. D'ici le point de vue de la probabilité 1/2, elle pourrait être mise au défi de montrer un isomorphisme entre G1 et H et avec la probabilité 1/2 qu'elle pourrait être mise au défi de montrer un isomorphisme entre G2 et H. Now une fois que Bob lance le défi Alice a à répondre. Et la réponse sera différente selon que i = 1 ou si i = 2 Si le défi est i = 2, c'est-à-dire si Alice est mise au défi de montrer l'isomorphisme entre G2 et H, alors elle peut simplement fournir le σ bijection qu'elle a utilisé pour calculer H à partir du graphique G2 graphique. Donc, ce sera sa réponse. Donc je détiens la réponse de ρ ici. So ρ will be ; the response ρ will be nothing but the mapping σ if i = 2. On the other hand, if Bob has contestée Alice to show an isomorphism between graph G1 and H, then Alice can riposte back by composing the mapping Π which was her témoigné with the secret mapping σ that he has choisit to go from the graph G2 and σ then by using Π and σ then by using Π from G1 we come to G2, Alice comes from G1 to G2 and then composing again with the mapping σ from G2 she can go to the graph H. So that means the way to go from G1 to H is to compose the mapping Π with the mapping σ. Et si en effet Alice connaît Π elle doit pouvoir composer Π et σ et elle peut répondre avec cette réponse ρ. Maintenant, Bob doit vérifier si Alice a bien répondu ou non. Alors ce que Bob vérifie est qu'il sait qu'Alice est supposé montrer un isomorphisme entre le graphe et H et que la réponse d'Alice est le mappage ρ et Bob a juste à vérifier si le graphe Gi emmène Bob au graphe H en fonction de ce mappage ρ ou pas. Si c'est alors Bob est convaincu qu'Alice a réussi ce tour sinon Bob dit qu'Alice a échoué dans ce round. Et ce que Bob va faire c'est que Bob va répéter tout ce processus, c'est-à-dire Alice commettant quelque chose de Bob un défi et Alice soumettez à nouveau la réponse k nombre de fois et pour chacun de ces tours Alice doit choisir l'engagement aléatoire H ce qui veut dire qu'elle choisira fraîchement le graphe H pour chaque tour ou chaque itération et de la même façon que Bob choisira de façon aléatoire les défis i pour chaque round, indépendamment de chaque round précédent. Cela signifie que ce ne sera pas le cas dans chaque round Bob va choisir i = 1 ou i = 2. Et le vérificateur Bob va en sortie 1, c'est-à-dire qu'il dira qu'Alice connaît bien le mappage secret Π, si tous les cycles sont réussis du point de vue de Bob, cela signifie que dans toutes les rondes Alice a réussi à soumettre les réponses ρ. Alors que si l'un des tours Alice échoue, les résultats de Bob sont rejetés. Cela signifie que Bob rejette la prétention d'Alice. C'est le protocole de connaissance zéro ici pour le problème de l'isomorphisme du graphe. (Référez-vous à la diapositive: 18:47) Maintenant, faisons l'analyse, voyons si ce protocole d'isomorphisme de graphe répond aux exigences de l'exactitude, de la solidité et de la connaissance nulle, de l'exhaustivité, de la solidité ou de la connaissance nulle. Donc la propriété de complétude ou la propriété correcte ici est simple, si effectivement Alice est honnête, cela signifie qu'elle connaît le mappage secret Π entre le graphe G1 et G2 et si elle suit les instructions du protocole honnêtement et si le vérificateur est aussi honnête, chacune des rondes sera un succès. Parce qu'il ne sait pas si Bob a des défis avec i = 1 ou avec i = 2. Alice sera toujours capable de répondre avec le bon mappage ρ et donc tous les tours seront couronnés de succès. (Reportez-vous à la section Heure de la diapositive: 19:30) Maintenant, analysons la propriété de solidité ici et rappelons-le pour la propriété solidité dont nous devons tenir compte lorsqu'Alice est potentiellement corrompue. Et elle ne connaît pas le mappage entre G1 et G2 ou à la première place il n'y a peut-être pas de mappage entre G1 et G2 montrant qu'ils sont isomorphes et donc puisqu'elle est corrompue, elle pourrait ne pas suivre le protocole, et se rappeler comme par le protocole qu'elle est censée envoyer une copie isomorphe de G2 dans chaque round, mais elle ne le fait pas aussi bien. Donc, pour la solidité, nous devons analyser cela avec la probabilité qu'elle puisse triché avec succès même si elle ne suit pas le protocole et qu'elle n'a pas l'isomorphisme entre le graphe G1 et G2 disponible avec elle. Il s'avère que la seule façon pour elle de trichiner dans un tour est de deviner à l'avance ce qui sera le défi de l'honnête Bob. Parce que si elle peut deviner correctement à l'avance si i = 1 ou si i = 2 puis à la première place elle-même elle peut créer une copie isomorphe de Gi. Il faut donc rappeler que, selon les étapes du protocole, elle est censée créer une copie isomorphe de G2, à savoir H doit être une copie isomorphe de G2. Mais si Alice est corrompue, elle peut ne pas être capable de suivre le protocole, elle peut essayer de deviner à l'avance que je pourrais être 1, je pourrais être 2 et avec le respect de deviner qu'elle peut créer une isomorphie de ce graphe Gi. Et si, en effet, sa supposition est correcte, elle pourra soumettre la réponse ρ. Mais la probabilité qu'elle puisse deviner correctement si i va être 1 ou si je vais être 2 est 1/2. Cela signifie qu'avec une seule probabilité, elle peut tromper en un tour et finir avec succès cette ronde. Mais puisque nous répétons ce processus k nombre de fois, car souvenez-vous que Bob n'est pas convaincu simplement en faisant ce protocole une seule fois ; en fonction de la confiance qu'il veut être dans la revendication d'Alice, il peut répéter le protocole k nombre de fois. Donc, quelle est la probabilité que dans chacune des itérations k une mauvaise Alice qui ne connaît pas l'isomorphisme entre G1 et G2 se termine avec succès tous les tours k. La probabilité qu'elle soit réussie au premier tour est de 1/2 ; la probabilité qu'elle ait réussi dans le deuxième tour est également de 1/2. Et rappelez-vous, la probabilité de succès ; réussir au second tour est indépendant de la probabilité de réussir au premier tour. Parce qu'au deuxième tour, le défi de Bob sera indépendant des défis que Bob a choisi au premier tour. C'est pourquoi la probabilité qu'Alice soit réussie au deuxième tour est la 1/2 et c'est comme si la probabilité qu'Alice soit capable de tromper Bob dans tous les tours en devinant correctement le défi de Bob dans tous les tours est 1/2 * 1/2 * 1/2 * 1/2 … k fois ce qui n'est rien d'autre que 1/2k. Donc si k est significativement plus grand, imaginez k = 100 et si une Alice ne connaît pas l'isomorphisme entre G1 et G2, alors il existe au moins un des tours avec une très forte probabilité où Alice sera attrapé et donc Bob rejettera la déclaration d'Alice. Le seul cas où Alice aura du succès dans tous les tours est quand elle est capable, quand elle a la chance de deviner le défi de Bob dans tous les tours k à l'avance ce qui ne peut arriver qu'avec la probabilité 1/2k qui est très petit si k devient significativement plus grand. (Référez-vous à l'heure de la diapositive: 23:11)Essayons maintenant de comprendre la propriété de la connaissance zéro ici où ; n'oubliez pas que nous devons considérer le cas où Alice est honnête et Bob est corrompu, le vérificateur est corrompu. Et l'objectif du vérificateur corrompu est d'analyser le transcrit du protocole et d'apprendre la permutation secrète Π qui mappe le graphe G1 au graphe G2, à savoir l'isomorphisme entre le graphe G1 et G2. Il s'avère que dans chaque round le vérificateur corrompu n'apprend rien sur le mappage de Π, car si le défi de Bob est i = 2, alors la réponse qu'Alice throws est le mappage du graphe G2 à H qui ne révèle rien à propos d'un mappage secret Π. D'autre part, si le vérificateur défie Alice avec i = 1 alors, dans ce cas, Alice répond avec la composition du mappage secret Π avec un autre σ de mappage choisi au hasard. Et puisque σ est choisi au hasard ; dans l'itération, vous pouvez imaginer que σ agit comme une sorte de masque ici, car puisque σ est choisi au hasard et que Π est un choix aléatoire et disponible uniquement avec Alice ; ce mappage global composé σ ne révèle rien à propos du mappage secret Π car le masquage ici, à savoir le σ de mappage secret, est choisi au hasard par Alice. Et comme σ est choisi au hasard dans chaque itération indépendamment de toutes les itérations, même si un prover malveillant continue à défier Alice avec i = 1, il ne pourra pas se renseigner sur le mappage secret Π, et cela vaut même si le vérificateur n'est pas délimité sur le plan informatique. Donc, en ce sens, un Bob malveillant n'apprend rien sur le témoin secret Π disponible avec Alice. Cela montre que ce système de preuve de la connaissance zéro que nous avons conçu pour le problème de l'isomorphisme du graphe répond en effet à toutes les exigences d'un système de preuve de zéro connaissance pour un problème d'isomorphisme de graphe. Cela m'amène à la fin de cette conférence. Juste pour résumer dans cette conférence, nous avons introduit le problème du système de preuve zéro-connaissance, nous avons officiellement déclaré leurs exigences, à savoir l'exhaustivité, la solidité et l'exigence de connaissance zéro et nous avons également vu une instance