Loading
Notes d'étude
Study Reminders
Support
Text Version

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 (ancien) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology – BangaloreLecture – 8Pseudorandom Generators (Référez-vous à la diapositive: 00 :30) Bonjour à tous, bienvenue à la conférence 8. Le plan de cette conférence est le suivant: ici, nous discuterons de la façon de se débarrasser de la première restriction imposée par le secret parfait. Nous discuterons de la façon de chiffrer de longs messages à l'aide de clés courtes et, pour cela, nous présenterons notre première primitive dans le monde en sécurité informatique, à savoir les générateurs de pseudorandom. Nous allons discuter de différentes définitions équivalentes pour les générateurs de pseudorandom. (Référez-vous à la diapositive: 00 :54) Ainsi, l'idée qui sous-tend le chiffrement de messages longs arbitraires à l'aide de clés courtes est la suivante: rappel du schéma de remplissage unique où l'espace de message, l'espace de clés et l'espace de chiffrement sont tous les éléments M=? =? = { 0, 1 }?. Pour chiffrer un message m ∈ { 0, 1 }?, l'expéditeur et le destinataire sont d'accord sur une clé uniformément aléatoire k ∈ { 0, 1 }? Nous avons discuté avec rigueur que cette notion de ce processus de cryptage vous offre la notion de secret le plus fort, à savoir le secret parfait, où il est garanti que si un adversaire qui n'est pas délimité par un ordinateur écoute le texte, alors il ne peut pas distinguer si le chiffrement est un chiffrement de m0 ou s'il s'agit d'un chiffrement de m1 parce que l'élément clé k ∈ { 0, 1 }?. C'était l'idée de base d'un tableau de remplissage unique. Maintenant, notre objectif est de trouver un mécanisme de cryptage où vous voulez chiffrer de longs messages à l'aide de clés courtes. Donc, pour cela, nous introduisons une nouvelle fonction ou une primitive que je dénote par G. Nous verrons très bientôt quelle est exactement cette primitive et quelles sont les propriétés dont nous avons besoin à partir de cette primitive. Alors, quelle est cette fonction?: { 0, 1l → { 0, 1 }?. Lorsque l et L sont des fonctions polynomiales de votre paramètre de sécurité, mais que la sortie de cette fonction G est significativement élevée par rapport à l'entrée de cette fonction G. Maintenant, la première modification que nous allons faire dans le plan directeur d'un bloc de temps est qu'à la place de l'expéditeur et du récepteur d'accord sur une clé, qui est aussi large que le message, l'expéditeur et le récepteur vont maintenant s'entendre sur une chaîne uniformément aléatoire de bits de longueur, et nowexpéditeur ne peut pas XOR cette chaîne s avec le message parce que la taille du message et la taille de la chaîne s sont différentes. XORing le message avec la clé qui se passait dans un bloc de temps, l'expéditeur calcule?? (?). Donc, puisque la sortie de la fonction G va être une chaîne de bits de longueur L, nous pouvons exécuter la XOR des bits du message avec la sortie de la fonction G sur les entrées s, et le texte chiffré qui en résulte est communiqué sur le canal. Maintenant, ce que nous espérons est si au lieu d'un adversaire sans limite de calcul, il existe un adversaire dont le temps de fonctionnement est polynomiquement délimité et s'il est fait en sorte que l'adversaire à limite de calcul ne puisse pas distinguer la sortie de la fonction G sur les entrées s d'une chaîne de bits de longueur uniformément aléatoire de longueur L, il sera alors garanti que L'adversaire délimité par ordinateur ne peut pas distinguer si le chiffrement c qu'il observe est un chiffrement de m0 ou s'il s'agit d'un chiffrement de m1.Donc, c'est l'idée de base derrière le chiffrement de longs messages à l'aide de clés courtes. L'idée de base est plutôt celle de? k, nous allons à présent réaliser?? (?) et nous supposerons qu'un adversaire délimité par ordinateur ne peut pas distinguer la sortie de cette fonction G d'une chaîne de bits de longueur uniformément aléatoire (voir la diapositive: 04 :43) Donc cette fonction G est appelée un générateur de pseudo-aléatoires. Voyons les détails internes et les propriétés de sécurité de cette primitive appelée générateur de pseudorandom. Donc sur un très haut niveau, un générateur de pseudorandom, désigné par G est un algorithme déterministe,?: { 0, 1l → { 0, 1 }?. Les exigences de cet algorithme G sont les suivantes: tout d'abord, le temps d'exécution de cet algorithme G doit être une fonction polynomiale d'un paramètre de sécurité qui signifie que votre G doit être un algorithme efficace. Cela signifie en interne que la valeur l ainsi que L sont des fonctions polynomiales de votre paramètre de sécurité. C'est donc la première exigence de votre générateur de pseudorandom. La seconde condition est l'extension? > l. La troisième exigence, qui est l'exigence de sécurité à partir de cette primitive, est le pseudo-critère de caractère aléatoire. De façon informelle, les exigences de pseudo-aléatoire exigent de vous qu'aucun test statistique efficace ne doit séparer de façon significative une sortie produite par l'algorithme G à partir d'une sortie d'un générateur vraiment aléatoire. Cela signifie que si vous considérez un générateur vraiment aléatoire, que je dénote en tant que G ’, qui va générer de façon uniforme une chaîne de bits de longueur L bits, alors le pseudo-critère de caractère aléatoire est qu'aucun test statistique ne doit être capable de distinguer les G (s) par rapport à une chaîne uniformément aléatoire produite par l'algorithme G ’. (voir Diapositive: 06 :38) Cela signifie en interne que le comportement de sortie de votre algorithme G et G ‘ doit être presque identique, et ceci est capturé antérieurement par une expérience basée sur l'indistinction, où l'intuition derrière l'expérience basée sur l'indistinction est Qu'aucun algorithme efficace ne devrait permettre de distinguer un échantillon aléatoire généré par l'algorithme G d'un échantillon aléatoire généré par un générateur G ’ réellement aléatoire. (Référez-vous à la diapositive: 07 :10) Voyons la définition de PRG basée sur l'indistinction. Dans cette expérience, nous avons un distinguisher dont l'objectif est de distinguer un échantillon généré par le générateur de pseudorandom d'un échantillon généré par un générateur vraiment aléatoire et nous avons un vérificateur hypothétique ou une expérience. Dans l'expérience, le vérificateur remet en question le distinguant par une chaîne ou un échantillon de bits de longueur L. Le défi de cette distinction consiste à déterminer si l'échantillon y est généré en exécutant le générateur de pseudorandom ou en exécutant un générateur véritablement aléatoire, c'est-à-dire que l'échantillon y qui est lancé comme un défi dans l'expérience à l'élément de distinction aurait pu être généré par l'une des deux méthodes suivantes. Le vérificateur aurait lancé une pièce uniformément aléatoire, et si le tirage de la pièce est égal à 0, l'échantillon de remise en question qui est remis au distinguisher est un échantillon uniformément aléatoire généré par un générateur de nombres vraiment aléatoires. Alors que B = 1, alors ce que le vérificateur aurait fait, c'est qu'il aurait choisi une graine ou l'intrant pour la fonction G uniformément au hasard et qu'il aurait calculé la fonction G sur cette entrée et aurait produit un échantillon y.Donc, maintenant, le défi pour le distinguisher est de savoir comment exactement l'échantillon est généré, qu'il soit généré par l'exécution d'un générateur vraiment aléatoire ou s'il est généré par l'exécution de l'algorithme G sur une graine uniformément aléatoire. L'attribut de distinction a le temps polynomial pour déterminer si l'y est généré par la méthode 0 ou par la méthode 1. Donc, la sortie du distinguant est un peu que nous dénote comme b ’.La définition de générateur de pseudorandom est nous disons un algorithme G est un générateur de pseudorandom si pour chaque modèle de temps polynomial participant à cette expérience basée sur l'indistinction, la probabilité qu'il puisse identifier correctement b = b ’ est borné par la moitié plus une fonction négligeable dans le paramètre de sécurité, où la probabilité de notre sortie D b = b ’ est sur le caractère aléatoire de l'élément de distinction et du caractère aléatoire de l'expérience ou du vérificateur. Donc, ici le terme PPT que j'introduis ici représente le temps polynomial probabiliste. Par un algorithme probabiliste de temps polynomial, je veux dire un algorithme de temps polynomial qui est de nature aléatoire. Donc, pour le reste du cours, puisque nous allons discuter des primitives sécurisées de calcul, nous envisagerons des adversaires dont le temps de fonctionnement sera le temps polynomial probabiliste. Donc, maintenant dans cette définition, nous avons besoin que la probabilité que D soit capable d'identifier le mécanisme par lequel y est généré doit être bornée par la moitié plus négligeable. Pourquoi la moitié plus négligeable? Parce qu'il y a toujours une stratégie de distinction triviale pour le distinguisher de deviner juste la méthode par laquelle y est générée, et la probabilité par laquelle cette stratégie de deviner de la distinction sera couronnée de succès est la moitié. Donc, nous ne pouvons jamais exiger dans cette définition que la probabilité que la sortie de l'élément de distinction soit correcte devrait être 0 car il y a toujours un distinguant 1/2probabilité qui peut distinguer ou dire si l'échantillon y est généré de façon aléatoire ou en exécutant le générateur de pseudo-pseudo-aléatoire. En dehors de la probabilité de la moitié, nous sommes également disposés à laisser l'adversaire identifier le mécanisme approprié par lequel l'échantillon y est généré avec une probabilité de succès négligeable et c'est parce que nous sommes dans le monde de sécurité informatique, et que nous nous attendons à l'avenir, nous utiliserons ce PRG pour chiffrer de façon arbitraire. Messages. Rappelez-vous que dans le monde en sécurité informatique, l'un des maux nécessaires qui est associé au modèle de sécurité informatique est que nous devrions être prêts à laisser l'adversaire briser ou attaquer le schéma avec une probabilité d'erreur négligeable ou très faible.Donc, c'est pourquoi cette probabilité supplémentaire négligeable est autorisée pour l'adversaire à gagner l'expérience ou à déterminer si l'échantillon est généré au hasard ou en exécutant le générateur de pseudorandom. Je souligne ici que dans toute cette expérience, la description de l'algorithme G est publiquement connue, parce que selon le principe de Kerckhoffs ’, nous ne supposons jamais que les étapes de l'algorithme sont cachées. Dans l'expérience, ce qui est caché à l'adversaire est de savoir si la graine avec laquelle l'expérience aurait invoqué l'algorithme G. L'objectif du distinguateur est de savoir si y est généré aléatoirement ou en exécutant le générateur de pseudorandom. Il s'avère qu'il existe une définition équivalente pour le générateur de pseudorandom et que la définition équivalente exige essentiellement que, quelle que soit la façon dont le vérificateur a décidé de choisir l'échantillon, la sortie du distinguant doit être identique. Autrement dit, la définition de rechange exige que la différence absolue entre ces deux probabilités soit délimitée par une fonction négligeable. Par conséquent, voyons à quoi correspondent exactement ces deux probabilités. La première probabilité est la probabilité que D étiquette l'échantillon y comme résultat d'un générateur de pseudorandom même s'il a été généré par un générateur vraiment aléatoire. Cela signifie, quelle est la probabilité que D résultats b ’ = 1 étant donné que b = 0. Donc D output b ’ = 1, cela signifie que D est en voie d'étiqueter l'échantillon y qui lui est lancé comme un défi comme résultat d'un générateur de pseudorandom, étant donné que b = 0,Cela signifie, le vérificateur a décidé de choisir l'échantillon au hasard, alors que la seconde probabilité est la probabilité que D identifie l'échantillon y comme le résultat d'un générateur de pseudorandom, étant donné qu'effectivement il a été généré par un générateur de pseudorandom. Par conséquent, la deuxième définition de rechange exige l'avantage distinctif du distinguant. Nous disons que la différence absolue entre ces deux probabilités est l'avantage distinctif du distinguant avec lequel elle peut distinguer si l'échantillon a été généré par un générateur de pseudo-aléatoires ou un générateur.Donc, cette définition alternative exige que, quelle que soit la façon dont l'échantillon y aurait été généré, ces réponses devraient être presque identiques dans les deux cas sauf avec une probabilité négligeable, et il s'avère que nous pouvons prouver que ces deux définitions ou conditions sont équivalentes. Nous pouvons prouver que si nous avons un générateur de pseudorandom, qui satisfait à la première condition, cela implique aussi qu'il doit satisfaire la seconde condition et vice versa. Cela signifie que ces deux définitions sont équivalentes à chacune d'elles. Par conséquent, dans le reste du cours, nous pouvons utiliser n'importe laquelle de ces deux conditions pour mentionner la définition de sécurité du générateur de pseudorandom selon notre convenance. Il suffit de se rappeler que la première définition dit que la probabilité est que D détecte correctement le mécanisme par lequel y est généré doit être borné par la moitié plus négligeable, alors que la seconde condition exige que l'avantage distinctif de l'élément distinctif, à savoir son avantage de se séparer que y soit généré par le mécanisme 1 ou le mécanisme 2 doit être borné par une probabilité négligeable. (Voir Diapositive Heure: 14 :58) Donc, voyons un exemple de générateur de pseudorandom. En fait, la construction que nous allons voir n'est pas un générateur de pseudorandom et nous allons le prouver formellement. Dans cet exemple, la fonction G est la suivante. Il prend des entrées de taille 1 bits et il étend son entrée de 1 bit, c'est-à-dire qu'il produit une sortie dont la longueur est supérieure à la longueur de son entrée, et la façon dont il s'étire est la suivante: les premiers bits de sortie l de l'algorithme sont les mêmes que les entrées de l'algorithme, cela signifie qu'ils vont être uniformément aléatoires alors que le dernier bit de sortie de l'algorithme G est simplement le XOR des bits des entrées de l'algorithme. Donc c'est une description de l'algorithme G qui vous est donné et maintenant vous devez prouver ou réfute si cet algorithme G est un générateur de pseudorandom ou pas. En fait, il s'avère que cet algorithme G n'est pas un générateur de pseudorandom et que pour cela, nous pouvons considérer le test statistique efficace suivant qui peut distinguer n'importe quel échantillon généré par un algorithme G à partir d'une chaîne uniformément aléatoire de l + 1 bits. Si nous considérons n'importe quel échantillon généré par l'algorithme G sur une entrée uniformément aléatoire, il s'avère que dans cette sortie, le l + 1ème bit doit être le XOR des premiers bits parce que c'est la propriété de sortie de toute sortie générée par l'algorithme G. considérant que si nous considérons une chaîne uniformément aléatoire de longueur l + 1ème bits générée par une vraie Générateur aléatoire, il peut arriver que l + 1ème bit est effectivement le XOR des premiers bits l, mais la probabilité de ce qui se passe n'est que 1/2.Cela signifie que vous avez maintenant une condition qui sera certainement satisfaite pour un échantillon toujours si l'échantillon aurait été généré par l'algorithme G, alors que la probabilité que la même condition tient pour un échantillon aléatoire généré par un algorithme est au plus de la moitié. Maintenant, sur la base de cette intuition, nous pouvons convertir ce test statistique en un distinguant efficace qui peut distinguer un échantillon généré par un algorithme G d'un générateur vraiment aléatoire avec une probabilité significative et la stratégie de distinction est le suivant. Le distinguant sera lancé avec un défi, qui sera constitué d'une corde de longueur l + 1 bits et le défi pour le distinguisher est de découvrir comment il est généré, à savoir s'il est généré de façon uniforme de façon aléatoire ou s'il a été généré par l'exécution de l'algorithme G sur des graines d'entrée uniformément aléatoires. Maintenant, la stratégie de distinction pour le distinguant est la suivante: le distinguant marque l'échantillon y comme étant le résultat du générateur de pseudorandom. Namely it says b ’ = 1 or outputs b ’ = 1 if and only if it finds the l + 1th bit of the challenge that is administré to him is the XOR of the restante l bits of the challenge. Maintenant, calculons l'avantage distinctif de cette stratégie de distinction.Voyons d'abord quelle est la probabilité que cet échantillon de stratégie de distinction soit uniformément aléatoire en tant qu'échantillon généré par un générateur de nombres réellement aléatoires, et il s'avère que la probabilité que D génère b ‘ = 1 étant donné que b = 0 est la moitié, parce que si b = 0 cela signifie que l'échantillon y est vraiment aléatoire et seulement avec la probabilité 1/2 et qu'il sera assuré que le l + 1ème bit est en fait le XOR des bits l restants. Dans ce cas, le distinguant aurait une sortie b ’ = 1, alors que la probabilité que les sorties b ‘ = 1 étant donné que b = 1 est en effet 1, parce que si b = 1, cela signifie que le défi ou l'échantillon qui a été donné à l'élément de distinction est généré par un générateur de pseudorandom, auquel cas il sera en effet le cas que l + 1thbit est le XOR des bits l restants et, dans ce cas, le distinguant va à la sortie 1.Donc, si vous considérez l'avantage distinctif de l'élément distinctif, il s'agit de la moitié, ce qui est simplement une bonne probabilité de distinction, il s'agit d'une fonction non négligeable dans le paramètre de sécurité, Et donc ce distinguisher ou cet algorithme G ne répond pas à la définition du générateur de pseudorandom. (Voir Heure de la diapositive: 19 :24) Donc, souvenons-nous du jeu de générateur de pseudorandom et dans le jeu de l'indistinction du générateur de pseudorandom, nous avons souligné que le distinguisher devrait être un algorithme efficace, il devrait être un algorithme de temps polynomial. Pourquoi nous devons mettre cette restriction? Il s'avère que, quelle que soit la façon dont vous concevez-vous un générateur de pseudorandom, il peut être toujours distingué par un distinguisher force brute où la stratégie de distinction sera de faire une force brute de ce qui est toutes les entrées possibles pour l'algorithme G. Ce distinguisher force brute peut toujours distinguer un échantillon véritablement aléatoire d'un échantillon de pseudorandom avec une probabilité, ce qui est presque équivalent à 1. Alors, comprenons ça. Tout générateur de pseudorandom, puisqu'il doit produire une sortie qui est significativement plus grande que son entrée, il doit déterministe étendre son entrée, et par conséquent, la sortie du générateur de pseudorandom va être très loin d'une chaîne uniformément aléatoire car pour un générateur vraiment aléatoire, chacun des bits de sortie est généré indépendamment, alors que pour un générateur de pseudorandom, chacun des bits de sortie est en fait une fonction déterministe de l'entrée. Alors pour montrer mon point, considérons un générateur de pseudorandom arbitraire. Ne nous concentrons pas sur les détails internes de cet algorithme G et imaginez qu'il s'agit d'un générateur de pseudorandom de longueur double, qui développe l'entrée par une entrée de taille double. Cela signifie que s'il prend une entrée de taille n bit, il produit une sortie de taille 2n bits. Nous voulons comparer cet algorithme avec un générateur G vraiment aléatoire qui aurait produit des chaînes de bits uniformément aléatoires de longueur 2n bits.Maintenant, si nous comparons les résultats de l'algorithme G, il s'avère que la plupart des chaînes de longueur 2n bits ne se produisent pas dans la plage de l'algorithme G. Donc, ce que je veux dire par gamme de G est l'ensemble de toutes les sorties possibles qui auraient pu être générées par l'exécution de l'algorithme G sur diverses entrées possibles. A savoir, la gamme de générateur vraiment aléatoire est le plus grand cercle, qui est l'ensemble de toutes les chaînes possibles de longueur 2n, parce qu'un générateur vraiment aléatoire va produire chacune de la chaîne de la candidate 2n comme un résultat avec probabilité 1/2 à la puissance 2n alors que, si nous considérons l'algorithme G, ce n'est pas le cas que toutes les chaînes de longueur 2n vont probablement se produire comme la sortie. Le nombre maximum de sorties distinctes que l'algorithme G pourrait produire est au maximum de 2n, à savoir le nombre d'entrées possibles pour l'algorithme G car puisque l'algorithme G est un algorithme déterministe, pour chaque entrée, vous obtiendrez une sortie spécifique. Donc, au mieux que vous pouvez espérer de ce qui est pour chaque entrée distincte, l'algorithme G vous donne un output.Donc, le nombre maximum de sorties que l'algorithme G peut produire est au plus de 2n. Comme vous pouvez le voir clairement, 2nis un très, très petit sous-ensemble de l'espace plus grand, à savoir 22n. Cela signifie que si nous considérons la probabilité qu'une chaîne de 2n bit uniformément aléatoire, qui aurait été produite par un générateur vraiment aléatoire, et si nous calculons la probabilité qu'une chaîne de longueur uniformément aléatoire aurait pu aussi se produire comme résultat de l'algorithme G. Eh bien, la probabilité pour cela est 2n /22nparce que la probabilité que cette chaîne vraiment aléatoire aurait aussi été produite par G dépend de l'existence d'une graine, ce qui, lorsqu'il est utilisé avec l'algorithme G aussi, aurait produit une chaîne vraiment aléatoire et la probabilité de se produire qui est 2-n. (Référez-vous à la diapositive: 23 :12) Maintenant, sur la base de cette idée, nous ne pouvons pas concevoir le modèle de distinction suivant qui permet de distinguer ces deux générateurs de nombres aléatoires avec une probabilité significative. Donc, sur votre gauche, vous avez la longueur de PRG double, alors que dans votre côté droit vous avez le générateur vraiment aléatoire générant des cordes de longueur 2n bits et voici notre distinguant. Le distinguisher a un défi, un échantillon de longueur de deux 2n bits et il doit déterminer s'il a été généré en exécutant le premier algorithme ou le second algorithme, à savoir, le vérificateur aurait généré une pièce, et si la pièce aurait été 0, l'échantillon aurait été généré de façon aléatoire et si la pièce aurait été 1, alors l'échantillon aurait été généré en exécutant l'algorithme G sur une graine uniformément aléatoire. Maintenant, la stratégie de distinction pour le distinguisher est la suivante: elle fait une force brute, c'est-à-dire qu'elle passe par toutes les valeurs possibles des candidats et exécute l'algorithme G et vérifie si oui ou non des candidats, G (s) auraient donné l'échantillon y. Si c'est le cas, alors le distinguo identifie le défi que doit relever le générateur de pseudorandom, sinon il étiquette un échantillon y comme étant généré par un générateur vraiment aléatoire. Bien sûr, le temps de fonctionnement de ce distinguisher est d'ordre 2ncar il doit faire une force brute d'un espace clé d'un espace de départ dont la taille est 2n. Donc, il est clair que c'est inefficace, le point que je veux souligner à travers cet exemple, c'est que cette stratégie de distinction peut toujours distinguer significativement ces deux algorithms.Donc, calculons l'avantage distinctif de ce distinguant. Donc, quelle est la probabilité qu'un échantillon vraiment aléatoire soit étiqueté par ce distinguisher comme un échantillon généré par le générateur de pseudorandom, c'est-à-dire ce qui est la probabilité D sorties b ‘ = 1 donné b = 0? Eh bien, comme nous avons discuté plus tôt de la probabilité pour cela est 2-n alors que si l'échantillon y aurait été effectivement généré par un générateur de pseudorandom, la stratégie de distinction serait effectivement sortie b ‘ = 1 avec probabilité 1.Donc, cela signifie, si vous prenez la différence absolue de ces 2 probabilités, l'avantage distinctif de la distinction s'avère être presque 1, à savoir 100%. Ainsi, il est possible de distinguer clairement si l'échantillon a été produit par le PRG ou par le générateur véritablement aléatoire, mais puisque, dans notre définition, nous n'envisageons la sécurité que contre un distinguant efficace, cette stratégie de distinction ne serait pas considérée comme une menace selon notre modèle. (Référez-vous à la diapositive: 25 :55) Nous avons donc vu deux définitions de PRG basées sur la notion d'indistinction. Il s'avère qu'il existe une autre définition, qui est différente de la définition indistinctiity-baseddefinition et la définition alternative est la suivante: imaginez un générateur vraiment aléatoire G ’ qui produit une chaîne de bits de longueur L, et comment le générateur vraiment aléatoire aurait fonctionné? Pour i = 1 à L, il aurait lancé une pièce de monnaie équitable, une pièce de monnaie non biaisée, et elle aurait produit le résultat. Puisque la pièce n'est pas biaisée avec la moitié de probabilité, chacun des bits de sortie aurait été 0 ou 1. Cela signifie, s'il y a un adversaire ou un algorithme qui a observé les premiers iissues de ce générateur vraiment aléatoire, où il s'agit de n'importe quoi dans la gamme 1 à L-1, il ne peut prédire le prochain bit de sortie du générateur vraiment aléatoire, sauf avec la probabilité la moitié parce que chacun des bits de résultat d'un générateur vraiment aléatoire est indépendant l'un de l'autre. Cela signifie, si la probabilité qui est l'algorithme A ayant observé les premiers i bits du générateur vraiment aléatoire les sorties correctement le bit suivant est toujours délimité par 1/2 et cela vaut pour n'importe quel i de l'intervalle 1 à L-1. La définition alternative du générateur de pseudorandom est que nous devrions nous attendre à ce que quelque chose de similaire se produise également pour le générateur de pseudorandom. Cela veut dire, pour un générateur de pseudorandom, même s'il y a un algorithme de distinction de temps ou un algorithme, qui a vu les premiers bits de la sortie du générateur de pseudorandom sur une graine inconnue, il ne devrait pas être capable de prédire le prochain bit de sortie du générateur de pseudorandom, sauf avec la probabilité à moitié plus négligeable, et cette intuition est maintenant saisie par une expérience que nous appelons comme l'expérience de prédiction suivante. Dans cette expérience, nous avons l'algorithme G pour lequel nous voulons considérer la sécurité. La description de l'algorithme est connue publiquement, et le défi pour l'adversaire est généré de la façon suivante: l'expérience ou le vérificateur exécute l'algorithme G en sélectionnant une entrée uniformément aléatoire pour cet algorithme G et il produit le résultat de l'algorithme que l'adversaire demande ou remet en question l'adversité dit “ okay! vous me donnez les i bits de la sortie que vous avez générée ”, où i est autre chose dans l'intervalle 1 à L-1. Donc, selon i, l'expérience, ou le vérificateur jette les premiers bits de la sortie générée par le vérificateur et le défi pour l'adversaire est de calculer le bit suivant de la sortie y générée par le vérificateur en observant les premiers bits de sortie de l'échantillon tels que générés par le vérificateur. Nous disons que l'algorithme G, qui est accessible au public, est imprévisible si la probabilité qu'A génère le bit i + 1 correctement est délimitée par la moitié plus négligeable. Alors, remarquant que dans cette expérience, l'adversaire n'est pas censé distinguer 2 algorithmes, seulement un échantillon généré par l'algorithme 1 par rapport à l'algorithme 2. L'essence de cette expérience est que l'adversaire doit prédire correctement le prochain bit de sortie de l'algorithme G, ayant observé les premiers bits de sortie de l'algorithme G sur un input.I stress que les entrées s ne sont pas connues de l'algorithme, parce que si les entrées s sont aussi connues de l'algorithme A, alors l'adversaire peut prédire correctement le prochain bit de sortie de y avec la probabilité 1. Le défi pour l'adversaire est en l'absence des entrées, il doit prévoir correctement i + 1ème sortie, et dans la définition, nous avons lié la probabilité de succès de l'adversaire par moitié plus négligeable. Encore une fois, la moitié parce qu'il y a toujours un adversaire qui peut deviner ce qui pourrait être le prochain bit de sortie de l'algorithme G, et avec la probabilité 1/2, cette stratégie de deviner est toujours correcte. En dehors de cela, nous sommes également disposés à laisser l'adversaire sortir correctement le prochain bit de sortie de l'algorithme G avec une probabilité négligeable, et ceci vient du fait que nous sommes dans le monde de sécurité informatique et l'un des maux associés au monde de sécurité informatique est que nous devrions être prêts à laisser l'adversaire briser votre schéma ou attaquer votre schéma avec une faible probabilité de succès.Il s'avère donc que nous pouvons prouver que si un algorithme G satisfait à cette expérience de bit suivant ou si votre algorithme G est imprévisible selon cette définition, il satisfait aussi à la définition de PRG basée sur l'indistinction que nous avons déjà vue. J'espère que vous avez apprécié cette conférence. Je vous remercie.