Fonctions de hachage cryptographiques | Modèle Oracle aléatoire | Alison
Loading
Notes d'étude
Study Reminders
Support
Text Version

Modèle Oracle aléatoire

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 Prof. Dr. Ashish Choudhury (Former) Infosys Foundation Career Development Chair Professor International Institute of Information Technology – Bangalore Lecture – 31 Random Oracle Model – Part I (voir Diapositive #: 00:30) Bonjour tout le monde, bienvenue à cette conférence. Juste un bref résumé. Lors de la dernière conférence, nous avons discuté de certaines des attaques génériques qui peuvent être lancées sur les fonctions de hachage, à savoir les attaques d'anniversaire, et nous avons également discuté de certaines applications de fonctions de hachage comme des chaînes de blocs, des arbres Merkel, etc. Dans cette conférence, nous poursuivrons notre discussion sur la fonction de hachage cryptographique. Fondamentalement, nous allons introduire un modèle de preuve très intéressant ce que nous appelons modèle aléatoire-Oracle. (Reportez-vous à la page Heure de la diapositive: 00 :58) Donc, commençons par notre discussion sur le modèle Random-Oracle qui est aussi appelé ROM. Il y a donc plusieurs scénarios où nous concevons des primitives cryptographiques où les fonctions de hachage résistant aux collisions sont utilisées et ces constructions sont très pratiques dans la nature et elles sont très efficaces. Certains des exemples de ces primitives sont la fonction de dérivation des clés, le schéma d'engagement, les primitives à clé publique et ainsi de suite, mais il s'avère malheureusement que nous ne pouvons pas prouver la sécurité de ces primitives cryptographiques en fonction des propriétés standard de la fonction de hachage. Ce que je veux dire par les propriétés standard de la fonction de hachage est la propriété de résistance aux collisions, non. Donc ce que fait exactement le modèle Random-Oracle c'est qu'il vous donne un modèle dans lequel vous pouvez prouver la sécurité des primitives cryptographiques qui sont conçues en fonction des fonctions de hachage où vous ne pouvez pas donner les preuves de sécurité simplement basées sur la propriété de résistance de collision de la fonction de hachage sous-jacente et ce que nous faisons dans ce modèle Random-Oracle est que nous faisons une supposition très forte sur la fonction de hachage sous-jacente. En effet, nous faisons une hypothèse idéalisée et l'hypothèse exacte que nous faisons au sujet de la fonction de hachage sous-jacente sera discutée bientôt et ce que ce modèle Random-Oracle fait est qu'il agit comme un terrain intermédiaire pour vous où vous n'avez pas de preuve de sécurité d'une main et que l'autre main vous avez une preuve de sécurité rigoureuse juste à partir des hypothèses de cryptographie standard. Donc, comme vous ne pouvez pas donner la preuve de sécurité des constructions basées sur les propriétés standard de la fonction de hachage cryptographique, en supposant que nous sommes dans le modèle Random-Oracle sert une sorte de terrain intermédiaire où en faisant des hypothèses idéalisées sur votre fonction de hachage sous-jacente, vous pouvez compléter la preuve de sécurité. (Reportez-vous à la page Heure de la diapositive: 02:47) Nous allons donc entrer dans les détails sous-jacents du modèle "Random-Oracle". Ce que nous faisons dans ce modèle aléatoire-Oracle est que nous supposons que nous concevons une primitive cryptographique basée sur une fonction de hachage qui permet de mapper des chaînes de bits de longueur arbitraire à des sorties de taille fixe de chaînes de bits. Ce que nous faisons, c'est que nous supposons que les fonctions de hachage sous-jacentes se comportent comme une fonction aléatoire de mappage d'entrée de longueur arbitraire à des sorties de longueur fixe et imaginez que nous concevons une primitive cryptographique où nous utilisons cette fonction de hachage sous-jacente modélisée comme une fonction vraiment aléatoire. Nous supposons que chaque participant du système a un accès Oracle à la fonction de hachage. Cela signifie qu'aucun participant au système, y compris l'utilisateur véritable ainsi que l'adversaire ne sera en mesure de connaître les détails internes et le code et la logique de la fonction de hachage sous-jacente. Donc, c'est une supposition très forte que nous faisons au sujet de la fonction de hachage sous-jacente dans ce modèle car en réalité lorsque nous concevons une primitive cryptographique, nous allons instancier cette fonction de hachage par une fonction de hachage pratique. Lorsque nous utilisons une fonction de hachage pratique, chaque entité du système sera en mesure de connaître le code exact ou la logique de la fonction de hachage, mais lorsque nous donnons la preuve dans le modèle Random-Oracle, nous supposons qu'aucune entité du système ne connaît les détails exacts de la fonction de hachage sous-jacente. Aussi les appels entre l'oracle et les participants sont privés. Cela signifie, imaginez si j'ai une primitive de cryptographie impliquant l'utilisateur 1, l'utilisateur 2, et l'utilisateur 3 et chacun d'entre eux doit utiliser cette fonction de hachage à dire que l'utilisateur 1 veut évaluer la fonction de hachage sous-jacente sur certaines entrées x. Nous supposons ensuite que dans le modèle Random-Oracle, l'interaction entre l'utilisateur 1 et l'interface ou l'oracle H passe par un canal privé entre l'utilisateur 1 et l'oracle H. Ainsi, l'utilisateur 2 et l'utilisateur 3 ne connairaient pas les entrées exactes sur lesquelles l'utilisateur 1 va évaluer la fonction de hachage sous-jacente ou l'oracle. Il est également supposé que l'oracle H est maintenu comme un tableau constitué de plusieurs x, y et la façon dont ce tableau est maintenu est le suivant. Si une entité interroge cet oracle sur une entrée x, alors ce que fait la table ou l'oracle c'est qu'elle vérifie essentiellement dans la table existante qui est une liste de plusieurs valeurs (xi, yi) s'il existe une entrée xi avec la valeur étant x. Cela signifie essentiellement que la table vérifie si la valeur de l'oracle sur l'entrée x est déjà là dans la table ou non. Si c'est déjà là, alors le yi correspondant est retourné comme la sortie de l'oracle sur l'entrée x, alors que s'il n'y a pas d'entrée existante xi avec la valeur x, alors ce que fait l'oracle? Il crée une nouvelle entrée dans la table où elle stocke la valeur de x et contre cette x, elle stocke une valeur y uniformément aléatoire où la valeur y est une chaîne de bits l uniformément aléatoire et qui sert de référence ou de sortie de fonction ou de la valeur oracle ou de la sortie oracle pour l'entrée x pour les appels ultérieurs à l'oracle. Donc, en maintenant cet oracle comme une table (x, y) comme celle-ci, on s'assure que l'oracle satisfait aux propriétés qui sont requises d'une fonction vraiment aléatoire, non. (Référez-vous à l'heure de la diapositive: 06 :06) Il y a donc des propriétés importantes dans le modèle Random-Oracle et cela sera crucial lorsque nous donnerons des preuves dans le modèle Random-Oracle. Ainsi, la première propriété est que si une entrée x n'a pas été interrogée sur l'oracle H, alors la valeur de l'oracle sur cette entrée x sera une valeur de l bit uniformément aléatoire et ceci est valable même si l'entrée x est connue d'une entité ou une partie de l'élément x est connue de l'entité ou même si x n'est pas uniformément aléatoire. Cela signifie même si x est une entrée où tous les bits de l'entrée sauf le dernier bit est connu et si l'oracle n'a pas été interrogé sur cette entrée x, alors la sortie de l'oracle sur cette entrée x sera une valeur de l bit uniformément aléatoire, et je souligne que ceci est différent de la propriété pseudo aléatoire du générateur de pseudorandom. Disons que si nous avons un générateur de pseudo-aléatoires G, alors pseudo randomité, il faut que la sortie du générateur de pseudorandom G sur certains x devrait être presque identique à une valeur uniformément aléatoire seulement si l'entrée x pour le générateur de pseudorandom est une valeur uniformément aléatoire et inconnue, alors que dans le contexte du modèle Random-Oracle, il y a une pseudo-propriété aléatoire que nous avons besoin est différente. Ici, ici, nous avons besoin que si l'oracle n'est pas interrogé pour l'entrée x et même si le x n'est pas une valeur uniformément aléatoire et est connu de vous, la valeur de sortie H (x) va être une valeur uniformément aléatoire du co-domaine. C'est donc l'une des propriétés importantes. (Reportez-vous à la page Heure de la diapositive: 07 :41) La deuxième propriété importante du modèle Random-Oracle est la propriété d'extractibilité qui sera une propriété très importante plus tard lorsque nous verrons les preuves des primitives cryptographiques dans le modèle Random-Oracle. Alors supposons que nous avons une construction cryptographique de quelque primitif, disons que cette primitive C impliquant un certain nombre d'entités, il pourrait s'agir d'une communication sécurisée, protocole, ou il pourrait s'agir de n'importe quel protocole de cryptographie. Par exemple, imaginez que cette primitive de cryptographie C implique 3 entités et que cette primitive nécessite également des appels à une fonction de hachage sous-jacente et supposons que nous donnons une preuve de réduction qui prouve que cette primitive cryptographique satisfait certains biens, certains biens de sécurité selon une certaine définition, et nous disons que nous donnons une preuve basée sur la réduction et fondamentalement quand nous donnons une preuve basée sur la réduction pour prouver que les soi-disant primitives de cryptographie satisfont à certaines propriétés de sécurité selon certaines définitions données dans le modèle d'Oracle aléatoire, alors quand nous donnons la réduction Sonde ce que nous allons faire en gros, c'est que nous supposerons que nous avons un adversaire A attaquant votre primitive cryptographique C, puis en utilisant cet adversaire notre but sera de concevoir un autre adversaire dire A ’ attaquer un autre primitif, non. C'est ce que nous faisons habituellement en matière de réduction de la preuve. Dans le cadre de sa stratégie d'attaque, cet adversaire A pourrait avoir besoin d'appeler la fonction de hachage sous-jacente, à droite, parce que cela pourrait faire partie de sa stratégie d'attaque sous-jacente. Mais depuis que nous sommes dans le modèle Random-Oracle, cet adversaire a besoin de faire des appels oracle à la fonction H. Ainsi, lorsque cet adversaire A ’ que nous concevons dans le cadre de la réduction, il appelle cet adversaire existant A comme sous-programme, il viendra à savoir que l'adversaire A ou l'adversaire existant A doit invoquer l'oracle H sur plusieurs intrants x de son choix. Donc ces entrées, la sortie de l'oracle sur les entrées que l'adversaire A veut interroger sera maintenant apprise par l'adversaire A ’ dans le cadre de la réduction. Donc, c'est ce que nous entendons par la propriété d'extractibilité. Cela signifie que l'adversaire A ’ peut maintenant voir les requêtes x que l'adversaire existant A aimerait faire à l'H Oracle. Cela ne contredit pas la propriété que, comme je l'ai dit plus tôt, j'ai dit que les appels entre chaque entité et oracle sont maintenus ou se passent par un canal privé. Dans la preuve de réduction, l'adversaire A ’ invoque fondamentalement l'adversaire A dans son esprit. Cela signifie que lorsqu'il appelle l'adversaire existant A comme sous-programme, il en viendra automatiquement à savoir que dans le cadre de sa stratégie d'attaque, quelles sont les requêtes x ou les valeurs x pour lesquelles l'adversaire existant A aimerait faire les appels oracle de H, non. Donc, cela ne viole pas la propriété existante du modèle Random-Oracle, mais le point important ici est que dans le cadre de la réduction, le nouvel adversaire que nous essayons de construire, à savoir A ’, il peut extraire les entrées x pour lesquelles l'adversaire existant aimerait faire les appels oracle. C'est donc l'une des propriétés importantes du modèle Random-Oracle et de la seconde propriété. (Reportez-vous à la page Heure de la diapositive: 11:02) La troisième propriété du modèle Random-Oracle qui sera de nouveau très cruciale lorsque nous allons faire des preuves des primitives cryptographiques dans le modèle ROM est la propriété de programmabilité, et ce que je veux dire exactement par la propriété de programmabilité, comme je l'ai dit, si nous donnons une réduction établie, alors le nouvel adversaire A ’ que nous concevons quand il appelle l'adversaire existant A, il approuira les requêtes H, à savoir les entrées x pour lesquelles l'adversaire existant aimerait faire les appels à l'oracle, non. Mais puisque nous faisons maintenant une réduction ici à droite, il n'y a pas de fonction H qui soit disponible soit à l'adversaire A, soit à l'adversaire A ’ parce que maintenant nous n'invoons pas une instance de la primitive C, pas vrai. Lorsque nous instancions en fait un appel de la primitive C, les parties auront accès à un oracle H, mais maintenant ce que nous faisons ici, c'est que nous donnons une preuve basée sur la réduction, donc il n'y a pas d'instanciation de la primitive C. Donc, il n'y a pas d'oracle disponible soit à l'adversaire A ’ ou à l'adversaire existant A, mais puisque dans le cadre de la réduction notre stratégie accusatoire A est de faire des appels oracle pour l'oracle H à plusieurs x entrées fondamentalement notre adversaire A ’ a pour simuler l'interaction de l'adversaire existant avec H. Fondamentalement, l'adversaire A ’ doit définir la sortie de l'adversaire. Oracle H à ces x intrants que l'adversaire A est exigeant. Donc, ce que l'adversaire A ’ peut faire dans le cadre de la réduction qu'il peut lui-même fixer ou qu'il peut lui-même prétendre comme s'il a l'accès à l'oracle et ce qu'il peut faire c'est de sélectionner aléatoirement des valeurs y du codomaine de l'oracle sous-jacent H et de le retourner comme la sortie de la requête oracle que l'adversaire A a demandé. C'est donc ce que nous entendons par la propriété de programmabilité. Nous appelons cela une propriété de programmabilité car dans la réduction, le nouvel adversaire A ’ peut programmer, il peut définir la sortie de l'oracle aux entrées x pour lesquelles l'adversaire A a demandé la réponse de l'oracle. Il s'agit donc d'une autre propriété importante du modèle aléatoire Oracle que nous utiliserons lorsque nous aurons les preuves basées sur la réduction pour les primitives cryptographiques dans le modèle Random-Oracle. (Voir Heure de la diapositive: 13 :21) Comparons maintenant une preuve donnée ou une preuve de sécurité pour une primitive de cryptographie donnée dans le modèle Random-Oracle par rapport à la preuve de sécurité donnée dans le modèle standard. Alors imaginez à nouveau que nous avons quelques primitives cryptographiques dire C et cela implique de dire plusieurs entités et où nous avons besoin de chaque entité pour utiliser une fonction de hachage sous-jacente. Ainsi, dans le modèle standard lorsque nous disons que nous avons une preuve de sécurité dans le modèle standard, nous ne abstraisons pas la fonction de hachage sous-jacente en tant que Random-Oracle. Nous supposons plutôt qu'il s'agit d'une fonction de hachage standard et que chaque entité a un accès libre à la fonction de hachage sous-jacente. Cela signifie qu'il connaît le code complet, la description complète de la fonction de hachage sous-jacente. Nous ne partons pas de l'hypothèse que les entités interagissent avec la fonction de hachage par oracle, alors que dans le modèle Random-Oracle lorsque nous supposons que si vous concevez-vous une autre primitive C ’ impliquant une fonction de hachage. Si nous disons que nous donnons une preuve dans le modèle Random-Oracle, alors ce que nous entendons exactement par là, c'est que chaque fois que nous instancions la primitive C ’ au début une nouvelle fonction aléatoire H sera instanciée et aucune de l'entité ne saura ce qu'est exactement cette fonction de hachage, pas vrai. Il s'agit donc d'une différence majeure pour une preuve de sécurité donnée dans le modèle aléatoire Oracle. Cela signifie que chaque fois que nous instancions la primitive C ’, il ne serait pas vrai que le même Random-Oracle ou la même instanciation de l'oracle H sera disponible tel qu'il existait lors de l'appel précédent. Dans chaque appel ultérieur dans chaque nouvel appel ou un appel indépendant de C ’, un oracle indépendant H sera corrigé au début et chaque instance aura accès à cet oracle via des canaux privés où aucune entité ne saura ce qu'est exactement la description de l'oracle sous-jacent ou instancié. La définition de sécurité dans les 2 preuves que nous avons données ici sera différente comme suit. Donc, nous donnerons une certaine définition de la sécurité, donc la définition de sécurité dans le modèle standard sera donc que pour tous les temps polynomiaux parties adverses ou essayant d'attaquer la primitive C, la définition sera que la probabilité d'un certain événement doit être négligeable qui sera la définition de sécurité pour la primitive C, à droite, dans le modèle standard et plus ou moins la même vaut même pour une définition de sécurité donnée dans le modèle Random-Oracle. La définition de la sécurité est que pour tous les adversaires à temps multiples qui tentent d'attaquer la primitive C ’ dans le modèle Random-Oracle, la probabilité de certains événements doit être négligeable. Quel est exactement cet événement qui dépend de la primitive sous-jacente C et de la primitive sous-jacente C ’ que nous essayons de construire. Par exemple, si la primitive C est un processus de chiffrement sécurisé, il s'agit essentiellement de l'événement de distinction. Alors que si la primitive C est une primitive de cryptographie très compliquée, alors cet événement qui définit si l'adversaire est capable de gagner le jeu ou non peut être un événement compliqué, mais indépendamment de cela, l'intuition sous-jacente est que dans la définition standard de sécurité du modèle signifie que la probabilité d'attaque ou de rupture de l'adversaire, ou la probabilité qu'un adversaire s'assure que certains événements particuliers se produisent avec une certaine probabilité est négligeable alors que dans le modèle ROM, la définition de sécurité reste plus ou moins la même. La différence est que dans le modèle standard, la probabilité est prise sur le choix aléatoire des parties et non sur la fonction de hachage sous-jacente car la fonction de hachage sous-jacente va être une fonction de hachage fixe car chaque fois que nous allons instancier la primitive C dans le modèle standard, la même fonction de hachage sera utilisée de nouveau et de nouveau, mais lorsque nous envisageons la probabilité que certains événements soient négligeables dans le modèle aléatoire Oracle, alors la probabilité est prise non seulement sur les requêtes aléatoires sur les parties mais aussi sur le choix aléatoire de l'oracle H qui est Instancié au début de l'instanciation de la primitive C ’. Donc, c'est une autre différence importante dans la preuve de sécurité dans le modèle Random-Oracle contre une preuve de sécurité dans le modèle standard. (Référez-vous à l'heure de la diapositive: 17 :29) Ce que cela signifie, c'est que dans le modèle Random-Oracle, la sécurité n'est pas garantie pour chaque instanciation d'Oracle. Cela signifie que la sécurité ne peut pas être garantie pour une instanciation particulière de H, mais elle peut être garantie pour d'autres instanciations de H, alors que dans la définition standard lorsque nous donnons la preuve juste à partir de la propriété de résistance de collision de la fonction de hachage sous-jacente, la preuve de sécurité tient pour toute instanciation de H qui est garantie d'être résistante aux collisions, mais ce n'est pas le cas dans le modèle Oracle Random. Cela signifie qu'il peut être difficile de soutenir que toute instanciation concrète de l'oracle H par des fonctions de hachage spécifiques qui sont déterministes dans la nature donnera un schéma sûr, et le point important est que, même si nous donnons une preuve de sécurité dans le modèle d'Oracle Random lorsque nous déployons effectivement ce schéma dans le monde réel, l'oracle sous-jacent H doit être instancié par une fonction de hachage déterministe en béton et dès que nous instancions l'oracle H par une fonction de hachage déterministe en béton chaque entité du système, l'expéditeur, le récepteur, le parti honnête et l'adversaire aussi Avoir accès au code de l'instanciation sous-jacente de l'H. Cela signifie que l'adversaire ne peut être limité à un simple accès à l'oracle à H, non. Il s'agit donc des propriétés importantes du modèle Random-Oracle. (Reportez-vous à la section Heure de la diapositive: 18 :48) Maintenant, voyons rapidement un exemple pour comprendre comment les choses fonctionnent exactement dans le modèle Oracle aléatoire. Alors imaginez que nous avons une fonction de hachage qui prend des entrées de taille de bits de lin et vous donne la sortie des bits de taille et à l'aide de cette fonction de hachage suppose que j'ai conçu une fonction G qui prend une entrée de taille de bits de lin et vous donne une sortie de bits de taille et en gros ce que cette fonction G fait est juste d'évaluer la fonction de hachage sur l'entrée x. Maintenant, je demande que si nous sommes dans le modèle Random-Oracle et si nous interprétons cette fonction de hachage sous-jacente comme Random-Oracle qui est instancié au début de chaque instanciation de la fonction G, alors cette fonction G peut être considérée comme un générateur de pseudorandom et pour prouver que la fonction G que nous avons construite ici est un générateur de pseudorandom dans le modèle Random-Oracle, nous devons modifier le jeu d'indistinction, le jeu d'indistinction standard que nous utilisons pour définir la sécurité du générateur de pseudorandom pour incorporer le modèle Random-Oracle. Le changement qui va se produire ici est que si vous vous souvenez dans le jeu d'indistinction standard pour PRG, le défi pour l'adversaire est de distinguer un échantillon de pseudorandom d'un échantillon vraiment aléatoire, mais maintenant que nous allons fournir une preuve dans le modèle Random-Oracle, nous avons aussi besoin de modéliser l'accès oracle à la fonction de hachage sous-jacente de l'Oracle Random-Oracle auquel le distinguisher peut avoir accès. Alors, voyons le jeu d'indistinction modifié pour le PRG dans le modèle Random-Oracle. Donc au début de cette expérience, cette expérience d'indistinction, une instanciation aléatoire de H se produira et personne n'aura accès au code de ce H, donc c'est pourquoi je le détiens comme une boîte ici, ni l'expérience, ni le distinguisher ne connaîteront les détails exacts de l'H, les deux auront un accès oracle à H. Maintenant, comme pour le jeu d'indistinction PRG, l'expérience du challenger choisit un échantillon y de petits morceaux de taille et défie le distinguant pour savoir comment il est généré, qu'il soit aléatoire ou pseudo-om. En gros, la façon dont cette y aurait été générée, c'est que le challenger aurait choisi une pièce uniformément aléatoire et la jeter et selon la valeur de cette pièce s'il est égal à 0, alors y est vraiment aléatoire alors que si la pièce est 1, alors le challenger aurait choisi une entrée x du domaine et il aurait évalué l'oracle H sur cette entrée x et d'évaluer qu'Oracle sur l'entrée x, le challenger ou l'expérience aurait fait une requête privée à l'oracle que le distinguant ne peut pas voir. Maintenant, une fois l'échantillon y est donné, le défi pour le distinguisher est de savoir si l'échantillon y est généré par la méthode b = 0 ou si l'échantillon de défi y est généré par la méthode b = 1, mais maintenant puisque nous sommes dans le modèle Random-Oracle, nous donnons à l'oracle de distinction l'accès à la fonction de hachage sous-jacente, puis il peut rendre polynomial nombre de requêtes à l'oracle sous-jacent H, il peut demander les valeurs H (x) pour plusieurs x de son choix et ensuite il doit enfin décider si l'échantillon y est généré par la méthode b = 0 ou par la méthode b = 1. À savoir, les sorties de distinction sont un peu et la définition de sécurité pour le PRG dans le modèle Random-Oracle est que nous disons que la fonction G est un générateur de pseudorandom dans le modèle Random-Oracle si pour chaque adversaire polytime ou distinction participant à ce jeu modifié, le comportement de l'élément de distinction demeure presque le même, que l'échantillon soit un pseudorandom ou qu'il soit vraiment aléatoire. Cela signifie qu'il importe peu que l'échantillon y soit généré par la méthode b = 0 ou par la méthode b = 1, dans les deux cas, la réponse de l'élément de distinction, à savoir b ’, doit être presque identique sauf avec la probabilité négligeable. (Référez-vous à la diapositive: 22 :44) Donc maintenant, ce que nous allons prouver, c'est que la construction G que nous avons conçue ici satisfait en effet cette nouvelle définition de l'indistinction PRG si nous sommes dans le modèle Random Oracle, non. Supposons donc qu'on nous donne un distinguisher D arbitraire et que Q dénote l'ensemble des requêtes x que le distinguisher a faites à Oracle, à droite, et le point important ici est que puisque le temps d'exécution d'un distinguisher est polytime, le nombre de requêtes que ce distinguisher pourrait faire est une fonction polynomiale dans le paramètre de sécurité. Donc maintenant, quelle est la probabilité que le distinguant D ait demandé la valeur oracle sur l'entrée x que le challenger a choisi pour le cas b = 1 à droite. Rappelez-vous donc que chacune des valeurs x, à droite, la valeur x que le challenger principal a utilisée, si l'échantillon y est généré par la méthode b = 1 droite, il s'agit d'une valeur uniformément aléatoire des bits de lin de taille. Donc, la probabilité que le distingueur D puisse deviner correctement la valeur de x dans son ensemble est maximum de | Q|/2lin, droite. La taille de Q, à savoir la taille de la requête définie sur 2lin et si nous nous assurons que lin est une fonction polynomiale dans le paramètre de sécurité, puis fondamentalement ce que nous obtenons, c'est que cette probabilité que notre distinction D querelle l'oracle pour l'entrée x est en effet une quantité négligeable. Donc maintenant, ce que cela signifie que si l'échantillon y qui est lancé comme un défi est généré par la méthode b = 1, cela signifie, c'est une valeur de pseudorandom ou c'est la sortie de G alors rien à propos de la valeur x est révélé par y parce que ce que nous supposons ici est que dans le modèle Random-Oracle, la fonction H est comme une fonction vraiment aléatoire. Cela signifie que même si y aurait été généré en faisant la requête oracle à l'oracle H sur une entrée x, la valeur de ce x ne sera pas révélée à partir de la sortie y. Cela signifie que nous pouvons dire que si nous sommes dans le cas où b = 1, c'est-à-dire si le défi y est généré par l'algorithme G, puis conditionné au fait que l'entrée x n'appartient pas à l'ensemble de requêtes du distinguant. Cela signifie que le distinguant n'a pas demandé le droit d'entrée x, le distinguant n'a pas demandé la valeur de l'oracle H sur la condition d'entrée x de cet événement du point de vue de ce distinguant, cet échantillon y est comme une chaîne vraiment aléatoire parce que nous supposons que dans le modèle Random-Oracle, H est comme une fonction vraiment aléatoire. Cela signifie une condition à cet événement, peu importe si nous sommes dans le cas b = 0 ou b = 1. Du point de vue du distinguant dans les deux cas, l'échantillon de défi y est un échantillon vraiment aléatoire et donc sa sortie va être la même, et nous avons déjà soutenu que ce qui est la probabilité qu'effectivement x n'appartient pas à Q, eh bien c'est la probabilité que c'est la taille de Q over 2lin (|Q|/2lin) qui est en effet une fonction négligeable, ce qui prouve clairement que la fonction G que nous avons construite ici à l'aide de la fonction de hachage peut être considérée comme un générateur de pseudorandom si nous allons dans le modèle Random-Oracle. Cela m'amène à la fin de cette conférence. Pour résumer dans cette conférence, nous avons introduit un modèle Random-Oracle. Ceci est essentiellement utilisé pour fournir la preuve de sécurité des primitives cryptographiques basées sur certaines fonctions de hachage où nous ne pouvons pas terminer une preuve de sécurité de cette primitive juste en utilisant les propriétés standard des fonctions de hachage, à savoir la propriété de résistance aux collisions et nous avons également vu une démonstration du modèle Random-Oracle, à savoir que si nous prenons une fonction de hachage et le modéle comme une Oracle Random, alors nous pouvons l'utiliser pour construire un générateur de pseudorandom. Je vous remercie.

Notification
You have received a new notification
Click here to view them all