Loading
Notes d'étude
Study Reminders
Support
Text Version

Fonctions 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-14Pseudo Random Functions PRFsHello everyone, welcome to lecture 13. (Consulter la diapositive: 00 :31) Le plan de cette conférence est le suivant. Nous allons introduire un bloc de construction très important pour la cryptographie à clé symétrique, à savoir une fonction pseudo-aléatoire. Et plus tard nous verrons que la fonction pseudo-aléatoire agit comme un bloc de construction fondamental pour la conception de nombreuses belles primitives symétriques symétriques. Nous discuterons également des variantes de la fonction pseudo-aléatoire, à savoir la permutation pseudo-aléatoire et la forte permutation pseudo-aléatoire. Nous verrons comment construire des générateurs pseudo-aléatoires à partir d'une fonction pseudo-aléatoire. (Voir Heure de la diapositive: 01 :01) Donc, commençons notre discussion sur la fonction pseudo-aléatoire. Sur un très haut niveau, une fonction pseudo-aléatoire est un algorithme déterministe avec deux entrées et un seul outputwhere et. Et nous supposerons que la taille de la clé est n et n est un paramètre de sécurité. C'est pourquoi nous appelons souvent la fonction F comme une fonction clé car elle sera exploitée par une clé. En pratique, la taille de n, l et L peut être très et plus tard sur nous allons voir différentes instanciations de fonction pseudo-aléatoire. En effet n, l, L all sont différents, mais asymptotiquement tout doit être une fonction polynomiale de votre paramètre de sécurité. Maintenant, comment nous allons utiliser cette fonction pseudo-aléatoire. Ainsi, chaque fois que nous concevons des primitives cryptographiques, la façon dont nous utilisons cette pseudo-fonction aléatoire est la suivante: au début des instanciations de la primitive cryptographique, qui utilise cette fonction F, l'expéditeur ou le récepteur va générer une clé uniformément aléatoire. Et d'une manière ou d'une autre, il sera établi avec la partie réceptrice, et il ne serait pas connu de l'agresseur. Une fois la clé fixée, nous n'allons pas changer la clé tout au long de cette session ou tout au long de cette instanciation. La clé restera la même. Maintenant, une fois que nous avons fixé la clé, où k va être corrigé et il ne serait pas connu de l'attaquant. C'est ainsi que nous allons utiliser une fonction pseudo-aléatoire. Maintenant, quelle est exactement la propriété de sécurité que nous avons besoin de la fonction pseudo-aléatoire. Et de manière informelle, nous avons besoin de ce qui suit: si la clé k est inconnue, et uniformément choisie au hasard à partir du domaine de l'espace clé, alors nous avons fondamentalement besoin que le comportement ou la sortie de la fonction clé de Fk devrait presque ressembler à la sortie d'une fonction vraiment aléatoire à. Donc, rappelez-vous, une fonction vraiment aléatoire est une fonction sans clé. Donc, ce qui veut en gros, c'est que la fonction à clé Fk, une fois que la clé a été choisie au hasard, son comportement devrait presque ressembler au comportement d'une fonction pseudo-aléatoire. (Voir Heure de la diapositive: 03 :53) Donc, allons un peu plus loin dans ce que je veux dire exactement par la déclaration formelle. Imaginez que vous avez une fonction vraiment aléatoire qui est une fonction unkeyed, elle n'a pas de clé, elle prend juste une entrée de taille l bits et elle produit une sortie de taille L bits. Donc, il est facile d'imaginer le comportement d'une fonction vraiment aléatoire comme suit: ce qui fait vraiment une fonction aléatoire est une entrée de taille x, et elle produit une sortie de bits de taille L, et vous pouvez imaginer que fondamentalement, cette fonction vraiment aléatoire tient une table composée de 2lrows, où en gros les magasins de première ligne. Donc, chaque fois que cette fonction vraiment aléatoire reçoit une entrée x, ce qui fait en gros c'est qu'elle vérifie en interne s'il y a déjà une entrée pour la valeur de cette fonction vraiment aléatoire à l'entrée x. Si elle n'est pas là, alors remplissez cette ligne, à savoir F (x) par. Pour les futurs appels de ces fonctions vraiment aléatoires a dit que y être la sortie de cette fonction vraiment aléatoire sur l'entrée x. D'autre part, si la valeur x qui a été transmise, vous avez déjà une entrée correspondant à cette clé x dans cette table puis juste passer la valeur qui est stockée dans cette ligne correspondante comme la sortie y. C'est ainsi que vous pouvez imaginer le comportement d'une fonction vraiment aléatoire. L'important ici est que puisque cette fonction est une fonction vraiment aléatoire, chaque rangée ici est une chaîne indépendante de bits de longueur L. Cela signifie et sont indépendants les uns des autres, pour n'importe quel autre. Cela signifie que s'il existe un algorithme, qui a été notyet vu la valeur de la fonction vraiment aléatoire sur certaines entrées x, il ne peut pas prédire quelle est exactement la valeur de la fonction sera pour cette entrée x, sauf pour deviner la sortie, et la devine sera couronnée de succès avec probabilité 1/2L. En dehors de cela, il n'y a aucun moyen de prédire le résultat de la fonction vraiment aléatoire sur une entrée x. Et cela tient même si cet algorithme qui essaie réellement de prédire le résultat de cette fonction vraiment aléatoire sur l'entrée x a déjà vu la sortie de cette fonction vraiment aléatoire sur plusieurs valeurs x précédentes, qui pourraient être liées à ces nouvelles valeurs x. Mais c'est parce que chaque rangée dans le tableau de cette fonction vraiment aléatoire est indépendante l'une de l'autre. La propriété de sécurité que nous avons besoin d'une fonction pseudo-aléatoire est qu'une fois que nous réparons la clé en sélectionnant la clé uniformément au hasard, alors cette fonction à clé devrait également avoir les propriétés similaires sauf avec une probabilité négligeable. (Voir Diapositive Heure: 07 :02) Donc, ce que cela signifie exactement, c'est que sur votre côté gauche vous avez une fonction à clé Fk, où la description de la fonction F est connue du public. Je souligne que la description de la fonction est connue du public et ce qui n'est pas connu est essentiellement la valeur de la clé. Sur le côté droit, vous avez une fonction vraiment aléatoire qui consiste essentiellement en 2Lrows chaque entrée constituée d'une chaîne uniformément aléatoire de longueur L bits. Et quand je dis que ma fonction F est une fonction pseudo-aléatoire, ce que je veux dire, c'est qu'il n'existe pas de test statistique de temps polynomial ou d'algorithme statistique qui peut distinguer de façon significative une sortie de l'algorithme Fk de la sortie de cette fonction vraiment aléatoire. Cela signifie que, si notre distinction ou le test statistique est essentiellement donné aux résultats de la fonction Fk ou de la sortie de la fonction aléatoire sur plusieurs entrées de l'adversaire, le choix de l'adversaire. Du point de vue du distinguant, ces extrants pourraient être aussi susceptibles de provenir de la fonction Fk qu'il est susceptible de venir de cette fonction vraiment aléatoire. Maintenant, avant d'aller plus loin, cette condition est similaire à la façon dont nous avons défini la notion de pseudo-générateur aléatoire. Alors, rappelez-vous dans le pseudo-générateur aléatoire que la sécurité est définie en disant qu'il n'existe pas de test statistique, qui lorsqu'un échantillon ne peut pas distinguer si cet échantillon est généré en exécutant un générateur pseudo-aléatoire, ou en exécutant un générateur vraiment aléatoire. Dans cette expérience, ce distinguisher n'a reçu qu'un seul échantillon parce que notre pseudo-générateur aléatoire est une seule fonction d'entrée. Pour chaque appel du pseudo-générateur aléatoire, l'échantillon va être différent car la clé du pseudo-générateur aléatoire va être différente. Mais dans le contexte d'une fonction pseudo-aléatoire, la façon dont nous allons utiliser une fonction pseudo-aléatoire dans l'application du monde réel est que la clé sera corrigée une fois pour tous au début de la session. Et puis les entrées x vont être variées. Et chaque appel de la fonction sera avec la même clé. (Voir Diapositive Heure: 09 :14) Donc ce que nous allons faire maintenant, c'est que dans notre définition formelle, fondamentalement l'adversaire va recevoir de nombreux échantillons, et il doit distinguer si ces échantillons sont générés en exécutant une fonction à clé Fk ou en exécutant une fonction vraiment aléatoire. Alors, voyons ce que sont exactement les détails formels. On vous donne la description d'une fonction publique, et l'expérience que nous appelons une expérience d'indistinction contre un PRF par rapport à un algorithme de distinction par rapport à la fonction F et l est le paramètre de sécurité. Les règles des jeux sont les suivantes: le distinguisher est autorisé à demander la sortie de fonction à plusieurs entrées x de son choix, et il peut demander à ses requêtes de façon adaptative ce qui signifie qu'il peut d'abord demander la sortie de fonction sur l'entrée x1. Ensuite, sur la base de la réponse, il peut décider de ce qui devrait être x2. Et ensuite basé sur la réponse, il peut décider de ce qui devrait être x3, et ainsi de suite. Nous ne mettons absolument aucune restriction sur le type de demandes de renseignements qui sont à l'ordre du jour. Maintenant, une fois que le distinguant soumet ses requêtes, le challenger ici doit trouver la réponse, c'est-à-dire la sortie des fonctions à ces entrées. Et la façon dont le challenger aurait préparé cette réponse est la suivante: en gros, le challenger va lancer une pièce uniformément aléatoire, qui sera soit en sortie 0 ou 1 avec probabilité 1/2. Si la pièce toss est 0, alors toutes ces réponses y1, .., yq sont essentiellement générées en exécutant une fonction vraiment aléatoire sur ces entrées x. D'une manière plus détaillée, toutes ces cordes y sont fondamentalement indépendantes les unes des autres et chacune d'elles est fondamentalement une chaîne de bits de longueur uniformément aléatoire. D'autre part, si le jeu de pièces de l'challenger est de 1, alors ces sorties y sont essentiellement la sortie d'une fonction à clé Fk, où la clé est choisie uniformément au hasard par le challenger. Et maintenant, le défi pour le distinguisher est de savoir comment exactement ces réponses y1, .., yq sont générées, qu'elles soient générées par le mécanisme 0 ou si elles sont générées par le mécanisme 1. C'est un défi pour notre distinction. Donc, distinguisher dans ce cas les sorties b ’ ce qui va être un peu qui dit fondamentalement si elle pense qu'un échantillon y1, .., yq sont générés par les mécanismes 0 ou par le mécanisme 1. Et notre définition de sécurité est que nous disons que la fonction F est une fonction pseudo-aléatoire si pour chaque algorithme de temps polynomial probabiliste D participant à cette expérience, il existe une fonction négligeable telle que la probabilité que le distinguant identifie correctement le libellé ou la nature des échantillons y1, .., yq est délimité par ½ ; + negl (n). Encore une fois, la probabilité est prise ici par rapport au choix aléatoire du challenger et aux requêtes aléatoires du distinguant. Une autre formulation équivalente de la même définition est que nous disons que la fonction F est un PRFif l'avantage distinctif de notre distinction est borné par une fonction négligeable. Cela signifie qu'il importe peu que b = 0 ou b = 1, ce qui signifie qu'il importe peu que les échantillons y soient générés par des fonctions réellement aléatoires ou qu'ils soient générés par une fonction pseudo-aléatoire. Dans les deux cas, l'élément de distinction devrait produire la même sortie, par exemple, b ’ = 1, sauf avec une probabilité négligeable. Et encore une fois, nous pouvons prouver que si nous avons une fonction pseudo-aléatoire qui satisfait la première condition, alors elle l'applique aussi satisfait la seconde condition et vice versa. Donc, selon notre commodité, nous pouvons utiliser l'une ou l'autre de ces deux définitions. C'est donc la définition d'une fonction pseudo-aléatoire. Fondamentalement, l'intuition de cette expérience est que nous donnons à notre distinguant un accès oracle à la fonction où la fonction est soit une fonction vraiment aléatoire, soit une fonction à clé. Et le distinguisher doit distinguer si elle interagit avec un oracle de fonction vraiment aléatoire ou si elle interagit avec une fonction à clé oracle. Cette définition de la sécurité exige que, sauf avec une probabilité négligeable, il ne soit pas possible de distinguer. Remarquez qu'ici, nous sommes tenus d'avoir la limite supérieure de la probabilité de succès de l'adversaire par ½ ; + negl (n). Nous ne pouvons pas mettre une définition disant qu'une probabilité de succès du distinguisher devrait être 0 parce qu'il est toujours possible que l'auteur de distinction puisse deviner qu'il interagit avec les termes TRF ou PRF et qu'avec la moitié de la probabilité il peut effectivement identifier correctement ou la probabilité de la moitié de sa supposition pourrait être correct.Donc, nous ne pouvons jamais mettre une condition selon laquelle la probabilité de succès du distinguisher devrait être 0. L'avantage négligeable supplémentaire est essentiellement dû au mal nécessaire associé au fait que nous sommes dans le monde computationnel. (Référez-vous à la diapositive: 14 :25) Donc, voyons maintenant, si c'est facile ou si c'est facile ou difficile de construire une fonction pseudo-aléatoire. Alors, imaginez que je conçerais une fonction F comme suit et pour la simplicité, je suppose que la longueur de clé et la longueur de bloc et la longueur de sortie sont de même taille, c'est-à-dire des chaînes de bits et la façon dont la sortie de la fonction est définie. C'est la façon dont la production est calculée. Notre but est de prouver ou de réfute si cette fonction est une fonction pseudo-aléatoire. En fait, nous voulons réfute que cette construction n'est pas un FPR. Et pour cela, nous voulons essentiellement discuter de savoir si, en effet, les résultats de cette fonction F vont produire des sorties pseudo aléatoires une fois que nous réparons la clé. Et si vous allez un peu plus loin dans l'algorithme, vous pouvez clairement voir le fait suivant: si nous avons une fonction vraiment aléatoire de mappage de n bits cordes à n cordes, alors la sortie de la fonction vraiment aléatoire sur 2 entrées différentes x1 et x2 sera complètement indépendante l'une de l'autre. D'autre part, pour la fonction de ce que nous étudions,, pour n'importe quel, cela signifie que vous avez maintenant un test qui sera toujours transmis ou qui sera toujours pour les échantillons qui sont générés par la fonction Fk. Et vous avez un test, le même test peut ne pas toujours être applicable pour les échantillons générés par une fonction vraiment aléatoire. Donc, cela nous donne fondamentalement une intuition pour concevoir un distinguisher qui peut distinguer le résultat de cette fonction F du résultat d'une fonction vraiment aléatoire. Donc, voici l'exemple du distinguisher: il demande essentiellement la valeur de la fonction à l'entrée x1, x2 qui sont différentes. En réponse, le challenger répond avec les sorties y1 et y2. La façon dont il est y1 et y2 aurait été générée selon le jeu d'indistinction du PRF est comme suit: le challenger aurait essentiellement lancé une pièce si la pièce toss est 0 alors y1 et y2 sont des chaînes de n bit aléatoires. Alors que, si la pièce toss est 1 puis y1 et y2 les résultats de la fonction à clé Fk pour la clé uniformément aléatoire connue uniquement au challenger. Et maintenant, le distinguisher peut agir intelligement et fondamentalement distinguer si y1 et y2 sont générés par une fonction vraiment aléatoire ou une fonction pseudo-aléatoire en effectuant simplement ce test. Il vérifie si x1 et x2 leur XOR est le même que le XOR de y1 et y2. Si c'est le cas, alors il dit que les échantillons y1 et y2 sont générés par le mécanisme b = 1, c'est-à-dire qu'il soumet b ’ = 1. Alors que si le test échoue et qu'il est indiqué, les échantillons y1 et y2 sont générés par le mécanisme 0, à savoir b ’ = 0. Alors, analysons quel est l'avantage distinctif de cette distinction particulière. Donc, d'abord, analysons quelle est la probabilité que notre distinguant marque correctement les échantillons y1 et y2 générés par une fonction pseudo-aléatoire, en effet, étant les échantillons d'une fonction pseudo-aléatoire, à savoir le pr [ D outputs b ’ = 1 / b = 1 ]. Je prétend que cette probabilité est égale à 1. Parce que si en effet b = 1, c'est un cas, les échantillons y1 et y2 sont en fonction des sorties d'une fonction pseudo-aléatoire. Et dans ce cas, cette condition, la vérification que l'adversaire ou le distinguisher se produit va toujours passer. C'est pourquoi la probabilité 1, si b = 1, la stratégie de l'élément de distinction sortiront effectivement b ’ = 1,Par contre, calculons la deuxième probabilité que ce qui est la probabilité que notre distinction entre incorrectement des échantillons vraiment aléatoires y1 et y2 étant les échantillons d'une fonction pseudo-aléatoire. Eh bien, si b = 0, cela signifie que nos échantillons y1 et y2 sont indépendants l'un de l'autre. Ensuite, la seule façon dont le distinguant peut toujours générer b ’ = 1 est que pour uniformément aléatoires y1 et y2this condition cales ou en d'autres termes, le pr [ D output b ’ = 1/b = 0 ] = 1/2n.So qui nous donne l'avantage distinctif de l'élément distinctif que nous avons conçu. Et si vous prenez la différence absolue, elle est presque égale à 1 qui fait avec presque 100% de probabilité. Si n devient plus grand, alors ce 1 – 1/2nquasiment devient 1. C'est pourquoi avec une probabilité de presque 100%, un distinguisher peut distinguer le résultat de la fonction clé F de la sortie d'une fonction vraiment aléatoire. Et c'est pourquoi cette fonction F n'est pas la fonction pseudo-aléatoire. Cela signifie que la conception d'une fonction pseudo-aléatoire est effectivement une tâche difficile. Nous verrons les constructions candidates plus tard. (Référez-vous à la diapositive: 19 :56) Maintenant, définissons simplement d'autres variantes de fonctions pseudo-aléatoires avec des propriétés plus fortes et des garanties de sécurité. Donc la première variante est appelée la permutation pseudo-aléatoire, qui est aussi connue sous le nom de code de chiffrement. Et là encore, nous avons une fonction clé F. La seule différence ici est que la fonction clé Fk devrait être maintenant une bijection,. C'est la seule différence. Informellement, la propriété de sécurité dont nous avons besoin ici est que nous avons besoin qu'une fois que nous fixons la clé en sélectionnant une clé uniformément aléatoire, et que la clé n'est pas connue de l'attaquant ou d'un distinguant. Ensuite, aucune distinction de temps polynomial ne permet de distinguer le comportement de sortie ou la nature de cette fonction clé Fk d'un mappage de bijection vraiment aléatoire des chaînes de bits L à des chaînes de bits de L, qui peuvent à nouveau être modélisées comme une expérience d'indistinction. (Référez-vous à la diapositive: 20 :53) Il s'agit donc d'une expérience d'indistinction que nous appelons l'expérience de l'indistinction du PRP et nous avons une bijection ici, bijection à clé. Nous voulons saisir l'intuition qu'aucun distinguisher ne devrait être en mesure de distinguer le comportement de cette bijection à clé d'une bijection véritablement aléatoire. Les règles des expériences sont donc les suivantes: les requêtes de distinction pour plusieurs entrées x de son choix et en réponse le challenger renvoie les réponses. Les réponses sont préparées en tirant l'une ou l'autre des règles suivantes: elle lance une pièce et si la pièce est 0, alors tous ces échantillons y1, .., yq sont fondamentalement générés en exécutant une permutation vraiment aléatoire. Si le tirage de la pièce est égal à 1, tous ces échantillons sont générés en exécutant la fonction à clé F sur une clé uniformément aléatoire qui n'est pas connue du distinguisher. Le défi pour le distinguisher est de savoir quelle est exactement la façon dont les échantillons sont générés. Cela signifie qu'il doit générer un bit et notre définition de sécurité est que nous disons que la bijection par clé F est un PRP, si la probabilité que tout écart polynomial puisse identifier correctement la nature de l'échantillon est délimité par ½ ; + negl (n). Donc, en substance, tout est le même que pour le cas de pseudo-fonction aléatoire, la seule différence est que nous sommes maintenant fondamentalement dans ce cas de fonction PRP est maintenant une bijection. (Référez-vous à la diapositive: 22 :34) Il est donc intéressant de voir la relation entre ces deux primitives pseudo-aléatoires et pseudo-aléatoires. Donc, sur votre partie gauche, vous avez une fonction pseudo-aléatoire. La différence ici est une fonction, c'est-à-dire la longueur d'entrée, la longueur de bloc et la longueur de sortie peuvent être différentes. Alors que dans le cas de la permutation pseudo-aléatoire, c'est l'abijection. Cela signifie que, dans le cas de fonctions pseudo-aléatoires, il pourrait s'agir d'un grand nombre d'une fonction alors que dans le cas d'une permutation pseudo-aléatoire, il s'agit d'un mappage d'un à un. Étant donné que notre FPR ne peut pas être une bijection, il est facile de voir qu'un PRF peut ne pas être un PRP. Qu'en est-il de l'autre? Fait intéressant, nous pouvons prouver que si la taille de la sortie L est supérieure à l, ou en termes plus génériques, si la taille de la sortie est une fonction polynomiale du paramètre de sécurité n, alors nous pouvons voir une permutation pseudo-aléatoire comme une fonction pseudo-aléatoire. Et l'intuition de cette affirmation est la suivante: nous imaginons qu'on nous donne une permutation à clé. Donc, ce Fk est une bijection à clé. Et comme c'est un PRP sécurisé qui signifie qu'aucun temps polynomial ne peut distinguer l'autre et l'interaction avec cette fonction clé Fk d'une bijection vraiment aléatoire et sans clé, c'est-à-dire que ces primitives Fk et FTRP sont computationnellement indistinguishable.Maintenant, si nous comparons une fonction vraiment aléatoire de cartographie des chaînes de bits à des chaînes de bits de L, comment exactement elle va être différente d'une permutation vraiment aléatoire, la seule différence entre une fonction vraiment aléatoire et une permutation vraiment aléatoire et sans clé est qu'une fonction n'a pas besoin d'être une bijection. Cela signifie qu'il y a des risques de collisions, ce qui signifie qu'il pourrait s'agir d'un grand nombre de fonctions où plusieurs entrées x pourraient vous donner la même production y. Considérant que, dans le cas d'une permutation vraiment aléatoire, il n'y a pas de risque de collision. Ainsi, la seule façon pour n'importe quel distinguisher de distinguer la fonction inkeyed vraiment aléatoire de cette Fk bijection à clé est la suivante. Si c'est le cas, notre distinguisher interagit avec une fonction vraiment aléatoire et si tel est le cas, que certaines de ses requêtes vous donnent la même sortie et qu'elle peut clairement identifier qu'elle interagit avec une fonction vraiment aléatoire. Parce que si elle interagit avec ce Fk bijection, les collisions ne vont pas se produire. Cela signifie que nous pouvons dire que conditionnés au fait que nos demandes de distinction ne vont jamais conduire à une collision, alors l'interaction de notre distinction avec Fk et FTRF est presque la même que si le distinguisher interagit avec Fk contre FTRP et que notre fonction Fk est une permutation à clé. Nous savons que cette interaction est impossible à distinguer sur le plan informatique. Donc, la condition de l'événement à notre distinguisher n'est pas de faire des collisions avec ses requêtes, l'interaction de notre distinguisher avec la fonction vraiment aléatoire et inkeyed Fkare de bijection à clé va presque être identique. La question est maintenant de savoir quelle est la probabilité que le distinguisher se trouve en collision en effectuant des requêtes aléatoires à l'aide d'une fonction vraiment aléatoire.S'il fait q requêtes aléatoires puis en utilisant un résultat bien connu, que nous appelons le paradoxe de l'anniversaire, que nous allons discuter plus rigoureusement dans le contexte de la fonction de hachage, nous pouvons prouver que les chances d'avoir une collision peuvent être délimitées par la probabilité q2 /2L. Et c'est pourquoi si votre L est une fonction polynomiale du paramètre de sécurité n, alors clairement, il s'agit d'une quantité négligeable. Cela signifie que les risques de collision sont négligeables. Et c'est la raison pour laquelle nous pouvons dire, ou nous pouvons traiter le Fk bijection par clé aussi comme une fonction pseudo-aléatoire. C'est donc la relation entre des fonctions pseudo-aléatoires et des permutations pseudo-aléatoires. (Référez-vous à la diapositive: 27 h) Maintenant, voyons la dernière variante de fonctions pseudo-aléatoires que nous appelons une forte pseudo-permutation aléatoire ou SPRP, qui est une sorte particulière de permutation pseudo-aléatoire. Et en gros, ici nous avons besoin que le Fk bijection à clé ne puisse être distingué d'une permutation vraiment aléatoire, même si le distinguisher obtient un accès oracle à l'inverse de la permutation, ce que je veux dire par ce qui est démontré dans ce expérimentateur. Et ici le distinguisher donne maintenant accès ou réponse pour 2 types de requêtes. Il a un accès oracle aux valeurs des permutations, et il a aussi un accès oracle à l'inverse de la permutation. Ce que je veux dire par cela, c'est qu'il peut demander la valeur des permutations à plusieurs x entrées de son choix et en réponse, il récuperait les sorties y correspondantes, et il est également autorisé à demander l'inverse de la permutation de plusieurs valeurs y de son choixet voir les valeurs de x correspondantes. Et la façon dont le challenger aurait répondu est la suivante, il aurait lancé une pièce uniformément aléatoire si le toss de la pièce est 0, alors toutes ces requêtes sont réponsantes en évaluant une permutation vraiment aléatoire. Cela signifie que toutes ces valeurs x sont évaluées en fonction de cette permutation vraiment aléatoire. Et toutes ces requêtes inverses sont aussi réponds en interroant l'inverse de la permutation vraiment aléatoire correspondante. D'autre part, si la pièce toss b = 1, alors toutes ces valeurs y et toutes ces valeurs inverses sont calculées en exécutant la fonction keyed Fk et l'inverse de cette fonction clé Fk. Et le défi pour le distinguisher, comme d'habitude, est de déterminer s'il a interagi avec l'oracle qui représente une permutation vraiment aléatoire ou s'il est interagi avec un oracle à clé. Notre définition de la sécurité est que la fonction F est une permutation pseudo-aléatoire forte si aucun temps polynomial ne peut identifier correctement la nature de son oracle, sauf avec la probabilité ½ ; + negl (n) ou la mettre en d'autres termes, que l'avantage distinctif de notre distinguisher doit être délimité par une quantité négligeable. Il s'avère que si nous avons une forte permutation pseudo-aléatoire, alors par définition, c'est aussi une permutation pseudo-aléatoire, et nous pouvons donner des constructions où la construction sera une pseudo-permutation aléatoire. Cela signifie qu'il ne sera sécurisé que lorsque l'adversaire aura accès aux requêtes d'oracle pour la sortie de fonction. Mais il ne s'agit peut-être pas d'une forte permutation pseudo-aléatoire qui signifie, dès que nous fournissons au distinguisher l'accès à l'oracle inverse que l'adversaire peut distinguer. Cela signifie que la forte permutation pseudo-aléatoire est plus primitive que la pseudo-permutation aléatoire. (Référez-vous à la diapositive: 30 :01) Maintenant, permettez-moi de terminer cette conférence en donnant un exemple de la façon de construire un générateur pseudo-aléatoire à partir d'une fonction pseudo-aléatoire. Alors imaginez que vous vous êtes donné un FPR sécurisé. Maintenant, en utilisant ceci je peux construire un générateur pseudo-aléatoire G, .Et en gros, la façon dont cet algorithme fonctionne est le suivant: il prend la graine k pour l'algorithme G et crée le k pour la fonction pseudo-aléatoire F. Et la fonction pseudo-aléatoire F est maintenant évaluée à des entrées connues publiquement 1 2 3 jusqu'à t. Cela signifie que les entrées de bloc qui sont utilisées à l'intérieur de cet algorithme G sont connues publiquement qu'elles sont de 1 à jusqu'à t, c'est seulement la clé qui ne sera pas connue du distinguant. Et chaque invocation de cette fonction F est avec la même clé, qui est en fait l'entrée de nos pseudo-générateurs aléatoires. Et la sortie du pseudo-générateur aléatoire est essentiellement la concaténation des sorties individuelles qui sont en train d'obtenir en exécutant les instances t de la fonction clé Fk, c'est la façon dont notre pseudo générateur aléatoire va être opéré. Maintenant nous voulons prouver que si la fonction clé Fk est un PRF sécurisé selon notre notion d'indistinction, alors l'algorithme G que nous avons construit est aussi un PRG sécurisé. Selon le jeu d'indistinction PRG fourni, le nombre de fois où nous avons invoqué la fonction pseudo-aléatoire Fk, à savoir t, qui est une fonction polynomiale du paramètre de sécurité, pour prouver cela, nous devons d'abord comprendre notre intuition. Nous considérons en gros une autre version de l'algorithme G, que j'appelle GTRG, où chaque instance de fonction à clé Fk est remplacée par une instance d'une fonction vraiment aléatoire de mappage des chaînes de bits vers les chaînes de bits de L. Nous avons introduit le concept de fonction pseudo-aléatoire ; nous avons vu la définition. Et nous avons introduit diverses variantes de fonctions pseudo-aléatoires telles que la permutation pseudo-aléatoire, une forte permutation pseudo-aléatoire, et nous avons vu comment construire un générateur pseudo-aléatoire sécurisé à partir d'une fonction pseudo-aléatoire sécurisée. Merci !