Loading
Notes d'étude
Study Reminders
Support
Text Version

NP-Classe complète

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 Indian Institute of Science – Bangalore Lecture – 58 Zero-knowledge Protocols Part II Bonjour tout le monde, bienvenue à cette conférence. Juste un rapide récapitulation. Lors de la dernière conférence, nous avons commencé notre discussion sur les protocoles zéro connaissance. Ainsi, lors de cette conférence, nous poursuivrons notre discussion sur les protocoles de connaissance zéro, en particulier nous allons introduire des protocoles de connaissance zéro pour les classes NP-complètes. (Référez-vous à l'heure de la diapositive: 00:44) Pour cela, nous allons introduire le problème de 3 couleurs et nous allons voir un système de validation des connaissances zéro pour 3 problèmes de coloriage. (Référez-vous à l'heure de la diapositive: 00:51)Par conséquent, rappelons que lors de la dernière conférence, nous avons vu que nous pouvons spécifier exactement une relation. Par exemple, si vous vous souvenez de la relation pour un problème de graphe-isomorphisme, alors la relation sera constituée de paires (x, w) où x est une instance de problème. Ainsi, dans cet exemple, si nous considérons un problème d'isomorphisme de graphe que l'instance x est essentiellement la description connue publiquement de 2 graphes et le composant témoin correspondant à cette instance x sera le mappage isomorphisme entre le jeu de sommets du premier graphe et le jeu de sommets du second graphe. Et en effet si nous avons une instance x ou un problème où les 2 graphiques sont isomorphes, alors nous devrions avoir un témoin correspondant w. Lors de la dernière conférence, nous avons vu que nous pouvons trouver un système de preuve zéro-connaissance qui permet au prover de montrer si une instance x a un témoin correspondant disponible avec la prover et non sans révéler quoi que ce soit sur le témoin w. Mais il s'avère que le graphique de relation-isomorphisme n'est pas une relation complète du PN et que la question suivante est de savoir si nous disposons d'un système de preuves à base zéro pour n'importe quelle relation complète du PN? Donc, pour les gens qui se demandent ce qui est exactement le problème du NP, ou le NP, la relation complète est. Un problème x est appelé un problème d'AN complet, si donné à un témoin w, nous pouvons vérifier si le témoin w est effectivement un témoin approprié pour l'instance de problème x et en quantité polynomiale de temps. Spécifiquement, en effectuant un calcul non déterministe pour le temps polynomial. C'est la première exigence. La raison pour laquelle nous appelons des problèmes tels que NP-complete, l'aspect complet ici indique que si nous avons un autre problème y appartenant à la classe NP, alors l'instance de problème y peut être réduite à une instance du problème x dans le temps polynomial du temps. En ce sens, ce problème x sera appelé comme une relation complète du PN. Cela signifie que si vous avez une solution pour résoudre l'instance d'incident x, cela signifie que si vous pouvez trouver des témoins pour l'instance de problème x en temps polynomial, puis en utilisant simplement la réduction des instances d'incident de y à l'instance de problème de x, vous pouvez également obtenir des solutions pour vos instances de problème y. Il s'agit donc d'une définition approximative de la relation complète du PN. Donc, nous sommes maintenant intéressés à voir si nous pouvons trouver un système de preuves à base zéro pour n'importe quelle relation qui est NP complète. Il s'avère donc que le graphique-isomorphisme n'est pas une relation complète du PN. (Référez-vous à l'heure de la diapositive: 03:35) Donc, ce que nous allons faire maintenant, c'est que nous allons voir un système de preuve de la connaissance zéro pour un autre problème de calcul que nous appelons problème de coloriage 3, qui est un problème bien connu de l'AN. Alors, voyons d'abord ce que nous entendons par un graphe 3-colorable? Nous disons qu'un graphe donné avec n sommets est 3-colorable si chacun de ses sommets peut être attribué une des couleurs à partir de couleurs connues publiquement c1, c2, c3 de telle sorte qu'aucune paire de sommets adjacents ne se voit attribuer la même couleur. Cela signifie que nous devons colorier les sommets de manière à ce que chaque paire de paramètres de chaque arête ait des couleurs différentes. Si vous considérez ce graphique par exemple, il s'agit d'un graphe 3-colorable. Par exemple, si mon { c1, c2, c3 } est { rouge, bleu, jaune }, alors nous pouvons colorier les sommets de ce graphique en utilisant ces 3 couleurs par l'une de ces affectations en assignant ces couleurs aux sommets respectifs. Et maintenant vous pouvez voir que 2 sommets adjacents, à savoir pas 2 sommets adjacents, se voient attribuer la même couleur ici. Par exemple, si je considère ces 2 sommets, ils sont adjacents dans le sens où ils sont les points d'extrémité d'un seul bord ont le même bord et ils ont des couleurs différentes. De la même façon, si je considère cette arête, les points finaux ont des couleurs différentes, etc. D'autre part, si je considère le graphique de votre côté droit, alors il n'est pas 3-colorable. Cela signifie qu'il n'est pas du tout possible de colorier tous les sommets de ce graphique avec seulement 3 couleurs satisfaisant à la condition qu'aucune paire de sommets adjacents n'ait la même couleur. Le problème 3-coloriage ou la relation de 3 couleurs est une relation complète de l'AN et l'entrée (x, w) dans la relation de 3 couleurs ressemblera à ceci. Ainsi, l'instance x sera la description publique d'un graphique, à savoir le nombre de sommets et le jeu de sommets, et l'ensemble de bord du graphe sera connu publiquement. Si, en effet, cette instance x, c'est-à-dire ce graphique, est 3-colorable, le témoin correspondant sera le mappage ou l'attribution de la couleur { c1, c2, c3 } à l'ensemble de sommets que j'appelle un. Et le coloriage du témoin doit satisfaire la restriction selon laquelle si l'arête (u, v) appartient à l'arête, alors la couleur attribuée au noeud u et la couleur attribuée au noeud v doivent être différentes. Si, en effet, il est possible de trouver une telle attribution de couleur pour l'instance de problème donnée x alors (x, w) sera considéré comme une entrée valide ou satisfaisant la relation 3-coloriage. Si nous ne trouvons pas de témoin w, alors correspondant à un x donné, alors ce x ne sera pas présent dans la relation de 3 couleurs. (Référez-vous à l'heure de la diapositive: 06:29)Donc, voyons maintenant que vous connaissez le système de validation des connaissances pour le problème de 3 couleurs. Alors imaginez une Alice est le ver et Bob est le vérificateur. L'entrée commune pour Alice et Bob est la description d'un graphique. Dis, l'entrée privée pour le tube étalon, à savoir Alice ici, est un 3 coloriage du graphe connu publiquement, à savoir une affectation de cartographie du sommet définie à l'ensemble de couleurs { c1, c2, c3 } et ce qu'Alice veut prouver à Bob que le graphe donné est 3-colorable et qu'elle a une affectation disponible avec elle. Donc, le but ici est de trouver un système de preuves de zéro connaissance qui devrait convaincre Bob qu'Alice connaît bien le mappage correspondant sans révéler quoi que ce soit sur le mappage réel. Dans le même temps, le système de démonstration zéro connaissance doit s'assurer que si le tube étalon ne connaît pas le 3-coloriage du graphe donné ou si le graphe n'est pas 3-colorable à la première place puis avec une très forte probabilité tout en donnant la preuve, Alice devrait être attrapée par Bob. Rappelez-vous qu'il s'agit de votre propriété de solidité, la deuxième exigence. Et la première propriété, à savoir Bob, ne doit pas apprendre quoi que ce soit sur le 3-coloriage est la propriété de la connaissance zéro. (Référez-vous à l'heure de la diapositive: 07:56)Maintenant, voyons comment exactement le système de preuve zéro-connaissance du problème de coloriage de 3 couleurs ressemblera. Alice a le 3-coloriage privé disponible avec elle. Donc, ce qu'elle fait, c'est qu'elle permute au hasard la couleur qu'elle a disponible avec elle, c'est-à-dire qu'elle a le mappage secret désolé qu'elle ait la coloration originale du graphe. Donc, ce qu'elle fait c'est qu'elle crée une permutation aléatoire de l'ensemble de couleurs. Par exemple, elle peut dire créer une permutation que nous sommes rouges est cartographiée en bleu, le bleu est mappé au rouge et la troisième couleur reste telle qu'elle est par la permutation. Fondamentalement, ce qu'elle fait, c'est qu'elle crée un nouveau 3-coloriage du graphe qui est disponible avec Bob par rapport aux nouvelles couleurs cartographiées. Ainsi, où que ce soit dans le graphe original, quels que soient les sommets de couleur rouge, ces sommets dans le nouveau colorant seront attribués à la couleur bleue car la couleur rouge est mappée à la couleur bleue. De la même façon dans l'ancienne coloriage, quel que soit le sommet, la couleur bleue de ces sommets dans le nouveau 3-coloriage se voit attribuer une couleur rouge, etc. Tout ce qu'Alice fait à sa fin. Maintenant une fois Alice calcule le nouveau 3-coloriage du graphe ce qu'elle fait est qu'elle garde les nouvelles couleurs assignées des sommets respectifs dans une boîte verrouillée. Et ici les boîtes verrouillées et les guillemets. Nous verrons plus loin quelles sont exactement les propriétés que nous avons besoin de ces boîtes verrouillées et comment l'instancions à l'aide de la primitive cryptographique. Donc, à un niveau très élevé ce que ces boîtes verrouillées signifie est que dans cet exemple nous avons 6 sommets. Donc ce qu'Alice fait, c'est tout ce qui est la nouvelle couleur assignée au sommet qui est gardé à l'intérieur de cette boîte verrouillée où le verrouillage est disponible avec Alice. Sa boîte verrouillée dans le sens où sans avoir accès à la clé, Bob ne peut pas ouvrir la première boîte et voir quelle est la nouvelle couleur du premier sommet. De la même façon que la nouvelle couleur du second sommet se trouve dans le second verrou, la nouvelle couleur du troisième vertex se trouve dans cette troisième boîte verrouillée, et ainsi de suite. Bob ne peut pas voir les couleurs disponibles dans les boîtes verrouillées. Donc du point de vue de Bob si en effet Alice connaît le 3-coloriage original alors du point de vue de Bob, Bob se sentira comme s'il voit maintenant un nouveau 3-coloriage du même graphe existant public avec l'exception qu'il ne sait pas ce qui sont ces couleurs exactes maintenant parce que toutes ces nouvelles couleurs sont dans la boîte verrouillée. Donc, ce premier message est comme un engagement d'Alice à Bob. Ça veut dire qu'elle dit que “ okay! J'ai maintenant calculé un nouveau 3-coloriage. Je ne vous montrerai pas le nouveau 3-coloriage. Ces nouveaux 3 couleurs sont en fait disponibles dans ces boîtes verrouillées. C'est l'engagement de mon côté comme le système de preuve zéro-connaissance. Une fois que Bob reçoit l'engagement d'Alice, ce que Bob fait c'est créer un défi pour Alice. Le défi est essentiellement un bord aléatoire (i, j) du graphique. N'oubliez pas qu'Alice ne sait pas exactement quel est le bord aléatoire que Bob va contester quand Alice engage les nouvelles couleurs dans les boîtes verrouillées. Donc, une fois que Bob prend le bord au hasard, il conteste Alice que “ vous pouvez ouvrir les nouvelles couleurs dans la boîte i et la boîte j. Je veux vérifier s'il s'agit bien de couleurs différentes ou non. Parce que si vous connaissez le 3-coloriage original puis comme par votre cartographie le nouveau coloriage devrait également être un 3D. Et donc puisque i et j sont des noeuds adjacents la nouvelle couleur du nœud i et une nouvelle couleur du nœud j devraient idéalement être différents de sorte que c'est ce que Bob est difficile à montrer à Alice. Et pour répondre au défi de Bob ce qu'Alice révèle, c'est qu'il révèle les clés de la boîte i et de la boîte j. Maintenant j'ai besoin d'une autre propriété de la boîte verrouillée ici. Souvenez-vous, l'une des propriétés de la boxe verrouillée que tout ce qui est conservé à l'intérieur de la boîte verrouillée Bob ne peut voir son contenu avant et à moins qu'il n'ait accès aux clés de la boîte. La deuxième propriété que j'ai besoin de ces boîtes verrouillées est qu'une fois Alice a gardé quelque chose à l'intérieur de la boîte verrouillée et si plus tard, on lui demande de révéler le contenu de l'une des cases qu'elle ne peut plus tard changer le contenu qu'elle a déjà conservé à l'intérieur de cette boîte particulière. Dans ce cas, dans ce cas, Bob défie Alice d'ouvrir la boîte i et la boîte j et Alice est forcée de donner les clés pour la boîte i et la boîte j. En ce qui concerne les propriétés du serrure, peu importe ce qu'elle a commis à l'intérieur de la boîte et la boîte de jème qu'elle n'est pas autorisée à changer. Bob va vérifier. En effet, Bob prendra les clés pour la moelle et la boîte, ouvrira ces boîtes pour qu'elles soient les nouvelles couleurs par rapport au nouveau 3-coloriage pour le graphe. Bob considérera qu'il s'agit d'un tour réussi s'il constate que les nouvelles couleurs du noeud i et du noeud j sont différentes, ce qui devrait idéalement être le cas. Si ce n'est pas le cas, alors le round est infructueux et Bob arrête le protocole ici même. C'est ainsi qu'est le fonctionnement d'une série de systèmes de preuves zéro-connaissances. Maintenant, pour renforcer la confiance dans cette preuve ce que Bob peut faire, Bob peut répéter ce processus k nombre de fois de façon indépendante où dans chaque round Alice peut utiliser un autre 3-coloriage par rapport aux anciennes techniques de 3 couleurs. Cela signifie chaque ronde qu'elle va choisir un mappage indépendant de l'actuel 3-coloriage à un nouveau 3-coloriage et que Bob va choisir de nouveaux défis (i, j) à chaque round. Cela signifie que ce ne sera pas le cas (i, j) qui est choisi comme l'arête de défi par Bob restera la même dans tous les cycles. Ils seront choisis de façon indépendante, et Alice ne sera pas en mesure de savoir quoi que ce soit sur les défis pour le prochain tour à l'avance et si tous ces tours de k sont couronnés de succès, Bob considérera qu'Alice connaît bien le 3-coloriage réel ou original pour le graphe existant. (Référez-vous à l'heure de la diapositive: 14:18)Il s'agit donc d'un système de preuve de connaissance zéro. Essons maintenant de faire l'analyse pour le système de preuves de la connaissance zéro, qu'il satisfasse à l'exigence de l'exactitude, de la solidité et de la connaissance zéro. Correction ou exhaustivité, si mémoriser un bien complet signifie que si Alice et Bob sont honnêtes et si Alice a un témoin pour le graphe, c'est-à-dire qu'elle a le 3-coloriage original alors avec une forte probabilité que la preuve devrait passer et Bob doit être convaincu. Il est facile de voir que si, en effet, Alice connaît le 3-coloriage original, alors effectivement dans toutes les rondes, elle sera en mesure de convaincre Bob. Elle n'échouera pas et, par conséquent, chaque tour sera un succès, et Bob acceptera la preuve. (Référez-vous à l'heure de la diapositive: 15:03)Maintenant, considérons la propriété de solidité. Alors, souvenez-vous de la propriété de solidité, nous devons prendre en compte le cas lorsque le ver est corrompu. Prover est corrompu en ce sens que soit le graphe n'est pas 3-colorable, soit il peut être le cas que le graphe est 3-colorable, mais Alice ne sait pas exactement ce qui est le 3-coloriage du graphe original. Par souci de simplicité et sans perte de généralité, on suppose que le graphique n'est pas 3-colorable. Alors, analysons maintenant quelle est la probabilité qu'un tour soit un succès en ce qui concerne un Alice potentiellement corrompu qui ne sait pas ou qui pour un graphe où le graphe n'est pas 3-colorable. Il s'avère que si Alice est corrompue et Bob est honnête alors la seule façon qu'Alice puisse réussir à réussir le tour est quand elle peut deviner en avance le bord (i, j) qui va être choisi comme le défi par Bob. Parce que si le graphe n'est pas 3-colorable, alors Alice ne peut pas créer de nouveau 3-coloriage pour le graphe car le graphe n'est pas 3-colorable en premier lieu. Alors la seule façon pour Alice de gagner est qu'elle peut deviner. Elle peut prétendre dans son esprit que c'est peut-être le bord (i, j) que Bob peut me défier. Donc, ce qu'elle peut faire c'est qu'elle peut assigner des couleurs arbitraires aux extrémités du graphe. En fait, elle peut attribuer les mêmes couleurs à tous les noeuds du graphique, à l'exception des points i et j. Parce qu'Alice peut juste deviner que ça pourrait être le bord que Bob peut me demander d'ouvrir. Que peut faire Alice par exemple, elle peut deviner que je pourrais être un mot 1 et j peut être égal à n'importe quoi dire semantics numéro 3? Ainsi, par exemple, elle peut imaginer qu'elle pourrait être mise au défi de montrer les nouvelles couleurs pour le graphe pour le bord (v1, v3) ou pour les points de fin v1 et v3. Ce qu'elle peut faire c'est pour la première boîte verrouillée qu'elle peut garder la couleur bleue et la troisième boîte verrouillée elle peut garder la couleur jaune, puis dans toutes les autres cases elle peut juste garder les mêmes couleurs. Et si en effet elle a de la chance, alors il se pourrait qu'on lui demande d'ouvrir la première boîte verrouillée et la troisième boîte verrouillée. Alors, elle va montrer Bob que “ Hey! J'ai attribué des couleurs différentes au noeud numéro v1 et numéro de noeud v3. Mais quelle est la probabilité de succès d'Alice deviner à l'avance que ce sera le hasard (i, j) que Bob va défier Alice pour ouvrir. La probabilité qu'Alice soit capable de deviner le défi aléatoire (i, j) n'est rien d'autre que 1 sur la taille de l'ensemble de bord. Environ la taille de l'arête définie dans le pire des cas peut être n2. Cela signifie que la probabilité de succès du cycle en cours de réussite est limitée par 1 sur l'ensemble de bord 1 / n2. Rappelez-vous qu'il y a de tels cycles. Cela signifie que la seule façon d'Alice sans même savoir que le 3-coloriage du graphe peut réussir tous les tours k, c'est quand pour chacun des k tours, elle peut deviner correctement à l'avance ce challenge (i, j) que Bob va demander à chaque round. Et la probabilité de réussite de deviner qu'en une seule ronde est 1 /E. La probabilité qu'elle puisse le faire dans tous les cycles de k n'est que 1/ |E|k. En définissant k pour être suffisamment grand, il est possible de s'assurer que cette quantité 1/ |E|k devient très petite. Ainsi, définitivement dans l'un des tours de k, Alice se fera prendre. Si elle est prise dans l'un de ces tours k, Bob va suspendre le système de preuve et la réclamation d'Alice sera rejetée. Cela prouve la solidité de la propriété. (Référez-vous à l'heure de la diapositive: 19:07) Maintenant, analysons une propriété de zéro-connaissance et souvenons-nous de la propriété zéro-connaissance que nous devons examiner lorsque notre prover, à savoir Alice, est honnête et qu'en effet, elle a un témoin qu'elle veut cacher à un vérificateur malveillant. Donc, dans ce cas, le vérificateur est le type corrompu et l'objectif du vérificateur est d'essayer d'en apprendre davantage sur le 3-coloriage original. Il s'avère que même si le vérificateur est corrompu, il n'apprend absolument aucune information sur l'original 3-coloring.This is because what he is voyant in the first round. Il voit le nouveau 3-coloriage mais pas la nouvelle 3D exacte, mais plutôt le vérificateur voit les nouvelles couleurs affectées aux sommets du graphe qui sont tous conservés dans les boîtes verrouillées. Ce n'est qu'une paire de boîtes verrouillées qui est ouverte par Alice en réponse au défi lancé par notre vérificateur. Donc même si le vérificateur voit la couleur du nœud i et le nœud j, ils sont le nouveau 3-coloriage. Ils correspondent au nouveau 3-coloriage et il n'apprend que les couleurs pour le noeud ith et le noeud jth, mais pas pour l'ensemble du nouveau 3 coloriage. N'oubliez pas que dans chacune des rondes, Alice choisit un nouveau choix indépendant. De cette façon, elle permute au hasard l'actuel 3 coloriage et crée un nouveau 3-coloriage. Donc, cela signifie que le nouveau 3-coloriage au premier tour sera indépendant du nouveau 3-coloriage au deuxième tour et comme ceci le nouveau 3-coloriage dans le kth round sera indépendant de tous les nouveaux 3 colorings au tour précédent. Cela signifie que dans chacune des rondes, le vérificateur va juste apprendre que je vais voir les nouvelles couleurs du nœud i et du nœud j qui, je le sais, seront distinctes. Et c'est pourquoi il ne révèle rien sur le 3-coloriage original qui était disponible avec Alice. Cela prouve la propriété de la connaissance zéro. (Voir Heure de la diapositive: 21:01) Revenir à la question suivante: quelles sont les propriétés dont nous avons besoin dans les cases verrouillées? Comme je l'ai dit, nous avons besoin de 2 propriétés. Nous avons besoin de la propriété cachée. Si vous êtes honnête, si Alice est honnête et si elle a gardé un contenu dans la boîte, alors jusqu'à ce que les clés de ces boîtes soient données à Bob, il ne peut pas ouvrir et voir le contenu qui est conservé à l'intérieur de la boîte. C'est ce que je veux dire par la propriété cachée ici. La propriété de liaison signifie que si Alice est corrompues, alors ce ne devrait pas être le cas où elle a mis quelque chose dans la boîte, mais quand elle est supposée ouvrir la boîte, elle peut la transformer ou elle peut la changer en tout nouveau contenu. C'est donc une propriété de liaison et maintenant nous savons très bien comment instancier cette boîte verrouillée à la fois avec ces deux propriétés. Fondamentalement, nous pouvons utiliser un schéma d'engagement pour que cela signifie ce qu'Alice a à faire à chaque round, elle doit calculer un nouveau 3-coloriage et une nouvelle couleur pour les sommets. Elle doit s'engager en utilisant n'importe quel programme d'engagement. Lorsque Bob conteste d'ouvrir les nouvelles couleurs du noeud ith et du noeud jth, Alice doit donner les informations d'ouverture correspondant à l'engagement de la jème et à l'engagement de la jème. Donc, ça prouve que nous avons maintenant un 3-coloriage. Nous avons maintenant un système de preuve zéro pour le problème de coloriage 3 et le fait que le problème de 3-Coloriage est un problème d'AN-complete qui signifie que nous avons maintenant un système de preuve zéro-connaissance pour n'importe quelle relation NP. (Référez-vous à l'heure de la diapositive: 22:31)Maintenant, voyons la puissance du système de preuve zéro-connaissance. Ce que nous pouvons maintenant faire, c'est que nous pouvons voir un très joli framework, c'est-à-dire un compilateur qui peut compiler n'importe quel protocole passivement sécurisé en protocole sécurisé. Imaginez, vous avez une tâche de calcul distribué dire f, il peut s'agir de n'importe quelle tâche de calcul abstrait. Il peut être dit, par exemple, une tâche impliquant plusieurs parties 2 parties, 3 parties ou disons 4 parties ou n nombre de parties où chaque partie a des entrées par exemple x1, x2, x3, x4. Je prends le cas où j'ai 4 parties. L'objectif des parties est essentiellement de calculer f (x1, x2, x3, x4) et de manière à ce que même s'il y a des méchants dans le système, ils n'apprennent rien sur les entrées x des gentils autres que ce qu'ils peuvent apprendre de leur propre entrée et de la sortie de fonction. C'est un problème très abstrait. Ce problème appelle également un problème de calcul multipartique. La façon dont un protocole de calcul multi-partite fonctionne comme suit: les parties auront leurs propres entrées et elles choisiront un peu de randomité locale par exemple r1, r2, r3, r4 respectivement, puis elles interagiront les unes avec les autres conformément aux instructions de ce protocole f. A la fin, ils obtiennent la fonction de sortie y où y = f (x1, x2, x3, x4) et pour le moment imaginez que ce protocole f est sécurisé passivement. Il est passivement sécurisé dans le sens que si même s'il y a un adversaire qui peut contrôler ou qui peut voir l'entrée et le caractère aléatoire local d'une fraction de ces n parties et quels que soient les messages qu'ils ont échangés au cours du protocole, en voyant leurs entrées la sortie et les messages qu'ils ont reçus et qu'ils ont envoyés au cours du protocole, le méchant n'apprend rien de plus sur les entrées des gentils. C'est donc ce que je veux dire en disant que ce protocole est une sécurité passive. Maintenant, imaginez que je veux compiler ce protocole. Compiler ce protocole en ce sens que je veux conserver le protocole f et je veux m'assurer que le protocole reste en sécurité même s'il y a un adversaire actif ou un adversaire malveillant. Un adversaire actif, c'est-à-dire que je veux compiler ce protocole en un portail mal sécurisé, désolé pour la faute de protocole. Ce que je veux dire par la sécurité malicieuse ici, c'est que même si les méchants qui sont sous le contrôle de leur adversaire essaient de s'écarter des instructions du protocole, ils ne doivent pas apprendre quoi que ce soit sur les entrées du bon gars. Je ne veux pas concevoir un nouveau protocole ou un nouveau protocole. Je veux simplement conserver le protocole qui est garanti contre l'adversaire passif. Alors comment pouvons-nous compiler le protocole passivement sécurisé en un protocole sécurisé? C'est une question que nous voulons connaître. Nous voulons maintenant utiliser ici un système de preuve zéro. Ainsi, il s'avère qu'un moyen générique de convertir le protocole passivement sécurisé en un protocole sécurisé malicieusement est le suivant: si chaque partie prouve à toutes les autres parties qu'elle suit correctement les instructions du protocole, alors en présence d'un adversaire malveillant, le protocole f va accomplir sa tâche. Maintenant, la question est de savoir ce que nous voulons dire en disant qu'une partie prouve à l'autre partie qu'elle suit correctement l'instruction du protocole. Je veux dire par là que chaque partie doit prouver à toutes les autres parties que les messages qu'elle envoie sont effectivement en rapport avec leur caractère aléatoire et leur contribution conformément aux instructions données par le protocole f. Comment les autres parties peuvent-ils vérifier si chaque partie suit son cours ou non? Il peut vérifier les messages envoyés par une partie en particulier et le témoin si cette partie envoie ou exécute correctement son action ou ne sera pas l'entrée des parties et le caractère aléatoire local. Par exemple, dans ce cas, si Alice veut vérifier si ce tiers suit son instruction de protocole correctement ou non? Alors une façon de vérifier qu'est Alice vérifie les messages que cette tierce partie envoie. En plus de cela si ce tiers montre son entrée x3 et son caractère aléatoire r3 qu'il a utilisé comme partie de ce protocole f à Alice alors en effet Alice peut effectuer l'action de ce tiers, parce que la description du protocole est connue ce qui n'était pas connu était x3 et r3. Mais maintenant x3 et r3 est également donné à Alice, donc elle peut elle-même calculer les messages que ce tiers est supposé envoyer selon le protocole f. Si ces messages correspondent aux messages que ce tiers a envoyés ou communiqués lors de l'exécution réelle du protocole, ce dernier prouve que ce tiers suit son pas conformément au protocole f. Comme chaque partie peut vérifier l'action de chaque partie s'il exécute ses actions conformément au protocole f, si cette partie révèle son entrée et son caractère aléatoire local. Mais il s'avère que l'apport et le caractère aléatoire local de chaque partie ne peuvent être donnés à d'autres parties parce que c'est ce qui assure la sécurité du protocole f. Si j'approuis l'entrée et le caractère aléatoire de toutes les autres parties, je ne peux pas garantir la sécurité du protocole f. Donc, il s'avère que la déclaration que chaque partie veut prouver à toutes les autres parties, à savoir que je suis en suivant l'instruction du protocole n'est rien d'autre qu'une instance d'une déclaration de NP. Les instances de problème sont l'ensemble de messages que j'ai envoyés, et je veux vous prouver que, correspondant à ces messages, j'ai un peu de caractère aléatoire et certaines entrées de sorte que ces messages sont effectivement calculés de manière cohérente selon les entrées et le caractère aléatoire selon l'instruction de protocole f. Donc, ce que chaque partie doit à présent faire pour convaincre à l'autre partie qu'elle suit effectivement l'instruction du protocole, elle doit fondamentalement prouver une déclaration de NP. Et il est intéressant de noter que nous avons maintenant un système de preuve zéro pour le problème de coloriage 3, qui est une déclaration complète de l'AN. Etant donné qu'il s'agit d'une instruction NP-complete, cela signifie qu'une instance de l'incident NP ou une instruction NP peut être réduite à une instance de ce problème de 3 couleurs. Cela signifie que nous pouvons maintenant utiliser le système de preuve zéro-connaissance pour le problème de 3 couleurs. Chaque partie peut transformer une instance de l'instruction NP, c'est-à-dire qu'elle suit correctement l'instruction du protocole en une instance du problème de 3 coloriage et nous donne une preuve de zéro connaissance pour l'existence de 3-coloriage et convaincre les autres parties qu'elle suit effectivement les instructions du protocole. Si la preuve est satisfaite, cela signifie que donner la garantie que chaque partie suit correctement les instructions du protocole. Si la preuve n'est pas la preuve, nous pouvons tout simplement arrêter le protocole lui-même. Donc, en ce sens le système de preuve zéro-connaissance, il vous donne un paradigme très puissant de compilation d'un protocole passivement sécurisé dans un protocole malicieusement sécurisé. Donc cela m'amène à la fin de cette conférence, juste pour résumer dans cette conférence, nous avons vu un système de preuve de la connaissance zéro pour le problème de 3 couleurs. Et 3-le problème de coloriage est un problème bien connu de l'AN et nous avons vu que l'utilisation d'un système de preuve zéro connaissance nous permet de compiler tout protocole sécurisé passivement pour toute tâche de calcul distribué dans un protocole qui sera sécurisé même contre un adversaire malveillant.