Loading
Notes d'étude
Study Reminders
Support
Text Version

Opérations sur des générateurs pseudo-aléatoires

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

    +

Fondations de CryptographyProf. Dr. Ashish Choudhury (Former) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology – BangaloreLecture – 9Composing PRGsHello everyone, welcome to this lecture. Dans cette conférence, nous poursuivrons notre discussion sur les générateurs de pseudorandom, c'est-à-dire que nous allons voir comment composer des DSRP. (Voir Diapositive Heure: 00 :39) Il s'agit d'une opération très populaire que nous réalisons sur les GPR et en composant les GPR, nous voulons en gros augmenter la taille des entrées et la taille des sorties de PRG. Cela signifie, imaginez que vous vous êtes donné un PRG sécurisé, oubliez pour le moment les étapes de l'algorithme G et l'algorithme G prend essentiellement une entrée de taille l bits et produit une sortie de bits de taille L et maintenant notre objectif est de composer de nombreuses exécutions indépendantes de l'algorithme G, à savoir ici nous allons considérer la composition parallèle de G. Dans notre futur discussion, nous allons aussi considérer la composition en série de G. Donc, en faisant la composition parallèle de l'algorithme G, notre but est de concevoir un nouveau générateur de nombres aléatoires que je dénote par Gnew, qui prend essentiellement une entrée de taille k.l bits et il devrait produire un Sortie de la taille k fois les bits L bits. Donc, vous pouvez imaginer que cet algorithme Gnew prend maintenant des blocs d'entrées où chaque bloc est de taille 1 bits et que chacun de ces blocs de bits de l est uniformément aléatoire. En interne ce que fait Gnew c'est qu'il exécute l'algorithme G de l'algorithme existant G sur le premier bloc, indépendamment qu'il exécute une autre copie de l'algorithme G sur le deuxième bloc et que, indépendamment, il exécute une copie de l'algorithme G avec le dernier bloc comme l'entrée. Il concatène simplement le résultat de chacun de ces appels indépendants de l'algorithme G et qui est défini pour être le résultat de cet algorithme Gnewand c'est comme ça que vous composez en fait l'algorithme G. Maintenant, nous voulons prouver ici que si le nombre d'exemplaires ou le nombre de fois où nous avons composé cet algorithme existant G, à savoir k, est une fonction polynomiale de votre paramètre de sécurité n et si votre algorithme existant G est un PRG sécurisé selon l'une ou l'autre des définitions, soit la définition basée sur l'indistinction, soit le prédicteur de bit suivant, alors nous voulons prouver que le nouvel algorithme Gnew que nous avons A obtenu en composant le PRG en parallèle est également un PRG sécurisé. (Référez-vous à la diapositive: 02 :52) Pour cela, nous allons introduire une nouvelle stratégie de preuve que nous appelons un argument hybride, et c'est une stratégie de preuve très populaire largement utilisée dans les primitives de cryptographie modernes. Afin de démontrer cet argument hybride, je considérerai que le facteur de répétition est k = 2, c'est juste pour la simplicité et plus tard nous allons voir le cas pour un k générique, où k est une fonction polynomiale du paramètre de sécurité, non. Donc, si je considère k = 2 ce qui veut dire, mon algorithme Gnew est maintenant composé de 2 copies indépendantes, 2 copies parallèles de l'algorithme existant G. Je veux prouver que cet algorithme Gnew est un générateur de pseudorandom, et je veux utiliser la définition basée sur l'indistinction. Donc, mon but est de montrer qu'il n'existe pas de distinction de temps polynomial qui puisse distinguer un échantillon uniformément aléatoire généré par cet algorithme Gnew à partir d'un échantillon uniformément aléatoire généré par l'exécution d'un générateur vraiment aléatoire, qui génère des chaînes uniformément aléatoires de longueur 2L bits, non. Donc, pour cela, considérons 2 expériences différentes, qui sont indiquées par H0 et H1.Dans ces deux expériences, le défi pour le distinguisher est un échantillon constitué de 2 blocs de bits L, qui sont indiqués par y1 et y2. Dans les deux mondes, le distinguisher doit découvrir la façon dont cet échantillon y1, y2 a été généré. Donc, dans l'expérience H0, la première partie de l'échantillon ainsi que la deuxième partie de l'échantillon sont à la fois des cordes uniformément aléatoires de longueur L bits et c'est ainsi que vous pouvez imaginer un échantillon de défi pour le distinguisher aurait été généré, si une corde uniformément aléatoire de longueur de 2L bits aurait été donnée comme le défi pour le distinguisher. Alors que dans l'expérience H1, les deux parties du défi, à savoir y1 et y2, sont générées en invoquant l'algorithme existant G sur les graines uniformément aléatoires s1 et s2 et en exécutant l'algorithme G indépendamment deux fois. Vous pouvez donc imaginer que cette expérience H1 est la version de l'expérience basée sur l'indistinction si le distinguisher aurait participé à l'expérience basée sur l'indistinction. Et l'échantillon que j'aurais donné à D aurait été généré par notre algorithme Gnew. Maintenant, notre objectif est de prouver que ces deux versions de l'expérience sont impossibles à distinguer sur le plan informatique, que je dénote par cette notation? ≈. Donc, cette notation signifie que ces 2 versions des expériences sont indiscernellement impossibles à distinguer et ce que je veux prouver ici, c'est que si mon algorithme existant G est effectivement un PRG sécurisé selon la notion d'expérience basée sur l'indistinction, alors avec une probabilité presque égale D aurait produit la même sortie dans l'expérience H0 ainsi qu'une expérience H1.Cela signifie que la probabilité de distinction ou l'avantage distinctif de mon distinguant pour tout temps polynomial est borné par une fonction négligeable. C'est ce que je veux prouver quand je dis que je veux prouver mon algorithme Gnew est un PRG sécurisé. Maintenant, il s'avère que nous ne pouvons pas prouver directement ou nous ne pouvons pas réduire directement la sécurité de l'algorithme Gnew à l'instance de la sécurité de l'algorithme existant G parce que l'algorithme G ne produit qu'un échantillon de bits de taille L, alors que dans l'algorithme Gnew vous appelez en fait votre algorithme existant G twice.Donc, pour prouver l'indistinction computationnelle de l'expérience H0 et H1, ce que je vais faire, c'est que je vais introduire une expérience intermédiaire que je dénote comme Hint et à un niveau très élevé, cette expérience intermédiaire est un peu intermédiaire entre H0 et H1. Cela signifie que, ici aussi, le distinguant se fera un échantillon constitué de 2 blocs de taille L bits, L bits, mais la différence ici est que la première partie de l'échantillon qui aurait été générée par l'exécution de l'algorithme G sur une entrée uniformément aléatoire. Alors que la seconde partie de l'échantillon qui aurait été générée par l'exécution d'un générateur vraiment aléatoire, et maintenant, ce que nous allons prouver est, nous prouverons 2 revendications différentes. La première revendication sera que si mon algorithme existant G est effectivement un PRG sécurisé, alors les deux expériences H0 et l'expérience Hint sont impossibles à distinguer sur le plan informatique. Cela signifie que tout écart de temps polynomial va générer les mêmes bits de sortie dans les deux versions de l'expérience qu'il soit H0 ou H1, sauf avec une probabilité négligeable, que je dénote par néglig1.De la même façon, je vais prouver que si mon algorithme existant G est un PRG sécurisé, alors mon expérience intermédiaire, Hint et H1 sont impossibles à distinguer sur le plan informatique du point de vue de n'importe quel modèle de temps polynomial. Cela signifie, avec une probabilité presque identique de n'importe quel temps polynomial, que le distinguisher va générer le même bit de sortie indépendamment du fait qu'il participe à l'expérience H1 ou s'il participe à l'expérience H2 sauf avec une fonction négligeable, que je dénote par néglig2.Maintenant, si je prouve ces deux affirmations, en additionnant ces 2 probabilités de distinction, je peux conclure que mon expérience H0 et H1 sont aussi indiscernellement impossibles à distinguer, à savoir la probabilité avec laquelle le distinguisher peut distinguer si elle participe à l'expérience H0 ou si elle participe à l'expérience H1 sera bornée par la sommation de 2 probabilités négligeables, et à partir de la propriété de fermeture de la fonction de probabilité négligeable, nous en sommes arrivés à la conclusion que la somme de 2 fonctions négligeables est également une probabilité négligeable. (Voir Diapositive Heure: 09 :22) Alors, prouverons la première réclamation. Cela signifie que nous voulons prouver que si G est un PRG sécurisé, alors aucun temps polynomial ne peut distinguer si elle participe à l'expérience H0 ou si elle participe à l'expérience Hint, sauf avec une certaine probabilité négligiblesuccess. L'intuition qui sous-tend cette affirmation ou la déclaration est que si nous avons un polynôme de temps de distinction qui peut distinguer de façon significative si elle participe à l'expérience H0 ou si elle participe à l'expérience Hint, alors en utilisant cette distinction nous pouvons concevoir un autre distinguisher qui peut distinguer un y1 uniformément aléatoire d'un pseudorandom y, et nous laisser formellement établir cette intuition. Donc, imaginez pour le moment que vous avez un distinguisher D qui peut distinguer si elle participe à une instance de l'expérience H0 ou si elle participe à une instance d'une expérience Hint.Now, en utilisant ce distinguisher, notre but est de concevoir un autre modèle de temps polynomial que je dénote par A dont le but est de distinguer un échantillon uniformément aléatoire généré par un algorithme G par rapport à un échantillon vraiment aléatoire de bits de taille L générés par un générateur vraiment aléatoire, non. Donc, l'algorithme A participe à une instance de mon indistinction basée sur la définition ou l'expérience pour le PRG où il sera lancé un défi y1 de L bitsand le défi pour l'algorithme A est de savoir si y1 est généré par l'algorithme G ou par un generator.Maintenant, ce que l'algorithme va faire, c'est l'algorithme va prendre l'aide de l'algorithme D,right. Avant d'entrer dans la façon dont l'algorithme A prend l'aide de l'algorithme D, permettez-moi de rappeler que, conformément à la syntaxe de notre expérience d'indistinction, la façon dont l'échantillon y1aurait été généré est la suivante. Le vérificateur de l'expérience basée sur l'indistinction aurait lancé une pièce, si la pièce avait la sortie 0, alors l'échantillon y1 est généré par un générateur vraiment aléatoire. Alors que si la pièce est 1, alors l'échantillon y1 est généré par l'exécution de l'algorithme G sur une entrée uniformément aléatoire. Le défi pour notre algorithme A est de savoir ce que b est exactement, si b = 0 ou si b = 1. Maintenant, ce que l'adversaire va faire, c'est qu'il va lui-même générer une chaîne uniformément aléatoire que je dénote par y2 de taille L bits et il produit un nouveau challenge ou un nouvel échantillon pour le distinguisher D en concaténant le défi y1 qui a été jeté à A avec l'échantillon y2 qu'il a généré uniformément au hasard.Maintenant, qu'est-ce qui se passe exactement ici? D'accord. Alors, faisons une pause pour un instant. Si vous voyez la façon dont l'adversaire A a fait le calcul ici, si l'échantillon pourquoi y1 aurait été généré uniformément de façon aléatoire, alors y1, y2 aurait considéré comme un défi que l'adversaire D aurait attendu en participant à l'expérience H0 parce que dans l'expérience H0 à la fois y1 et y2 sont générés uniformément au hasard.Cela signifie dans cette réduction, si l'échantillon y1 qui est lancé comme un défi pour l'adversaire est généré par l'exécution d'un générateur vraiment aléatoire, et s'il est concaténé par un échantillon vraiment aléatoire, un autre échantillon indépendant de bits de taille L, alors y1, y2 aurait considéré comme un défi que l'adversaire D aurait attendu en participant à l'expérience H0, à droite. D'autre part, si l'échantillon y1 qui est lancé comme un défi pour l'adversaire est généré par l'exécution d'un générateur de pseudorandom G, alors ce y1 concaténé avec un échantillon uniformément aléatoire y2 serait un défi pour le distinguant, ce que le distinguant aurait attendu en participant à une instance de l'expérience Hint. Parce que dans cette expérience intermédiaire, la première partie de l'échantillon est générée par l'exécution d'un générateur de pseudorandom, alors qu'une seconde partie de l'échantillon de l'échantillon est uniformément aléatoire. Maintenant, notre adversaire A ne sait pas s'il a effectivement transmis un échantillon selon l'expérience H0 ou s'il a transmis un échantillon selon l'expérimentateur au distinguisher. Il s'agit d'un distinguisher D qui peut en fait identifier si y1, y2 qu'il voit est généré par H0 ou par Hint. C'est ce que je veux dire quand je dis que nous avons un distinguisher qui peut distinguer de façon significative s'il participe à une instance de H0 par rapport à un exemple d'expérience Hint, non. Donc, quel que soit le cas basé sur l'échantillon y1, y2 qui est donné au distinguant, le distinguisher va produire un bit, par exemple, b ’, qui indique si l'échantillon est généré selon l'expérience H0 ou s'il a été généré par Hint.Now, en fonction de la sortie de l'algorithme D, ce qu'A va produire? Il va produire la même production que D pour produire. Cela signifie que si D dit que l'échantillon qu'il voit est généré par l'expérience H0, alors A identifie l'échantillon y1 comme s'il est généré par un générateur vraiment aléatoire, alors que si le distinguant D dit b ’ = 1, cela signifie que si l'échantillon y1, y2 est généré selon l'expérience intermédiaire, alors l'adversaire A dit que l'échantillon y1 est généré selon les termes de la pseudo-générale.Donc, calculons maintenant l'avantage distinctif de l'algorithme A, que nous avons construit à l'aide de l'élément de distinction existant D. Donc, calculons d'abord la probabilité que notre algorithme A produit ou étiquette uniformément échantillon aléatoire y1 comme résultat d'un générateur de pseudorandom. Cela signifie que nous voulons calculer la probabilité qu'une sortie b ’ = 1, même si b = 0, et la revendication, c'est exactement la même probabilité avec laquelle notre distinction D va produire b ’ = 1 dans l'expérience H0, et c'est parce que si b = 0, à droite, si b = 0, alors nous sommes dans le cas où y1 aurait été généré par un générateur vraiment aléatoire et que y1 concaténé par y2 aurait créé un échantillon pour D selon l'expérience H0 zéro. À savoir, le point de vue du distinguant aurait été exactement le même que celui qu'il aurait en participant à l'expérience H0, n'est-ce pas? Alors que la probabilité que notre algorithme A génère b ’ = 1 donné b = 1, cela signifie qu'il génère l'échantillon y1 car il identifie l'échantillon y1 comme étant la sortie d'un générateur de pseudo-andom, étant donné qu'il a effectivement été généré par un générateur de pseudorandom est exactement le même avec lequel notre distinction D, l'élément D existant aurait une sortie b ’ = 1 en participant à une instance de l'expérience Hint car si b = 1, c'est-à-dire l'échantillon de défi y1 pour A généré par un générateur de pseudorandom, alors cet exemple de pseudorandom généré par un échantillon vraiment aléatoire ressemblerait à un échantillon Que D s'attend à participer à une instance de l'expérience Hint.So, avec la probabilité que D ait une sortie b ’ = 1 dans l'expérience Hint, avec exactement la même probabilité que notre adversaire A va à la sortie b ’ = 1 donné b = 1. Donc, si vous considérez l'avantage distinctif de l'algorithme A que nous avons construit, c'est exactement le même avec lequel l'algorithme existant D peut distinguer l'expérience H0versus l'expérience H1.Donc, si le distinguisher existant peut distinguer significativement l'expérience H0 de l'expérience Hint, alors ce que nous avons montré est un algorithme A qui peut distinguer significativement un échantillon de pseudorandom généré par l'algorithme G d'un échantillon uniformément aléatoire, mais c'est une contradiction avec l'hypothèse que nous faisons, nous disons que l'algorithme existant G est un algorithme sécurisé PRG.Cela signifie, puisque l'algorithme existant G est un PRG sécurisé, l'avantage distinctif de l'algorithme A va être délimité par une probabilité négligeable, ce qui implique en outre que l'avantage distinctif de l'algorithme existant D va également être délimité par une probabilité négligeable. Ainsi, cela prouve notre première revendication. (Référez-vous à la diapositive: 18 :44) De la même façon, nous pouvons prouver que si l'algorithme existant G est sécurisé, alors aucun temps polynomial ne peut distinguer de façon significative une instance de l'expérience Hint de l'instance de l'expérience H1. Encore une fois, l'idée de preuve restera la même. Supposons pour le moment que vous avez un distinguisher existant qui peut distinguer l'expérience Hintfrom H1 une. En utilisant cela, nous concevons un autre distinguant A, qui peut distinguer un échantillon de pseudorandom de taille L bits d'un échantillon uniformément aléatoire de taille L bits.Donc, il participe à une instance de l'expérience basée sur l'indistinction, où il est donné un échantillon y2 qui est généré soit uniformément au hasard, soit il est généré par l'exécution d'un algorithme G avec une entrée uniformément aléatoire. Le but de l'adversaire A est de savoir si b = 0 ou b = 1. Maintenant, ce que le présent A va faire est de choisir une graine elle-même, qui est de taille 1 bits, et elle produit un échantillon de pseudorandom y1 et elle produit maintenant un échantillon de défi plus grand pour la distinction existante D par concaténation de l'échantillon de pseudorandom y1 avec l'échantillon de défi y2.Donc avant d'aller plus loin, vous pouvez clairement voir ici que si l'échantillon de défi y2 est uniformément aléatoire, alors un échantillon de pseudorandom y1 suivi d'un échantillon vraiment aléatoire ressemblerait à un échantillon que la D attend dans une instance de l'expérience Hint. Alors que si l'échantillon y2 est un échantillon de pseudorandom, alors un pseudorandom y1 concaténé avec un pseudorandom y2 créerait un échantillon pour D comme par une instance de l'expérience H1, drot.Donc, sur la base de la même idée que celle que nous utilisons pour prouver la revendication précédente, nous pouvons en fait montrer que la probabilité avec laquelle A pourrait distinguer si le défi y2 est pseudo-aléatoire ou vraiment aléatoire est exactement la même avec laquelle le distinguant D pourrait distinguer si elle participe à une instance de l'expérience Hint versus si elle participe à une instance de l'expérience H1. Ainsi, si l'avantage distinctif de l'algorithme G est non négligeable, alors l'avantage distinctif de notre algorithme A est non négligeable, mais c'est une contradiction avec l'hypothèse que notre algorithme G est pseudorandom. (Référez-vous à la diapositive: 21 :17) Donc, sur la base de ceci, le résumé de la preuve est le suivant. Nous avons en fait prouvé 2 revendications individuelles. Si l'algorithme existant G est un générateur de pseudorandom, alors aucun temps polynomial ne peut distinguer si elle participe à l'expérience H0 ou si elle participe à l'expérience Hint, sauf avec une fonction négligeable dire néglige1. De la même façon si l'algorithme existant est un PRG sécurisé, alors aucun distinguisher ne peut distinguer si elle participe à une instance de l'expérience Hint versus si elle participe à une instance de l'expérience H1, sauf avec une probabilité négligeable que je dénote par néglig2. Donc si je additionne ces 2 avantages distinctifs, j'obtiens que l'expérience H0et l'expérience H1 sont aussi indiscernellement impossibles à distinguer parce que la somme de 2 fonctions négligeables est également délimitée par une fonction négligeable. Cela signifie, si nous composons en fait l'algorithme existant G deux fois avec des entrées indépendantes, alors le nouvel algorithme est aussi un PRG sécurisé. (Référez-vous à la diapositive: 22 :27) Donc, allons-nous au cas général, c'est vrai. Le cas général était quand nous composions en fait l'algorithme existant G polynomial nombre de fois, et pour prouver que le nouvel algorithme est aussi un PRG sécurisé. En effet, nous créons 2 instances de l'expérience H0 et H1où H0 aurait réellement créé un échantillon de défi pour le distinguisher généré par l'exécution du générateur réellement aléatoire k temps indépendant, alors qu'une expérience H1 l'échantillon qui est donné au distinguisher est en fait généré par l'exécution de l'algorithme G k fois de façon indépendante.Notre but est de prouver qu'aucun temps polynomial ne permet de distinguer si elle participe à l'expérience H0 ou si elle participe à l'expérience H1. Pour prouver cette affirmation, nous devons à présent introduire le nombre polynomial d'expériences hybrides intermédiaires, à droite. À savoir, nous devons introduire des cas de k d'hybrides intermédiaires. Ainsi, le premier hybride intermédiaire sera presque identique à H0, sauf que la première partie du défi. En fait, le premier bloc de l'échantillon de contestation qui est donné au distinguant est en fait généré par l'exécution d'une instance d'un générateur de pseudorandom, alors que les blocs restants de l'échantillon de remise en question qui est donné à la distinction sont tous générés de façon aléatoire. Donc, c'est la seule différence entre l'expérience H0 et Hint1 et nous pouvons prouver en utilisant une stratégie similaire que nous avons utilisée dans la revendication précédente de l'exemple précédent que si l'algorithme G est un PRG sécurisé, alors le distinguisher D ne peut distinguer une instance de l'expérience H0 par rapport à une instance de l'expérience Hint1. De la même façon, la deuxième expérience hybride intermédiaire sera presque identique à la première expérience hybride Hint1. La différence sera que la deuxième partie ou le second bloc de l'échantillon de défi qui est donné au distinguisher est maintenant généré par l'exécution d'un générateur de pseudorandom et que les blocs restants (k – 2) du défi sont générés de manière aléatoire, non. Encore une fois, nous pouvons prouver que si l'algorithme existant G est un PRG sécurisé, alors aucun temps polynomial ne peut distinguer une instance de l'expérience Hint1 d'une instance de l'expérience Hint2 .Comme cela, le (k-1) e hybride intermédiaire sera comme suit. Ici, le premier (k – 1) blocs de l'échantillon de défi qui est donné au distinguisher est généré en exécutant (k-1) des instances indépendantes de l'algorithme G et le dernier bloc de l'échantillon de défi est généré uniformément au hasard et nous pouvons prouver que si mon algorithme G est sécurisé PRG, alors aucun temps polynomial ne peut distinguer une instance de cette expérience hybride thintermédiaire (k-1) de (k – 2) l'expérimentateur hybride intermédiaire. Enfin, nous prouverons que si l'algorithme existant G est sécurisé, alors aucun temps polynomial ne peut distinguer l'un de l'autre. L'expérience H1 à partir d'une expérience de l'expérience hybride thintermédiaire (k-1). Donc, si je résume maintenant ces avantages distinctifs de l'adversaire, ce que j'ai fini par montrer, c'est que l'avantage distinctif de tout écart de temps polynomial pour distinguer une instance de l'expérience H0 d'une instance de l'expérience H1 est borné par une fonction k fois négligeable. Puisque k est une fonction polynomiale, k fois la fonction négligeable va aussi être une fonction négligeable, ce qui prouve que mon algorithme Gnew est aussi un PRG sécurisé. (Voir la diaporama: 26 :18) Donc maintenant, regardons dans l'exemple final de cette conférence. Nous envisageons maintenant une autre opération que nous pouvons effectuer sur PRG et obtenir un PRG sécurisé. Donc, ici, on me donne un PRG sécurisé arbitraire et je construis maintenant un nouveau PRG G ’ où la sortie de G ’ est simplement obtenue en exécutant l'algorithme G, qui est l'algorithme existant et en inversant simplement la sortie de l'algorithme existant G, pas vrai. Ma prétention est que si votre algorithme existant G est un PRG sécurisé, alors ce nouvel algorithme G ’ est aussi un PRG sécurisé. Encore une fois, la preuve sera la réduction et l'intuition derrière le groupe de réduction est la suivante. Au contraire, supposons que votre nouvel algorithme G ’ n'est pas un algorithme sécurisé. Cela signifie, supposons qu'il existe un algorithme polynomial time distinction qui peut distinguer la sortie de G ’ d'un résultat d'un générateur vraiment aléatoire, puis en utilisant cet algorithme nous pouvons aussi en fait concevoir un distinguisher polynomial qui peut distinguer un résultat d'un algorithme G d'un résultat d'un générateur vraiment aléatoire, ce qui sera une contradiction. L'intuition derrière cette réduction est que l'inverse de n'importe quelle chaîne uniformément aléatoire est aussi une chaîne uniformément aléatoire et l'inverse d'une chaîne de pseudorandom est aussi une chaîne de pseudorandom. L'idée qui sous-tend une réduction est la suivante. Donc, supposons par exemple que vous avez un distinguisher existant la DG ’ pour le nouvel algorithme pour le G ’ nous avons construit et utilisé cet algorithme Je veux construire une autre DG de distinction de temps polynomial pour mon algorithme existant G. Donc, la DG de distinction est donnée un échantillon, qui est soit généré uniformément au hasard, soit en exécutant l'algorithme G. Ce que cet algorithme va faire, c'est qu'il va simplement produire un nouvel échantillon pour mon algorithme DG ’ en inversant simplement les bits de l'échantillon de défi y. Donc, avant d'aller plus loin dans la réduction, le point ici est que si l'échantillon y est en fait un échantillon uniformément aléatoire, alors c'est le nouvel échantillon Y. D'un autre côté, si l'échantillon y est un échantillon de pseudorandom, alors c'est le nouvel échantillon Y. Cela signifie, quelle que soit la probabilité que mon algorithme existant DG ’ puisse distinguer un échantillon vraiment aléatoire Y d'un échantillon de pseudorandom Y, avec presque la même probabilité, ma nouvelle DG d'algorithme va distinguer un échantillon aléatoire et uniforme d'un échantillon aléatoire Y, c'est en gros l'idée derrière une réduction, et je laisse les détails complets de l'échantillon. La réduction pour vous. Fondamentalement, nous finissons par montrer que l'avantage distinctif de mon algorithme DG est exactement le même que l'avantage distinctif de la DG d'algorithme existante ’, right.So, si cela s'avère si mon algorithme existant G est un PRG sécurisé, alors c'est le nouvel algorithme G ’ .Donc, cela m'amène à la fin de cette conférence. Juste pour résumer, dans cette conférence, nous avons vu une nouvelle primitive appelée générateur de pseudorandom, qui est un algorithme déterministe et l'objectif du générateur de pseudorandom est d'étendre son entrée et de générer une sortie qui est significativement plus grande que son entrée. Plus important encore, l'objectif de la pseudorandom generatoris est de produire un échantillon de sortie qui semble presque identique à une sortie qui aurait été générée par un générateur vraiment aléatoire. Nous avons vu diverses définitions équivalentes du générateur de pseudorandom, et nous avons aussi vu comment nous pouvons composer avec des générateurs de pseudorandom polynomial nombre de temps pour obtenir un nouveau générateur de pseudorandom. J'espère que vous avez apprécié cette conférence. Je vous remercie.