Loading
Notes d'étude
Study Reminders
Support
Text Version

Chiffrement sécurisé CPA à partir de PRF

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 ProfessorInternational Institute of Information Technology-BangaloreLecture-15CPA Secure Encryption From PRFHello everyone, welcome to lecture 14. (Reportez-vous à la diaporama: 00 :32) Le plan de cette conférence est le suivant. Dans cette conférence, nous discuterons de la façon de concevoir l'algorithme de chiffrement sécurisé de CPA à l'aide d'une fonction pseudo-aléatoire. Et nous verrons également une preuve de sécurité détaillée de cette construction, car au cours de cette preuve de sécurité détaillée nous allons voir un modèle de démonstration de la sécurité des constructions basées sur une fonction pseudo-aléatoire, que nous rencontrerons à plusieurs reprises tout au long de ce cours. Nous discuterons aussi de certains inconvénients de l'algorithme de chiffrement CPA que nous allons construire à partir de la fonction pseudo-aléatoire, ce qui nous motivera à concevoir ce que nous appelons les modes d'opérations de PRF ou des algorithmes de chiffrement par bloc, dont nous discuterons lors de la prochaine conférence. (Voir Diapositive: 01 :11) Donc, rappelons-nous la définition de Message unique de sécurité CPA. Donc, en gros, c'est un jeu entre un challenger et un adversaire où l'adversaire est délimité par les calculs, nous avons un schéma connu publiquement sur un espace de message. Et le nom de l'expérience est l'expérience unique de l'indistinction des messages CPA. Et en gros l'expérience consiste en 4 phases, vous avez une phase de formation pré-challenge, puis la phase de challenge, la phase de formation post-challenge et la sortie phase.Donc, au cours de la phase de formation pré-test, notre adversaire est autorisé à obtenir un service d'oracle de chiffrement qui signifie qu'il peut demander le chiffrement de tous les messages de son choix à partir de l'espace de texte en clair. Et il peut demander ses requêtes de façon adaptative et répondre à la requête d'oracle de schiffrement de l'adversaire, le challenger génère une clé uniformément aléatoire en exécutant l'algorithme de génération de clé et crypte tous les textes en clair que l'adversaire a demandé pour utiliser la clé inconnue k, alors dans la phase de remise en question, l'adversaire soumet une paire de texte en clair, mais la seule restriction étant que la longueur doit être le same.Je répète ici qu'il n'y a absolument aucune restriction sur le message de contestation m0 et m1 que l'adversaire soumet. Il peut s'agir de n'importe quel message pour lequel il a peut-être déjà obtenu le service de requête d'oracle de chiffrement et de différencier la paire de texte en clair de l'épreuve de l'oracle de chiffrement que j'utilise différentes polices pour dénoter le texte en clair. Maintenant, pour répondre à la paire de texte en clair, le challenger décide au hasard soit de chiffrer le message m0 ou m1 et de chiffrer un message mb et l'objectif de l'adversité ou le défi pour l'adversaire est de déterminer si c * est un chiffrement de m0 ou m1.Et nous donnons en fait plus de puissance à l'adversaire, c'est-à-dire qu'après avoir vu le texte de défi c *, nous donnons à l'adversaire un accès au service d'oracle de cryptage post-challenge où il peut de nouveau demander le cryptage de n'importe quel message de son choix. Et le challenger doit encore chiffrer tous ces messages en utilisant la clé inconnue k. Et enfin, dans la phase de sortie, l'adversaire décide ou donne si c * est un chiffrement de m0 ou m1.Et nous disons que le processus de cryptage Π est un seul message est CPA sécurisé, si la probabilité qu'un adversaire délimité par ordinateur puisse gagner ce jeu est délimité par la moitié plus une fonction négligeable négative (n) dans le paramètre de sécurité n ou, de façon équivalente, l'avantage distinctif de l'attaquant est délimité par une probabilité négligeable. C'était donc notre définition du message unique que nous avions vu lors de la dernière conférence (voir Diapositive: 03 :54). Maintenant ce que nous allons faire, c'est que nous allons maintenant concevoir un processus de cryptage des candidats qui satisfait à cette notion de sécurité. Donc avant d'entrer dans la construction réelle en utilisant une fonction pseudo-aléatoire pour le moment, supposons que nous avons accès à une fonction vraiment aléatoire. Et nous allons d'abord voir la construction d'un processus de cryptage sécurisé du candidat CPA, en supposant que nous avons accès à une fonction vraiment aléatoire. La raison pour laquelle nous voyons ce processus de cryptage sécurisé de l'ACP à l'aide d'une fonction vraiment aléatoire est que plus tard, lorsque nous verrons la construction réelle basée sur le PRF, la preuve sera simplifiée. Vous pouvez donc prendre en compte cette version du processus de chiffrement que j'appelle Π, consistant en un processus de chiffrement et de déchiffrement d'algorithme de génération de clés. Le processus de génération de clés pour ce schéma Π est essentiellement la sortie d'une fonction uniformément aléatoire ou d'une fonction vraiment aléatoire de mappage des chaînes de bits vers les chaînes de bits de type L. Maintenant, l'algorithme de chiffrement de ce schéma de chiffrement est le suivant: il prend du texte en clair de taille L bits. Et il faut une fonction vraiment aléatoire qui sera disponible aussi bien à l'expéditeur qu'avec le récepteur, et elle ne sera connue qu'à l'expéditeur et au récepteur. Maintenant, pour chiffrer le message m, ce que fait l'algorithme de chiffrement, c'est qu'il décide d'un x uniformément aléatoire à partir du domaine de la fonction f, de droite. Et ensuite, la fonction vraiment aléatoire f est évaluée sur cette entrée x pour obtenir un masque de bits de longueur L qui est effectivement utilisé pour masquer le message m, qui est le texte de chiffrement. Maintenant, vous pouvez voir que le texte chiffré est une collection de 2 composants. Il se compose de 2 composants, à savoir la valeur x à laquelle la fonction vraiment aléatoire est évaluée. Et le chiffrement réel du message qui est le masquage du message avec la valeur de la fonction vraiment aléatoire évaluée à cette valeur uniformément aléatoire x, qui fait partie du texte chiffré. Comment le décryptage va se produire. Alors, imaginez que le récepteur ait aussi la même fonction vraiment aléatoire, et il obtient un code de chiffrement qui se compose de 2 composants la partie x et la partie de chiffrement proprement dit. Maintenant, si vous voyez la syntaxe du processus de chiffrement par la propriété de XOR, il s'ensuit que pour récupérer le message m et ce que le destinataire a essentiellement à faire est de calculer la valeur de la fonction vraiment aléatoire f à l'entrée x, et juste de le récupérer à partir du composant ciphertext du texte chiffré ou du composant c du texte chiffré réel. Et cela redonnera le texte en clair. M. C'est donc l'algorithme de décryptage, c'est pourquoi ce système est inefficace. La raison pour laquelle le système est inefficace, c'est que l'émetteur et le récepteur doivent stocker la description de la fonction vraiment aléatoire f. Et si vous imaginez une fonction vraiment aléatoire comme table de vérité, alors fondamentalement à la fois l'expéditeur et le récepteur doivent stocker ces nombreux nombres de bits. Namely 2lrows, chacun constitué de bits L. Donc si L est une fonction polynomiale du paramètre de sécurité, ceci est exponentiellement grand. Ainsi, le stockage sage de l'expéditeur et du récepteur doit stocker ou effectuer une quantité exponentielle de calcul. Pour le moment, ne vous inquiétons pas pour cette partie de l'inefficacité, analysons l'aspect sécurité de ce processus de cryptage. Nous allons maintenant prouver que le système est protégé par l'ACP pour le cryptage des messages de L bit. Et l'intuition de base que ce processus de cryptage est sécurisé par CPA est que si vous voyez la syntaxe de votre processus de cryptage ici, chaque instance du processus de cryptage évalue réellement la fonction vraiment aléatoire sur un x uniformément aléatoire. Cela signifie que ma fonction f est une fonction vraiment aléatoire, la valeur de f sur ce x uniformément aléatoire va être une chaîne de bits uniformément aléatoire, c'est-à-dire chaque instance d'un processus de chiffrement que vous pouvez imaginer comme une instance d'un bloc de temps, que cela tient dans l'hypothèse que les valeurs x que nous utilisons en fait pour le processus de chiffrement, ne se répète jamais. Cela signifie que si vous utilisez ce processus de chiffrement pour le chiffrement du nombre polynomial de messages, et dans le nombre polynomial d'instances de chiffrement, la valeur x ne se répète jamais, puis chaque instance de ce processus de chiffrement que vous pouvez imaginer comme une instance indépendante d'un bloc de temps unique. Et nous avions déjà vu que si vous considérez des instances indépendantes d'un bloc de temps où le tampon utilisé dans chaque instance est indépendant l'un de l'autre, alors il ne peut pas être brisé même par un adversaire sans limite de calcul. Cela signifie que nous pouvons dire intuitivement que conditionnés à l'événement que les valeurs x ne sont jamais répétées dans le nombre polynomial d'instances de ce processus de cryptage. Donc, ce système de cryptage est en fait CPA sécurisé. C'est une intuition de base. Maintenant, ce que nous allons faire, c'est que nous allons vraiment formaliser cette intuition rigoureusement à travers notre expérience. (Référez-vous à la Diapositive: 08 :50) Et l'analyse de cette expérience. Alors, pensez à n'importe quel adversaire arbitraire A, qui veut participer à une instance de jeu de sécurité CPA à message unique contre ce processus de cryptage Π. Donc, comme pour les règles des jeux, nous avons 4 phases. (Référez-vous à la diapositive: 09 :05) Ensuite, dans la phase de formation pré-test, notre adversaire peut demander le chiffrement de n'importe quel nombre de messages de son choix tant qu'il est délimité par une fonction polynomiale dans le paramètre de sécurité. Alors laissez l'adversaire demander le chiffrement du nombre de messages. Maintenant, pour répondre à ces messages, le challenger a essentiellement à chiffrer tous ces messages selon notre processus de cryptage Enc. Donc, pour ce faire, il va exécuter un algorithme de génération de clé ou l'algorithme de génération de fonction, dans ce cas pour être spécifique et génère une fonction vraiment aléatoire. Et une fois qu'une fonction vraiment aléatoire est disponible avec le challenger, elle va chiffrer tous les messages pour lesquels l'adversaire a demandé le service d'oracle de cryptage, non. Donc chacun des ciphertext (ci, xi) fondamentalement chaque algorithme de chiffrement se compose essentiellement de 2 composants, à savoir un composant x et le chiffrement réel. Ainsi, la valeur x est effectivement utilisée pour évaluer la fonction vraiment aléatoire pour obtenir le masque et ensuite XORed avec le message réel pour obtenir le composant ciphertext. De la même façon que l'adversaire de phase de défi soumettra une paire de messages par exemple m0 et m1 et que notre challenger va chiffrer au hasard l'un d'entre eux, je dénote le message chiffré crypté mb à être la collection de (x*, c *) essentiellement x * est la valeur x qui est utilisée pour générer l'extrusion pour masquer le message mb. Et le masquage du message mb avec l'extrusion est c *, alors vous avez la phase de formation post-test que nous sommes à nouveau notre adversaire peut demander le service d'oracle de chiffrement pour le nombre polynomial de messages. Et encore une fois, en utilisant la même fonction vraiment aléatoire inconnue qui n'est disponible qu'avec le challenger, le Challenger va générer le masque à savoir f (xi) où xi sera la partie du texte chiffré. Et une fois pour xi est calculé, il sera XORed avec les messages pour obtenir la partie de chiffrement correspondante. Et puis nous avons la phase de sortie droite là où l'adversaire produit essentiellement si c *, ou le code de défi (x*, c *) pour être plus précis est un chiffrement de m0 ou m1, de droite. Alors, faisons d'abord quelques calculs ici. Laissez-moi indiquer le nombre total de requêtes, à savoir les requêtes pré-challenge et les requêtes post-test que l'adversaire a demandé est Q (n), qui va être une fonction polynomiale du paramètre de sécurité. Et nous allons prouver cette affirmation, à savoir, nous allons prouver que tout adversaire arbitraire A qui est délimité par les calculs et fait de Q (n) le nombre de requêtes dans une instance de jeu de sécurité de message unique CPA par rapport au processus de chiffrement Π ’ ou Π va identifier correctement si le chiffrement de défi est un chiffrement de m0 ou m1 avec probabilité au plus 1/2 + (Q (n) / 2l). Puisque Q (n) est de la fonction polynomiale du paramètre de sécurité et en supposant que l est aussi une fonction polynomiale du paramètre de sécurité, globalement cette quantité Q (n) /2lis en fait une quantité négligeable, non. Cela signifie que nous allons vraiment prouver que la probabilité que tout adversaire arbitraire A par Q (n) nombre de requêtes gagne une instance de message unique de sécurité CPA est la moitié plus negl (n), ce qui prouve que notre processus de cryptage Π est en fait un seul message CPA sécurisé. (Référez-vous à la diapositive: 12 :34) Alors, faisons la preuve de notre réclamation. Et nous allons le prouver en utilisant plusieurs observations que nous allons faire à propos de n'importe quelle instance de message unique de sécurité CPA. Notre première observation est donc que si nous considérons l'ensemble de valeurs x qui sont réellement utilisées pour chiffrer le chiffrement ou les requêtes d'un pré-challenge, et les valeurs x qui sont réellement utilisées par le challenger pour chiffrer les requêtes d'oracle de chiffrement post-challenge, alors l'adversaire connaît la valeur de la fonction vraiment aléatoire f disponible avec le challenger sur ces x valeurs, pourquoi?. Alors, concentrons-nous d'abord sur la phase de formation avant remise en question. Donc, si je considère que la requête est juste, la requête est pour le chiffrement du message mi où mi est connu de l'adversaire. Et en réponse à cela, l'adversaire apprend le texte qui est la collection de (xi, ci) la valeur et l'adversaire connaît la relation entre mi xi ci. L'adversaire Namely sait que la fonction vraiment aléatoire inconnue f évalué au xi est lié à ci et mi par l'opération XOR et tout est connu de l'adversaire dans cette équation, sauf la partie f. Donc, si l'adversaire connaît la partie mi, l'adversaire connaît la partie ci et l'adversaire connait la partie xi. Donc, si l'adversaire vient juste de réaliser cette opération, l'adversaire vient au courant de la valeur de la fonction vraiment aléatoire f à la xi. Donc c'est le cas pour la phase de pré-challenge ou la phase de formation pré-challenge. Il en va de même pour la phase de formation post-remise en question. Cela signifie que si l'adversaire a demandé le service d'oracle de cryptage pour ce message mi et en réponse à cet adversaire obtient le texte chiffré sous le nom (xi, ci) alors qu'en effectuant cette opération, c'est-à-dire l'exécution de la XOR de mi et de l'adversaire ci va apprendre la valeur de la fonction vraiment aléatoire f à l'entrée xi de droite. Donc c'est la première observation qui est facile à voir. (Référez-vous à Diapositive: 14 :32) La seconde observation ici est si vous considérez x * valeur, c'est-à-dire la valeur x, qui est réellement utilisée pour générer l'extrusion pour le chiffrement du challenge, qui est en fait utilisé pour générer le code de chiffrement de défi, alors si ce x * n'appartient pas à l'ensemble de valeurs x, qui sont utilisées pour chiffrer une phase de requête pré-challenge, les requêtes pré-challenge et les requêtes post-challenge, alors la probabilité que l'adversité gagne cette instance du jeu CPA est au plus 1/2.Et c'est à cause du fait que si la valeur x * qui est réellement utilisée Générer le texte de chiffrement de défi n'a jamais été utilisé dans aucune des requêtes de phase de formation pré-challenge ou de post-remise en question, puis, en gros, si je retire cette phase de formation pré-challenge et la phase de formation post-remise en question, et si je me concentre sur la phase de remise en question de cette expérience et qu'elle réduit à une instance d'une expérience d'indistinction de temps de remplissage unique, et nous avons déjà vu qu'un bloc de temps est parfaitement sécurisé même contre un adversaire sans limite de calcul. C'est donc la preuve de notre deuxième observation. Maintenant, la troisième observation que nous pouvons faire à propos de cette instance de jeu CPA est que, si la valeur x * qui est utilisée pour générer le texte de chiffrement est répétée, cela signifie qu'il appartient à l'ensemble des xvaleurs qui sont utilisées pendant la phase de formation pré-challenge, ou l'ensemble de valeurs x qui sont utilisées pendant la phase de formation post-challenge, alors la probabilité que l'adversaire gagne ce jeu est en fait 1. En effet, dans le cadre du défi de chiffrement, l'adversaire connaît la valeur x, à savoir la valeur x *, qui est utilisée pour générer ou chiffrer le message mb. Et l'adversaire a également vu les valeurs x utilisées au cours de la phase de formation pré-remise en question, ainsi que la phase de formation post-remise en question. Donc en comparant la valeur x * avec la liste des valeurs x que l'adversaire a, s'il voit que x * se répète, alors il peut facilement identifier où le c * est en fait un chiffrement de m0, ou s'il s'agit d'un chiffrement de m1 en effectuant cette opération, non. C'est donc notre troisième observation. Et l'observation la plus cruciale que nous allons maintenant faire, c'est que la probabilité que la valeur x qui est utilisée dans le texte de chiffrement de défi, à savoir x * se répand lorsque notre adversaire est en train de faire le nombre Q (n) de requêtes est au plus (Q (n) /2l). Donc, pour cela, remarquant que Q (n) qui n'est rien d'autre que le nombre de requêtes que l'adversaire a fait tout au long de cette instance du jeu CPA. Et dans chaque cas de la requête lorsque l'adversaire est en train de demander le chiffrement d'un message, la valeur x qui est utilisée par le challenger pour chiffrer ce message est choisie au hasard sur l'ensemble de la chaîne binaire de l bit, à droite. Donc la probabilité que x * qui est réellement utilisé dans le challenge, de générer le challenge ciphertextgets repris dans Q (n) le nombre de requêtes est bien sûr Q(n) /2l.So c'est notre quatrième droit d'observation. Donc, sur la base de ces 4 observations, formalisons notre argument quant à la raison pour laquelle ce système basé sur une fonction vraiment aléatoire est bien sûr CPA. Alors, let Répéter indique l'événement que la valeur x qui est utilisée pour chiffrer le défi, qui est utilisé pour générer le texte de chiffrement est répété. Cela signifie qu'il est soit utilisé lors de l'une des requêtes d'oracle de chiffrement pré-challenge, soit l'une des requêtes de l'oracle de chiffrement post-challenge.Ensuite, notre but est d'analyser quelle est la probabilité de succès de notre adversaire d'identifier correctement si le chiffrement de défi est un chiffrement de m0 ou m1. Et la probabilité gagnante peut être divisée en deux probabilités individuelles, à savoir la probabilité qu'un adversaire gagne le jeu CPA étant donné que la valeur x * se répète pendant l'une des requêtes d'oracle de chiffrement, ou la probabilité que l'adversaire gagne le jeu CPA, étant donné que les valeurs x*ne sont jamais répétées pendant l'une des requêtes d'oracle de chiffrement, drot.Maintenant, ce que je peux faire c'est que la première probabilité ici, je peux toujours être liée par la probabilité que l'événement Répéter se produit et la seconde probabilité que je l'écris comme c'est le cas. Donc cela signifie que mon but est de calculer maintenant la probabilité que la répétition de l'événement se produise et la probabilité que l'adversaire gagne le jeu CPA, étant donné que la répétition de l'événement ne se produit pas. Et Iam va montrer que ceci est délimité par 1/2 + Q(n) /2l.Pourquoi bien nous avons déjà vu que la probabilité que la valeur x * se répète est Q (n) /2l, nous avions déjà vu dans l'une des observations, et la seconde probabilité, à savoir l'adversaire gagne le jeu CPA étant donné que x * la valeur ne se répète jamais est délimité par 1/2 parce que dans ce cas, on peut simplement dire que la phase de formation pré-challenge et la phase de formation post-test est inutile pour l'attaquant. Et si je me concentre sur la partie challenge du jeu qui n'est rien d'autre qu'une instance d'une expérience d'indistinction de l'extrusion temps, et nous Savent que même un adversaire sans limite de calcul ne peut pas gagner le seul jeu d'indistinction de l'extrusion. C'est ainsi que nous obtenons la probabilité globale de succès de notre adversaire. Et comme j'ai déjà soutenu que la probabilité Q (n) /2lcan be approximée par une fonction négligeable dans le paramètre de sécurité, si Q (n) est une fonction polynomiale dans le paramètre de sécurité et l est également une fonction polynomiale dans le paramètre de sécurité. Donc ce que nous avons en général, c'est qu'une construction basée sur une fonction vraiment aléatoire est en effet CPA (voir la diapositive: 20 :28). Mais comme je l'ai dit, ce schéma hypothétique Π basé sur la fonction vraiment aléatoire que nous ne pouvons pas utiliser dans la pratique parce que pour le déploiement, l'émetteur et le récepteur doivent stocker la description d'une fonction vraiment aléatoire qui est de taille exponentielle. Donc, ce que nous allons plutôt faire, c'est que nous allons conserver le plan que nous avions utilisé pour ce processus de cryptage Π. Et ce que nous allons faire maintenant, c'est que partout où il y a des invocations de la fonction vraiment aléatoire, on les remplace par des invocations d'une fonction pseudo-aléatoire. Donc ici je suppose que j'ai une fonction pseudo-aléatoire F, dont la taille de clé est n bits, la taille de bloc est lbits et la taille de la sortie est L bit, droite. Donc au lieu de surpasser une fonction vraiment aléatoire, l'algorithme de génération de clé modifié va maintenant générer une clé uniformément aléatoire, qui sera disponible à la fois avec l'expéditeur et le récepteur. De la même façon, au lieu de calculer la valeur de la fonction vraiment aléatoire sur une entrée x pour générer le masque, et l'utiliser pour masquer le message, ce que nous allons faire c'est si l'expéditeur veut chiffrer un message de taille, L bits, il isva uniformément aléatoire de choisir une valeur x, évaluer la fonction pseudo-aléatoire à clé sur cette entrée x pour générer un bloc de taille L bit et XOR it avec le message. Par conséquent, nous sommes plus ou moins en train de faire le même processus que nous le faisons dans le processus de chiffrement à fonction vraiment aléatoire. La seule différence est qu'au lieu d'évaluer une fonction vraiment aléatoire sur une valeur x aléatoire, nous évaluons actuellement une fonction pseudo-aléatoire à clé par rapport à une clé uniformément aléatoire sur une valeur x uniformément aléatoire. Et le processus d'opération de déchiffrement modifié est analogue au processus de déchiffrement basé sur une fonction vraiment aléatoire. Si le récepteur voit un texte chiffré, il le transmet en tant que collection de pièce x et de texte chiffré réel. La partie x est utilisée pour évaluer la fonction saisie avec la même clé k disponible avec le récepteur pour générer le masque et cette XOR à partir du texte de chiffrement pour récupérer le texte en clair. C'est un schéma modifié pi. (Référez-vous à la diapositive: 22 :46) Et un énoncé de théorème que nous allons maintenant prouver est que si la fonction F est une fonction pseudo-aléatoire sécurisée, alors le schéma modifié est en fait un processus de chiffrement sécurisé CPA pour le chiffrement des messages de L bit. Et avant d'entrer dans la preuve réelle, comparons le processus de 2cryptage, sur votre partie gauche côté vous avez le processus de cryptage basé sur la fonction vraiment aléatoire, et dans votre partie droite, vous avez le processus de cryptage basé sur la fonction pseudo-aléatoire. Et quelle est la différence réelle entre ces deux processus de cryptage, la seule différence est la nature du masque. Dans le processus de chiffrement à fonction véritablement aléatoire, le masque a été généré par l'évaluation d'une fonction vraiment aléatoire inconnue dans laquelle la fonction n'était connue qu'à l'expéditeur et au récepteur. Alors que dans la construction à base de PRF, le masque est généré par l'évaluation d'une fonction pseudo-aléatoire à clé où la clé est maintenant aléatoire et connue uniquement à l'expéditeur et au récepteur, à droite, c'est la seule différence. Et nous avions déjà prouvé rigoureusement que le processus de cryptage basé sur des fonctions vraiment aléatoires est la CPA sécurisée contre n'importe quel adversaire délimité par ordinateur.Donc intuitivement la même devrait tenir même si je remplace toutes les instanciations de la fonction vraiment aléatoire par une fonction pseudo-aléatoire. Parce que maintenant, si après le remplacement de la fonction vraiment aléatoire et par une fonction pseudo-aléatoire le schéma modifié n'est pas sécurisé par CPA, cela signifie que nous avons maintenant un distinguisher, qui peut distinguer le comportement d'une fonction vraiment aléatoire f du comportement d'une fonction pseudo-aléatoire F (k). Mais c'est une contradiction avec l'hypothèse que nous faisons à propos de la fonction F étant une fonction pseudo-aléatoire sécurisée. Donc maintenant nous allons rigoureusement formaliser cette intuition grâce à une réduction. (Référez-vous à la diapositive: 24 :34) Donc maintenant, vous avez 3 entités ici vous avez le processus de cryptage basé sur une fonction vraiment aléatoire, que nous savons que CPA est sécurisé. Nous avons le schéma modifié basé sur une fonction pseudo-aléatoire. Et ces deux schémas sont sur le même espace de message des chaînes de bits de L. Et nous avons une fonction pseudo-aléatoire connue. Maintenant, imaginez que nous avons un adversaire A qui peut en fait gagner le jeu de sécurité CPA contre un système modifié Π. Maintenant en utilisant cet adversaire A, ce que nous allons faire, c'est que nous allons concevoir un distinguant, un distinguant PRF, qui peut distinguer la sortie d'une fonction pseudo-aléatoire de la sortie de ma fonction clé F, ce qui sera une contradiction. Alors, voyons comment fonctionne le distinguisher. Donc, le distinguisher agit essentiellement comme un vérificateur et appelle l'adversaire A de l'adversaire CPA A. Et une instance du jeu CPA est exécutée ou exécutée. Ainsi, selon les règles du jeu, l'adversaire demande les requêtes de cryptage, c'est-à-dire qu'il demande le service d'oracle de cryptage et qu'il lance un nombre de requêtes. Maintenant, pour chiffrer ces messages, ce que fait le distinguant, c'est qu'il choisit au hasard le nombre de valeurs x, à droite du domaine de la fonction clé F ou de la fonction vraiment aléatoire f, et il demande que les valeurs de fonction soient x valeurs et en réponse, il obtient les valeurs de fonction de la fonction sur ces valeurs x. Donc, cette partie de l'expérience est essentiellement le jeu de jeu PRF, où l'objectif de l'adversaire est de rechercher plusieurs nombres de x valeur de la fonction et obtient la réponse et en se basant sur la réponse, il doit savoir s'il a interagi avec une fonction vraiment aléatoire ou un pseudo Fonction aléatoire, alors que cette partie du jeu est votre droit de jeu CPA. C'est ainsi que vous pouvez imaginer le droit de réduction. Il s'agit donc de la première limitation de ce régime ou du premier inconvénient de ce régime, et non d'une limitation. Plus important encore, chaque instance du processus de chiffrement va nécessiter une nouvelle instance de caractère aléatoire, c'est-à-dire que la valeur x que nous utilisons pour générer le masque doit être fraîchement choisie pour chaque instance du processus de cryptage. C'est donc le deuxième inconvénient, parce que, dans la pratique, la création d'un caractère aléatoire uniforme est une tâche coûteuse sur le plan informatique. Il s'agit donc des 2 restrictions ou des inconvénients du système de PRF candidat que nous avons conçu ici. Au cours de la prochaine conférence, nous allons voir comment nous allons procéder pour nous débarrasser de ces 2 restrictions. En résumé dans cette conférence, nous avons vu un processus de cryptage des candidats basé sur une fonction pseudo-aléatoire, et nous avons vu une preuve de sécurité rigoureuse que nous pouvons réduire la sécurité globale de ce système construit à la sécurité de la fonction pseudo-aléatoire sous-jacente. Je vous remercie.