Loading
Notes d'étude
Study Reminders
Support
Text Version

Schémas d'identification

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 – Bangalore Lecture – 53 Identification Schemes (référez-vous à la diapositive: 00:39) Bonjour à tous, bienvenue à cette conférence. Le plan de cette conférence est le suivant. Dans cette conférence, nous introduisons la définition du schéma d'identification, qui est une primitive crytographique bien connue et nous allons voir une instanciation du schéma d'identification, à savoir nous verrons la description du schéma d'identification de Schnorr basée sur l'hypothèse du log discret. Lors de la prochaine conférence, nous verrons comment utiliser l'heuristique de Fiatt-Shamir, nous pouvons convertir le schéma d'identification de Schnorr en une instanciation du schéma de signature numérique basé sur l'hypothèse de log discret. (Référez-vous à la diapositive: 01 :01) Alors essayons de comprendre la motivation qui sous-tend le schéma d'identification. Alors, encore une fois, permettez-moi de prendre un exemple, que j'ai déclaré lors de notre première conférence. Donc, c'est un épisode bien connu de Sunderkand à Ramayana. Ram est en Inde et il est très déçu. Il manque sa mère Sita, alors il demande à son messager de passer mon message à Sita que je lui manque. Le messager à savoir que Lord Hanuman dit que vous voulez mon seigneur et que Ram dit que puisque vous allez rencontrer Sita pour la première fois, elle peut vous demander de prouver votre identité. Donc vous pouvez prendre cette bague comme une preuve parce que seul Sita sait à propos de cette bague et que le messager prend la bague et qu'il va au Lanka, puis il commence l'interaction avec la mère Sita disant que je suis le messager de Lord Ram et qu'il a un message pour vous. Mais Sita a si peur là, alors elle n'est pas prête à croire Hanuman, alors elle demande comment je peux vous faire confiance et prouver votre identité et Hanuman prouve son identité en montrant l'anneau que Lord Ram a donné à Hanuman et une fois que Mère Sita voit la bague, elle accepte l'identité du messager. Ainsi, dans cet exemple, l'anneau sert de preuve et confirme l'identité et la preuve de Hanuman ’. La preuve que Hanuman a donné est montrée en clair, mais il s'avère qu'il est extrêmement dangereux de montrer clairement dans l'ère actuelle de Kalyuga où la preuve est très volatile et que les gens ne se font pas confiance les uns les autres. Donc, le schéma d'identification est une primitive cryptographique, il s'agit essentiellement d'un protocole n-interactif entre deux entités, qui permet à un étalon de prouver son identité. Dans cet exemple, Hanuman sans révéler les références secrètes, à savoir l'anneau. Alors, laissez-nous entrer dans les détails formels du schéma d'identification et nous nous intéressons à la construction d'un système d'identification dans le cadre de la clé publique, et plus particulièrement nous nous concentrerons sur trois systèmes d'identification de réponse à un défi de validation, mais il n'est pas nécessaire que votre schéma d'identification ait trois tours. Mais nous nous intéressons uniquement à l'étude du schéma d'identification consistant en trois séries d'interactions, car plus tard, nous verrons comment construire des schémas de signature à partir de trois plans d'identification. Un schéma d'identification est donc constitué de quatre protocoles. Nous avons donc un algorithme de génération de clé, et nous aurons deux algorithmes, P1 et P2 pour le prover qui veut prouver son identité. Et nous aurons un protocole ou un algorithme pour le vérificateur à l'aide duquel le vérificateur peut vérifier l'identité du tube étalon. Ainsi, la façon dont nous utilisons un système d'identification est la suivante. Donc, on a un étalon et un vérificateur. L'algorithme de génération de clé sera exécuté principalement par le prover et il exécutera l'algorithme de génération de clés pour obtenir une clé de vérification et une clé secrète. La clé de vérification sera disponible dans le domaine public pour vérifier l'identité de la cuve dite "prover" alors que la clé secrète ne sera disponible qu'à l'étalon et à l'aide de ce schéma d'identification, le but de l'étalon est de convaincre le vérificateur qui est au courant de la clé de vérification que le prover connaît la clé secrète correspondante k associée à cette clé de vérification vk et la façon dont cela se produit est par un protocole à 3 tours. Ainsi, lors du premier tour, le prover exécute l'algorithme P1, qui prend un engagement secret d'entrée et de sortie, que nous dénotent par moi, et l'engagement est donné au vérificateur. Le prover envoie l'engagement au vérificateur et avec que l'algorithme P1 génère des informations d'état, ce qui se maintient en lui-même. Maintenant, voyant l'engagement, le vérificateur choisit un défi, que je dénote par r. Ce défi est choisi à partir d'un espace de défi et le défi est choisi uniformément à partir de l'espace de défi et de voir le défi r du vérificateur, le prover doit trouver une réponse, et la réponse est dénotée par s, qui est calculé en exécutant l'algorithme P2, qui prend la clé secrète sk, les informations d'état et le défi. En voyant la réponse, le vérificateur doit vérifier si le prover a répondu correctement en réponse au défi r, en ce qui concerne l'engagement I, qui a commis au tour 1 et de vérifier que le vérificateur exécute l'algorithme V, qui prend la clé de vérification, le défi et la réponse et l'objectif du vérificateur est de vérifier si la sortie de cet algorithme V est égale à l'engagement I ou non. Si la sortie correspond à l'engagement que j'ai alors dit que le vérificateur accepte l'identité du ver, cela signifie que le vérificateur est convaincu qu'en effet la personne qui connaît la clé secrète correspondant à la clé publique de vérification, alors que si ce test que la sortie de l'algorithme V doit être égal à I échoue, alors le vérificateur n'est pas convaincu que le prover qui a réellement participé à ce protocole connaît la clé secrète correspondante de sk. Donc, une exécution réussie dans ce protocole implique que la communication s'est effectivement produite avec le prover prévu et non pas un imposteur. Plus précisément, nous avons besoin des deux propriétés suivantes d'un schéma d'identification. Donc, la première propriété est la propriété correcte, qui dit que pour chaque paire de clé que votre algorithme de génération de clé pourrait produire et chaque transcription, qui est générée en exécutant une instance du schéma d'identification, ce qui suit doit tenir. Si le vérificateur exécute l'algorithme de vérification par rapport à la clé de vérification et au composant r et s de la transcription, il doit donner la composante I de la transcription. Cela signifie que la vérification doit être réussie au niveau du vérificateur. Donc, c'est la propriété de la correction. La propriété de sécurité exige de manière informelle qu'un imposteur ou un écouteur qui a des écoutes et qui a une interaction entre un nombre polynomial d'un prover et d'un vérificateur de l'époque ne soit pas en mesure d'accepter la transcription et de le faire accepter au côté du vérificateur, et cela devrait tenir si mon adversaire est délimité par les calculs. Donc en gros ce que cela signifie est, si l'adversaire a vu le nombre polynomial de conversations entre un étalon honnête et un vérificateur honnête, alors même après avoir vu un nombre polynomial de conversations en l'absence de la clé secrète sk et seulement avec la connaissance de la clé de vérification vk, il ne devrait pas être possible pour les écouesdropper délimités par les calculs de prétendre comme un prover et d'arriver avec une conversation d'acceptation, ce qui est accepté au côté du vérificateur. (Référez-vous à la diapositive: 08 :48) Donc, nous modélisons cette exigence cette exigence informelle par une expérience de sécurité. Donc dans cette expérience, que nous appelons l'expérience d'identification Ident (, nous avons un adversaire délimité par les calculs et le challenger et la description du schéma d'identification est publiquement connu, donc le challenger passe en premier et il exécute l'algorithme de génération de clé, garde la clé secrète avec lui-même, et envoie la clé de vérification à l'adversaire. Maintenant, ce que l'adversaire peut demander est, il peut exiger pour un accès oracle au service de transcription et cela modéle le fait que dans le monde réel, il pourrait y avoir un adversaire qui aurait pu voir le nombre polynomial d'interactions, ou le nombre polynomial d'instances du schéma d'identification s'exécuter entre un étalon honnête et un vérificateur honnête. Donc, cet adversaire aurait pu voir le nombre polynomial de transcriptions sous la clé inconnue, qui pourrait être seulement disponible avec le tube étalon. Donc, pour modéliser cela, nous donnons à l'adversaire ici l'accès Oracle au service de transcription, afin de répondre à cet accès Oracle, ce que le challenger a à faire essentiellement les suivants. Donc, il connaît la clé de vérification vk, et il connaît aussi la clé secrète sk, donc il exécute l'instance de ce schéma d'identification, simulant le rôle du prover et du vérificateur dans son esprit. Donc, en gros, il vient juste de faire le cas de ce schéma d'identification comme jouant le rôle du prover lui-même. En jouant le rôle du vérificateur lui-même et en générant le moi correspondant, r, et que la transcription est donnée en réponse au service d'accès Oracle que l'adversaire a demandé et puisque l'adversaire pouvait demander à Oracle l'accès au service de transcription pour un nombre de fois polynomial, chaque fois qu'une telle demande d'accès Oracle ou Oracle arrive, le challenger doit générer une transcription simulée comme celle-ci et l'avoir donnée à l'adversaire. Une fois que l'adversaire est formé en voyant le nombre polynomial de transcription, il essaie de trouver une transcription contrefaite et d'essayer de le faire accepter par le challenger. Pour ce faire, il prétend que c'est le prover et essaie de trouver la transcription acceptée sans même connaître le secret correspondant, donc il soumet un engagement, que je dénote par I*. En réponse, le challenger présente un défi, que je dénote par r *, et en réponse au défi que l'adversaire soumet une réponse s *. Ce triplet I*, r *, et s * est une transcription contrefaite, que l'adversaire tente de produire à l'égard de toute cette expérience et la définition de l'expérience dit que l'adversaire est capable de falsifier une transcription, qui est dénotée en disant que la sortie de cette expérience est une, si et seulement si l'algorithme de vérification v, lorsqu'il est exécuté par le challenger par rapport à la clé de vérification, et r * composant, et s * composant de cette transcription falsifiés donne effectivement I*. Cela signifie que I*, r *, s * constitue une transcription d'acceptation, et notre définition de la sécurité est que nous disons qu'un schéma d'identification est sécurisé si pour chaque adversaire polytemporel participant à cette expérience, la chance qu'il peut gagner l'expérience est borné par une fonction négligeable. (Référez-vous à la diapositive: 12 :42) Donc, c'est notre définition de notre système d'identification. Maintenant, voyons si nous pouvons arriver à une instanciation d'un tel système et qu'il existe un schéma d'identification bien connu dû à Schnorr, et il est basé sur l'idée suivante. Donc, en gros, dans ce schéma d'identification essaie de prouver son identité en disant qu'il connaît le log discret d'une valeur publiquement connue sous le g DLog (, et pour vérifier la revendication du tube étalon, le vérificateur défie essentiellement le prover pour montrer une combinaison linéaire aléatoire du log discret de y, où les combinateurs aléatoires pour la combinaison linéaire seront sélectionnés par le vérificateur. Donc, l'idée ici est que si le ver connaît le log discret de y, alors il devrait être capable de produire une combinaison linéaire aléatoire du log discret de y avec toute autre valeur de la plage correspondante du log discret, et toute cette interaction se produit dans la mode de connaissance nulle dans le sens que tout au long de l'interaction, il sera fait en sorte que le prover connaisse le log discret de y à la base g, puis le journal discret n'est pas appris par un vérificateur malveillant. Ainsi, l'algorithme de génération de clé de ce schéma est le suivant. Il génère une clé de vérification et la clé secrète, où la clé de vérification est la description d'un groupe cyclique d'ordre q et une description du générateur et de l'élément aléatoire y du groupe où y est essentiellement gx, où x est sélectionné de l'ensemble 0 à q-1 et la clé de vérification, à savoir le log discret de y, qui est x sera disponible avec le tube étalon, alors que la clé de vérification, à savoir y sera disponible avec le vérificateur. Donc, le prover va d'abord dans ce schéma d'identification et il valide une valeur k de l'ensemble sélectionné Zq par le calcul de gk, donc c'est une valeur aléatoire qu'il donne au vérificateur et le défi choisi par le vérificateur est une valeur aléatoire r, sélectionnée à partir de l'ensemble Zq et pour répondre au défi, fondamentalement le prover doit trouver une combinaison linéaire du logis discret x de l'y. La valeur k qu'elle a sélectionnée dans le round 1 et la combinaison linéaire aléatoire ici est (r * x + k) modulo q et pour vérifier si la réponse du tube étalon est correcte ou non, le vérificateur doit vérifier si les gs * y-r = I ou non, ce qui devrait en fait être le cas si le prover sait x et il a envoyé gk pendant le premier rond.Donc, avant d'entrer dans l'analyse de ce schéma d'identification, nous allons voir une définition ici, nous disons un triple I, r, s où je suis un élément de groupe, et r et s sont des éléments de Zq est une transcription d'acceptation si gs * y-r = I détient et la propriété correcte du schéma d'identification sont de Schnorr Découle du fait qu'en effet le prover et le vérificateur sont honnêtes et que le prover sait que le log discret de y. À savoir qu'il connaît x, alors la transcription générée en exécutant une instance du schéma d'identification de Schnorr sera en effet une transcription d'acceptation. Ainsi, la vérification de la fin du vérificateur ’ sera réussie. Donc, c'est la preuve de la propriété correcte. Maintenant, essayons de comprendre la propriété de sécurité ici. Donc, nous considérons d'abord un écouteur ici et imaginez que le ver et le vérificateur sont honnêtes et qu'il y a un écouteur qui a surveillé le nombre polynomial d'exécutions du schéma d'identification Schnorr. Alors imaginez qu'il a une écoute sur une transcription, qui est I, r, et je demande ici qu'en voyant la transcription ne pas apprendre quelque chose sur la clé secrète sk, c'est-à-dire le log discret de y à la base g, qui est x, et c'est parce que si vous voyez la distribution de l'engagement, c'est-à-dire le I, il est indépendant de x parce que l'engagement je suis gk, où k est choisi indépendamment de x. De la même façon, la composante r de la transcription, elle est complètement indépendante de x et elle est choisie par le vérificateur, donc elle ne révèle rien du secret x. Cependant, si vous voyez la valeur s, alors la valeur est (r * s + k), donc on peut sentir qu'en voyant s, l'écoute peut apprendre quelque chose à propos de x, mais ce n'est pas le cas ici parce que la distribution de s ici est indépendante de x parce que le k qui est utilisé dans le calcul de la combinaison linéaire s est prélevé de façon indépendante et aléatoire par le tube étalon, et si le tube étalon est honnête, alors la valeur k, qui est utilisée dans la combinaison linéaire, sera uniformément aléatoire et inconnue de l'adversaire. Cela signifie simplement en voyant l'adversaire, encore une fois ne peut pas comprendre quoi que ce soit à propos de x et cela signifie qu'une personne qui voit un transcrit d'acceptation I, r, s, n'apprira rien au sujet du secret sous-jacent. X. Ce que l'adversaire ou les écoutes apprenderont simplement que la transcription I, r, s est une transcription d'acceptation et sa distribution est indépendante de x. Donc, sur la base de cette observation, nous pouvons faire une affirmation très forte ici que, nous pouvons dire n'importe quelle écoute peut simuler une transcription d'acceptation basée sur la connaissance de la clé de vérification elle-même. Cela signifie qu'il est aussi bon de dire que même si aucune interaction ne se produit entre le prover et le vérificateur, l'écouteur pourrait bien avancer avec une distribution de probabilité de la transcription, ce qui serait vu par des écoutes de conversations réelles entre le ver et le vérificateur, et comment cela peut être possible, voici la façon dont l'adversaire ou l'écouteur pourrait se présenter avec une transcription simulée à lui seul sans même écouter la conversation entre le ver et le vérificateur. Donc, ce que l'écoute peut faire est, il pourrait choisir au hasard une valeur r et la valeur de Zq puis une fois qu'il choisit la valeur r et la valeur s, il pourrait définir la valeur I comme valeur de gs qu'il a choisie, multipliée par y-r valeur qu'il a choisie, et il s'avère que si vous comparez la distribution de probabilité des transcriptions réelles, et par les transcriptions réelles, je veux dire les transcriptions, qui sont réellement générées par l'exécution réelle de ce schéma d'identification Schnorr où un étalon honnête et un vérificateur honnête participent au protocole. Si nous considérons la distribution de probabilité des transcriptions simulées, par laquelle les transcriptions simulées, je veux dire, les transcriptions qui sont générées par l'écoute par cette méthode, où elle ne voit pas l'exécution réelle du protocole, mais elle vient avec les valeurs de I, r, s en utilisant la méthode, que j'ai discutée tout à l'heure. Donc, si je considère la distribution des probabilités de ces deux transcriptions, elles sont exactement identiques. Ceci est dû au fait que si vous voyez la distribution de probabilité de la valeur r dans les transcriptions réelles et la distribution de probabilité de la valeur r dans les transcriptions simulées, elles sont identiques. Dans une exécution réelle, r sera prélevé au hasard à partir de l'ensemble Zq, et dans la transcription simulée également r les valeurs sont aussi choisies au hasard à partir de l'ensemble Zq. De la même façon dans les transcriptions réelles, il s'agit d'une valeur uniformément aléatoire de Zq parce que k aurait été choisi uniformément au hasard par le tube étalon. Il en est de même pour la valeur s dans les transcriptions simulées et si vous voyez la distribution de probabilité de la valeur I dans les transcriptions réelles ainsi que dans les transcriptions simulées dans les deux cas I = (gs * y-r) parties des transcriptions et ceci est vrai tant pour la transcription réelle que pour la transcription simulée. Donc si vous voyez la distribution sage, la façon dont les transcriptions auraient été générées dans une exécution réelle du protocole et la façon dont les transcriptions sont générées par l'adversaire dans son esprit sans vraiment voir aucune conversation ont exactement la même distribution. Cela signifie que l'écoute de la communication entre un étalon honnête et un vérificateur ne va pas aider l'adversaire à apprendre quoi que ce soit sur la clé secrète sous-jacente x. Maintenant, voici un aliment pour vous. Puisque j'affirme ici que si des écoutes pouvaient simuler et trouver une transcription d'acceptation sans même connaître la clé secrète sk, cela signifie-t-il que l'utilisation de la stratégie, que le simulateur utilise ou que l'écouteur utilise pour trouver la transcription simulée, pourrait forger une transcription d'acceptation et participer à une instance du schéma d'identification de Schnorr et finir par convaincre un vérificateur honnête qu'effectivement il connaît la valeur x, ce qui n'est pas exactement le cas. Il s'avère que ce n'est pas le cas parce que si vous voyez la stratégie de simulation ici, la façon dont l'adversaire a simulé la transcription, il fixe la valeur de r et la valeur de départ. Cela signifie qu'il est à l'esprit qu'il pourrait s'agir de la valeur r ou de la valeur de remise en question, que le vérificateur choisirait et seulement après avoir fixé la valeur r et sa valeur, il en vient à son engagement I. Donc, si avec cette stratégie tente de participer à une exécution du schéma d'identification de Schnorr avec un vérificateur honnête, alors la probabilité qu'il soit en mesure de présenter une transcription acceptée par le vérificateur est la même que le défi r, que l'adversaire pense bien en tête que dans son esprit correspond exactement à la transcription qu'un vérificateur honnête est effectivement en train de récupérer Lors de l'exécution réelle du schéma d'identification Schnorr. Mais la probabilité que la valeur de r simulée, que l'adversaire devine dans son esprit bien en avant correspond à la valeur exacte du défi r qui sera choisi par le vérificateur est une sur la taille de l'ensemble Zq, à savoir son 1/q et si q est suffisamment grand, alors il s'agit d'une très petite quantité une fonction négligeable dans le paramètre de sécurité. Donc, cela signifie que cette stratégie de simulation ne va pas aider les écoutes à gagner ou à falsifiger ou à briser ce schéma d'identification. Donc ce que nous avons prouvé jusqu'à présent, c'est que les écoutes ne vont certainement pas aider l'adversaire à briser la sécurité du schéma d'identification de Schnorr, si seulement qu'elle pourrait attaquer ce schéma d'identification est la suivante, sans savoir que la clé secrète est qu'elle doit interagir avec un vérificateur honnête comme suit. Donc, il faut s'engager avec un certain engagement en ce qui concerne une stratégie que l'adversaire a dans son esprit, et une fois que le vérificateur lance un défi, il doit trouver une réponse s, de sorte que gs * y-r en effet égal à I et si nous voulons que l'adversaire soit capable de briser la sécurité du schéma d'identification de Schnorr avec une forte probabilité, alors il devrait être le cas que cet adversaire qui essaie de briser la sécurité devrait être capable de trouver sa réponse s indépendamment de la valeur de r est utilisé comme un défi par le vérificateur. Cela signifie que ce que j'essaie de dire ici, c'est qu'une fois que l'adversaire a commis une certaine valeur et a présenté son engagement, et si, en fait, l'adversaire est capable de briser la sécurité de ce schéma d'identification avec une très forte probabilité, alors il importe peu de ce qui est exactement le défi. Ça pourrait être r1, ça pourrait être r2, ça pourrait être n'importe quoi. Pour toute valeur de défi, il devrait être possible pour l'adversaire de trouver les réponses de réponse, de sorte que les gs multipliés par y-r doivent être égaux à l'engagement de l'adversaire. Cela signifie, une fois que l'adversaire a soumis son engagement, peu importe si le défi est r1, correspondant à la r1, l'adversaire doit pouvoir se présenter avec s1 de telle sorte que cette propriété ou cette vérification soit réussie ou peu importe que le vérificateur lance le challenger en tant que r2, il devrait être possible pour l'adversaire que pour le même engagement I et le défi r2 l'adversaire soit capable de trouver la réponse correspondante s2, de sorte que la vérification soit réussie à la fin du vérificateur ’ parce que si l'adversaire sait seulement venir avec le Réponse à certaines valeurs précises du défi, alors ce n'est pas une bonne stratégie de l'adversaire. Prouver officiellement cette allégation. Donc, pour cela, j'introduit une notation. Par conséquent, laissez ω dénoter le caractère aléatoire utilisé dans cette réduction complète, sauf les valeurs de défi r1, r2 qui sont sélectionnées par le solveur de journal discret. Ainsi, l'ω indique le caractère aléatoire utilisé par le challenger dans l'expérience de journal discrète. Il indique le caractère aléatoire utilisé par l'adversaire par rapport au schéma d'identification, et il indique également le caractère aléatoire utilisé par le solveur de log discret, à l'exception du caractère aléatoire utilisé pour relever les défis r1 et r2 dans toute cette expérience. Maintenant, j'utilise cette quantité V (ω, r), et je dis que cette fonction V (ω, r) = 1, si elle correspond au hasard ω et correspondant au défi r, l'adversaire contre le schéma d'identification pourrait se présenter avec une transcription d'acceptation. Si tel est le cas, alors je dis que la sortie de la fonction V (ω, r) est 1, sinon il est égal à zéro et en ce qui concerne un caractère aléatoire fixe ω, cette quantité δ ω est définie comme la probabilité que la sortie de la fonction V par rapport à la randomité fixe ω sur tous les éventuels problèmes aléatoires r = 1. C'est ma quantité δ ω, donc c'est essentiellement la probabilité de l'adversaire contre le schéma d'identification qui arrive avec une transcription d'acceptation par rapport à une randomité fixe ω sur tous les éventuels problèmes de randomité r, et laissez-moi appeler cette fonction δ (n) être la probabilité avec laquelle cet adversaire contre le schéma d'identification peut gagner le jeu de sécurité contre le schéma d'identification dans cette réduction. Donc, selon nos notations que nous avons introduites jusqu'à présent, ce δ (n) n'est rien d'autre que la probabilité de tous les aléas aléatoires ω utilisés dans cette réduction complète et la probabilité de toute contestation aléatoire r, la probabilité que V (ω, r) = 1, et si nous l'approfondirons, il ne s'agit que de la sommation de tous les éléments aléatoires ω, que quelle est la probabilité que ω soit le caractère aléatoire utilisé dans cette réduction complète, à l'exception de la randomité des défis et de la randomité fixe ω, quelle est la probabilité de δ ω. C'est ainsi que nous élargissons notre fonction δ (n). Maintenant, si vous voyez cette réduction complète, notre solveur de log discret peut extraire avec succès le logis discret x seulement si ces trois conditions sont retenues, à savoir I, r1, s1 est une transcription d'acceptation, et I, r2, s2 est une transcription d'acceptation et les défis r1 et r2 sont différents où les défis r1 et r2 sont choisis au hasard par le solveur de journal discret. Ainsi, nous pouvons officiellement affirmer que la probabilité que notre solveur de log discret puisse résoudre le log discret est la probabilité que si vous prenez la probabilité sur tous les aléas randomisés et tous les problèmes de caractère aléatoire r1 et r2, V (ω, r1) = 1. Ceci capture le fait que I, r1 et s1 doivent accepter la transcription et V (ω, r2) doit être 1. Ceci capture le fait que je, r2 et s2, devrait accepter la transcription et r1 devrait être différent de r2. Ceci capture la troisième condition. Donc maintenant ce que nous devons faire, c'est simplement que nous élargissons cette expression de probabilité parce que cette probabilité concerne tous les candidats randomisés ω, défier la randomité r1 et contester le caractère aléatoire r2. Donc, en utilisant les règles de probabilité si je règle, alors cette quantité r1 n'est pas égale à r2, je peux remplacer par la probabilité r1. Je peux prendre cette probabilité d'ω, r1 et r2 à l'intérieur, et ensuite je peux remplacer cette condition AND par cette condition de soustraction et ce que je peux faire, je sais que cette chose que ma randomité r1 et r2 sont différentes est 1/q parce que les deux r1 et r2 sont choisis au hasard à partir de l'ensemble Zq et maintenant ce que je peux faire, je peux développer cette première quantité et la seconde quantité par rapport à r1 et r2 à des valeurs de ω fixes, et une fois que je répare ω, ces deux événements de V (ω, r1) doivent être 1 et V (ω, r2) doivent être 1, ils sont indépendants l'un de l'autre, car r1 et r2 sont choisis indépendamment par Le solveur de journal discret. Donc, si je répare le hasard ω, et que je prends l'ω à l'intérieur et essaie de prendre de l'expansion en ce qui concerne le caractère aléatoire r1 et r2, l'inégalité ici, je constate que l'inégalité ci-dessus s'avère être ce truc et maintenant je peux appliquer l'inégalité bien connue de Jensen, que je ne dis pas ici. Vous pouvez utiliser n'importe quelle référence standard pour trouver la formule de l'inégalité Jensen ’, ce que je peux faire, c'est que je peux prendre le carré ici à l'intérieur de la probabilité d'expression de randomité ω pour arriver ici. Si vous voyez maintenant que tout ce grand support ici, le carré de ce grand support n'est rien d'autre que δ (n), c'est ce que la définition de δ (n), δ (n) n'est rien d'autre que la probabilité avec laquelle l'adversaire contre le schéma d'identification peut gagner le jeu ici dans la réduction et c'est ce que nous voulions prouver. Nous avons prouvé que l'avantage du solveur de log discret ici est supérieur ou égal au carré de l'avantage de l'adversaire du schéma d'identification moins 1/q. Si q est une fonction exponentielle dans le paramètre de sécurité, alors ce 1/q est négligeable et selon l'hypothèse que l'avantage du solveur de log discret devrait être une fonction négligeable qui prouve que le carré de l'avantage de l'adversaire contre le schéma d'identification devrait aussi être négligeable. Donc, ça m'amène à la fin de cette conférence. Pour résumer, dans cette conférence, nous avons introduit un schéma d'identification, qui est une primitive cryptographique bien connue et nous avons vu une instanciation du schéma d'identification.