Loading
Notes d'étude
Study Reminders
Support
Text Version

Instantiation de l'instanciation des GPR

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-11Provablement Secure Instantiation of PRGHello Tout le monde, bienvenue à la conférence 10, le plan pour cette conférence est le suivant. (Voir la diaporama: 00 :33) Dans cette conférence, nous discuterons de l'instanciation théorique de générateurs pseudo-aléatoires pour lesquels nous présenterons le concept d'une façon de fonctionner. Et après avoir introduit le concept d'une façon de fonctionner, nous verrons comment concevoir PRG avec un peu d'expansion et ensuite nous verrons comment concevoir PRG avec une expansion arbitraire. (Voir Diapositive Heure: 00 :53) Donc, la question que nous voulons répondre est celle de PRG. Donc, rappelez-vous que lors de la dernière conférence, nous avons vu que si vous avez un générateur pseudo-aléatoire, alors vous pouvez utiliser que vous pouvez concevoir des chiffrements de flux, ce qui vous permet de chiffrer de longs messages à l'aide de la clé courte. Donc, la question que nous ne voulons pas répondre est celle de ce PRG existant ou non. Et pour rappeler, un PRG est un algorithme déterministe qui prend une graine ou une entrée de bits de taille que nous dénotent par s. Et il développe sa production et produit une sortie qui est significativement plus grande que l'entrée et la sécurité de PRG signifie que la sortie de cet algorithme déterministe G doit être indiscernellement impossible à distinguer de la sortie d'un générateur vraiment aléatoire de la même taille, de droite. Il s'avère donc qu'il y a deux façons de concevoir les GPR. La première façon est de sécuriser les constructions de PRG d'une façon ou d'une autre, et quand je dis bien sûr je veux dire que les constructions que nous donnons en utilisant une voie de route pour que nous donnions une preuve que la construction est en effet PRG en ce sens qu'il n'existe pas de distinction de temps polynomial qui peut distinguer le résultat du PRG résultant du générateur de nombres aléatoires correspondant. Malheureusement, nous ne pouvons pas les utiliser dans la pratique parce que la quantité de calcul qui est impliquée dans la construction résultante est d'ordre de plusieurs ordres de grandeur. D'autre part, il y a des instanciations pratiques de pseudo-générateurs aléatoires, mais malheureusement ils ne sont pas sûrs dans le sens où nous pensons qu'ils sont sécurisés de façon heuristique parce que depuis leur construction, aucune faiblesse n'a été rapportée pour de tels générateurs pseudo-aléatoires, mais l'avantage de rechercher des générateurs pseudo-aléatoires est qu'ils sont super fast.Donc, c'est pourquoi dans la pratique nous préférons utiliser de tels générateurs. Une instanciation. Ainsi, l'accent sera mis sur les instanciations de construction de pseudo-générateurs pseudo-aléatoires à partir d'une seule fonction. Dans la photo suivante, nous allons discuter des instanciations pratiques de pseudo-générateur aléatoire (voir Diapositive Heure: 03 :00) Donc laissez-moi vous présenter le concept d'une façon de fonctionner ou OWF en abrégé, donc il s'agit d'une fonction du domaine de la chaîne de bits vers le codomaine de la chaîne de bits dénotée par f. Et, de manière informelle, c'est une fonction facile à calculer, mais difficile à inverser. Plus précisément, il y a 2 exigences de cette fonction. La première exigence est qu'il doit être facile à calculer. En effet, si vous avez une entrée x, calculez la valeur de la fonction sur cette entrée x temps polynomial, polynôme dans la taille de l'entrée x. La seconde condition, qui est la propriété intéressante de cette fonction unique est la propriété difficile à inverser, c'est-à-dire que si on vous donne un échantillon aléatoire y, du codomaine, alors trouver la préimage ou l'une des préimages de cette y en temps polynomial doit être difficile sauf avec une probabilité négligeable. Et cette propriété est modélisée par une expérience. (Voir Heure de la diapositive: 03 :58) Ainsi, dans cette expérience, on nous donne la description d'une fonction publique f. Et le nom de l'expérience est Invert, joué par rapport à un algorithme de temps polynomial dont l'objectif est d'inverser la sortie d'une fonction sur un échantillon aléatoire par rapport à la fonction f, et n est le paramètre de sécurité ici. Donc dans cette expérience, nous avons 2 entités, à savoir le vérificateur et l'adversaire. Donc les règles de l'expérience sont les suivantes: le vérificateur ici choisit un x aléatoire du domaine qui est une chaîne de bits arbitraire et calcule la valeur de la fonction sur cette entrée x, qui est donnée comme un défi pour l'adversaire. L'adversaire n'est donc pas au courant de l'entrée x, il ne voit que la sortie de la fonction sur l'entrée x, c'est-à-dire y et l'objectif ou le défi pour l'adversaire est d'inverser l'échantillon y à savoir de trouver au moins une des préimages de cette valeur donnée.Donc il soumet sa réponse, à savoir x ’ et nous disons que la fonction f a une propriété de wayness, iffor any polynomial time algorithme A participant à cette expérience il existe une fonction négligeable dire negl (n) telle que la probabilité est que la probabilité que l'adversaire est effectivement capable de générer x ’, ce qui est en fait une préimage de l'y est délimité par une fonction négligeable. Cela signifie que nous avons besoin qu'aucun algorithme de temps polynomial ne soit capable d'inverser cette ysauf aléatoire avec une probabilité négligeable. Donc, dans cette définition, l'exigence est que la probabilité de succès de cet adversaire pour inverser la y aléatoire doit être bornée par une fonction négligeable non pas par 0, parce qu'il existe toujours une stratégie de deviner par l'adversaire, à savoir l'adversaire peut simplement deviner un x ’ aléatoire.Et il existe toujours une probabilité non nulle que le deviné x ’ s'avère être l'une des préimages de l'y, c'est pourquoi dans la définition, nous n'avons pas besoin que nous n'appliquons pas que la condition qu'elle A soit capable d'inverser l'échantillon y devrait être bornée par 0, nous donnons l'effet de levier et la limite supérieure de la probabilité de succès de l'adversaire par une probabilité négligeable.Notez également qu'il n'est pas requis par l'adversaire de trouver le x exact, car la fonction peut être plusieurs à une fonction. Donc, il pourrait être possible que le même y qui est jeté comme un défi pour l'adversaire a plusieurs préimages. Le but de l'adversaire est de trouver l'une de ces préimages (voir Diapositive: 06 :25) Donc, voyons un exemple pour rendre notre compréhension claire, considérons la fonction f qui est une fonction 2entrée et la fonction est de l'ensemble des nombres naturels à l'ensemble des nombres naturels. Ainsi, la fonction prend 2 entrées de l'ensemble des nombres naturels et la sortie de la fonction est essentiellement le produit des 2 entrées. Maintenant, la question est cette fonction une fonction unique qui signifie que si quelqu'un vous donne la valeur de x point y, votre x et y ne sont pas connus de vous. Serez-vous capable d'inverser ou de trouver une des préimages à savoir une paire de x, y telle que le produit dont le produit est égal au produit donné en quantité polynomiale de temps, et il s'avère qu'ils existent, en effet, il existe en effet un algorithme simple pour trouver l'une des préimages et l'algorithme est comme suit. On vous donne donc un échantillon aléatoire z, qui est essentiellement la sortie de la fonction sur une paire d'entrées inconnues x, y. Et votre algorithme d'inversion est le suivant. L'algorithme vérifie si z est même ou non, si z est même alors l'algorithme génère la paire de préimages suivante, la première preimage x ’ est 2 et une seconde preimage y ’ est z/2. Donc, c'est une paire d'entrées qui vous donneraient la sortie z, alors que si l'échantillon z qui vous est donné est impair, alors vous sortirez aléatoirement x ’, y ’ sur l'ensemble de nombres naturels.Donc, il s'avère que la probabilité de succès de cet algorithme d'inversion est en fait 3 par 4. Parce que puisque la fonction est une fonction d'entrée de 2, les valeurs possibles de x, y peuvent être (impair, impair), (impair, pair), (même, impair) et (même, même). Et il s'avère que sur ces 4 combinaisons, pour 3 des combinaisons, votre z sera toujours même. Et si z est même et même l'algorithme d'inversion qui est utilisé ici, à savoir la sortie 2 et z/2 comme la préimage possible est un algorithme réussi. Le seul cas problématique est quand l'échantillon x, y est en fait une paire impaire et bizarre dans laquelle votre z peut ne pas être z ne sera pas un nombre pair, auquel cas vous pourriez être en train de mettre un x ’ incorrect, y ’. Donc, il s'avère que dans les trois quarts des instances, l'adversaire ou cet algorithme sera capable d'inverser avec succès la valeur donnée z. Par conséquent, cette fonction f n'est pas une fonction d'une seule façon parce que la probabilité de succès d'une inversion est de 3/4, ce qui est une quantité importante de probabilitité.Par contre, nous allons légèrement modifier cette fonction. Donc, ma fonction f (x, y) est toujours le produit de x et y mais au lieu de dire que x et y sont des nombres naturels aléatoires, mettez ici la restriction que x et y sont des nombres premiers aléatoires de la même taille. Et il s'avère que cette fonction est maintenant conjectuée d'être une fonction d'une façon si x et y sont de grands nombres premiers par ordre de 1024 bits. Donc je souligne ici qu'il est juste conjecturé que cette fonction f (x, y) où x et y sont des nombres premiers arbitraires de grande taille est une fonction unique car jusqu'à présent, nous n'avons pas d'algorithme de temps polynomial pour inverser cette fonction. Il n'est pas prouvé formellement qu'effectivement cette fonction est une fonction unique. Et plus tard, quand nous discuterons de la cryptographie à clé publique, et nous discuterons de la théorie des nombres où nous allons voir plusieurs fonctions de ce type, qui sont des conjectures sur plusieurs problèmes difficiles de théorème du nombre, donc pour le moment, nous croyons que cette fonction f (x, y) où x et y sont des nombres arbitraires importants et que la fonction est un produit de x et y est une fonction candidate. (Référez-vous à la diapositive: 10 :02) Maintenant, définissons un autre concept connexe, à savoir celui d'une façon de permutation ou d'OWP. Et fondamentalement une permutation d'une façon est une fonction d'une façon, qui se trouve aussi être une bijection. Le mappage est maintenant un mappage un sur un. Cela signifie que chaque y du codomaine aura une préimage unique. Et l'exigence ou la partie difficile à inverser pour une permutation d'une façon est que si on vous donne un caractère aléatoire à partir du codomaine, le défi pour l'adversaire est de trouver une préimage unique x qui aurait en fait donné cette y en quantité polynomiale de temps. Donc la différence ici est pour le cas d'une façon de fonctionner, le challenge aléatoire y pourrait avoir plusieurs préimages et votre but était de trouver une de ces préimages. Dans le cas d'une permutation d'une façon, l'échantillon aléatoire y qui est donné à vous n'aura qu'une préimage unique. Et votre but est de trouver cette préimage unique et le temps polynomial. Notez que dans le cas d'une façon fonctionnelle aussi bien que d'une manière permutation, nous mettons la restriction que l'algorithme d'inversion doit prendre le temps polynomial. Parce que si nous ne mettons aucune restriction sur la quantité de temps, qui est donnée à l'algorithme d'inversion, alors il existe toujours un algorithme de force brute, à savoir, l'algorithme peut essayer sur tout le candidat possible x de l'ensemble de la candidate x et certainement il frapperait sur un x qui sera donné au hasard y qui est jeté comme le défi, mais le temps d'exécution de cet algorithme de force brute sera exponentiellement ou il sera Et la taille du domaine est exponentiellement grande que les algorithmes d'inversion du temps sont aussi exponentiels. Donc, c'est pourquoi dans l'expérience, où nous modélisons la partie d'inversion à la fois pour la fonction d'une façon aussi bien que pour la permutation, nous mettons la restriction que le temps de fonctionnement de cet adversaire devrait être polynomial. (Référez-vous à la diapositive: 11 :52) Alors, discutons maintenant d'un autre concept intéressant, à savoir celui du prédicat dur qui sera utile lorsque nous concevrons notre candidat pseudo-générateur aléatoire d'une façon à l'autre et que la motivation de ce prédicat dur est la suivante. Alors imaginez que vous avez une fonction f, qui est une fonction d'une façon ou une permutation d'une façon. Et si on vous donne la valeur de la fonction sur une entrée aléatoire x, alors il est difficile de calculer la totalité de x en quantité polynomiale est difficile. Parce que c'est ce qui est la propriété d'une fonction d'une façon ou d'une permutation d'une façon, mais cela ne signifie pas nécessairement que vous ne pouvez pas calculer quelque chose à propos de x en temps polynomial, il peut y avoir des informations sur x, que vous pouvez calculer à partir de la valeur de f (x) en quantité polynomiale de temps. Pour que le point soit plus clair, considérez la fonction?: { 0, 1 } ∗ → { 0, 1 } ∗ et dites que cette fonction f est une fonction d'une façon et utilise cette fonction que nous concevons une autre fonction g, qui est maintenant une fonction 2entrée et la fonction g sur la paire d'entrée x1, x2 est définie comme la sortie composée de x1 comme elle est, et la seconde partie de la sortie de cette fonction g est en fait la valeur de la fonction f sur la seconde partie de l'entrée, à savoir x2,? (x1, x2) = (x1,? (x2)). Je suis en mesure de définir ma fonction g. Et mon affirmation est que si la taille de x1 et x2 est à peu près la même, à savoir une fonction polynomiale dans le paramètre de sécurité, alors si la fonction f avec laquelle nous commençons est une fonction d'une façon, alors la fonction construite g, qui est construite comme ceci est aussi une fonction à sens unique. Donc en gros, l'idée ici est que si g n'est pas une fonction d'une façon, cela veut dire si quelqu'un vous donne la valeur g (x1, x2), et vous pouvez en fait trouver x1, x2 en quantité polynomiale de temps. Ensuite, intuitivement à l'aide de cet algorithme, vous pouvez également calculer la valeur de x2 en utilisant seulement f (x2), de sorte que nous pouvons formellement établir son fait à l'aide d'un argument de réduction. Je ne vais donc pas dans l'argument de la réduction. Mais fondamentalement, l'idée ici est que si f est une façon de fonctionner et la fonction g, qui est une fonction de 2 entrées construite comme ceci est aussi une fonction d'une façon fournie à la fois x1 et x2 sont à peu près la même taille e.Maintenant, si vous voyez la fonction g, il s'avère que même s'il s'agit d'une fonction d'une façon, en voyant la sortie de cette fonction g sur une paire aléatoire d'entrée, vous finitiez en fait à apprendre la moitié de l'entrée, pas vrai. Parce que la première moitié de la sortie est en fait la première moitié de l'entrée telle qu'elle est. En ce sens, même si cette fonction g est une fonction unique, il n'est pas vrai que si je vous donne la valeur de cette fonction g sur une paire arbitraire d'entrée, vous ne pouvez pas calculer la totalité de l'entrée dans le temps polynomial. Il y a quelque chose que vous pouvez calculer, il y a quelque chose que vous ne pouvez pas calculer en quantité polynomiale de temps. Donc cette notion de prédicat dur modèle avec précision, quel est le temps polynomial calculable à partir de la valeur de la fonction f (x) sur l'entrée aléatoire x, droite. (Voir la diapositive Heure: 15 :01) Donc voyons la définition formelle de ce prédicat dur. Donc, imaginez que vous êtes donné une fonction d'un domaine de chaîne de bits au codomaine de la chaîne de bits et j'insiste sur le fait que la fonction peut ne pas être une fonction unique elle pourrait être une fonction normale. Donc, nous avons une fonction f et correspondant à la fonction f nous définissons une autre fonction hc qui est une fonction booléenne qui signifie, il faut une chaîne binaire arbitraire comme entrée et elle produit une sortie booléenne 0, 1.Et puis nous voyons que cette fonction hc associée à une fonction f est un prédicat dur si les deux conditions suivantes sont réunies. Donc, la première condition est que si vous avez un texte d'entrée aléatoire et que vous calculez la valeur de cette fonction, prédicat dur, c'est-à-dire hc de f doit être un temps polynomial calculable qui signifie que vous devriez être en mesure de calculer la valeur de hc de x en polynôme de temps polynomial dans la taille de l'entrée x. La seconde propriété intéressante qui fait en fait un prédicat dur très intéressant est la suivante que si on donne la valeur de f (x) pour un x choisi au hasard, alors il n'est pas possible de calculer la valeur de hc (x) avec probabilité significativement meilleure que la moitié en quantité polynomiale de temps. Cela signifie que le défi ici est que si je vous donne f (x) et que je ne veux pas vous dire la valeur de x, où x est choisi au hasard, alors même après apprentissage f (x), nous ne devrions pas être en mesure de calculer la valeur de la fonction hc de x dans le temps polynomial, sauf avec la probabilité, négligeable meilleur que la moitié. Si c'est le cas, alors nous disons que la fonction hc (x), hc est le prédicat fort dur associé à la fonction f. Donc cette exigence de l'incapacité de calculer la valeur de hc (x) avec une probabilité significativement meilleure que la moitié par un algorithme de temps polynomial est modélisée par une expérience que nous appelons "expérience dure". Et maintenant, cette expérience est conçue en fonction d'une fonction f qui est connue publiquement, qui est une fonction candidate qui pourrait être candidate à une fonction ou une façon de permutation ou qui pourrait simplement être une fonction et associée à la fonction f nous avons un prédicat de noyau dur candidat, qui est une fonction booléenne et l'expérience implique 2 entités. La règle de l'expérience est donc la suivante: le vérificateur choisit ici un x aléatoire du domaine, calcule la valeur de la fonction sur cette entrée x. Et la production correspondante y est donnée comme un défi pour l'adversaire. Et l'objectif de l'adversaire ou le défi pour l'adversaire est après avoir vu la valeur de y il doit calculer la valeur de hc (x) sans connaître le x. Donc, dire hc (x) va être un peu la sortie de l'adversaire un peu qui pourrait être 0 ou 1.Et nous disons que l'adversaire a gagné le jeu si en fait b = hc (x). Ainsi, nous disons que la fonction hc associée à la fonction f est un prédicat dur, si pour n'importe quel algorithme de temps polynomial participant à cette expérience, la probabilité que les sorties adverses b où b est en fait égal à hc de x est délimitée par la moitié plus une probabilité négligeable ou une fonction négligeable dans le paramètre de sécurité. Si c'est le cas, alors nous disons que la fonction hc est un prédicat dur associé à la fonction f. Donc, l'avis est en définition, nous avons limité la probabilité de succès de l'adversaire à être à moitié plus négligeable, nous n'avons pas besoin que la probabilité de succès de l'adversaire soit 0, parce qu'il ya toujours une stratégie de deviner ou de deviner l'adversaire qui peut juste deviner un bit et il y a toujours une probabilité de 1/2 que l'invité est effectivement la valeur de hc (x) correctement.En dehors de cela, nous sommes également prêts à donner à cet adversaire un avantage supplémentaire négligeable et à dépasser avec succès le prédicat, parce que nous sommes dans un monde de sécurité informatique. Donc, c'est la définition du prédicat dur (voir la diapositive: 18 :53) Donc maintenant la question est, si on nous donne une fonction candidate ou un mode de permutation, il y a un prédicat de noyau dur associé ou non. Et il s'avère que c'est intéressant, la réponse est oui. Et c'est à cause d'un théorème très fondamental et de la cryptographie, qui est aussi appelé théorème de Goldreich-Levin. Et le théorème de Goldreich-Levin vous montre essentiellement comment construire un prédicat dur associé à une fonction quelconque, ou à une permutation d'une façon donnée. Donc, nous ne nous allons pas dans la preuve du théorème de Goldreich-Levin, nous allons voir à peu près le théorème et l'intuition de la sécurité. Le théorème est donc comme suit. Alors imaginez que vous vous êtes donné un candidat une façon fonctionnelle de dire f ou un candidat une façon de permutation. Maintenant l'utilisation de cette fonction candidate f, nous construisons une fonction d'entrée g, et la construction de gis comme suit. Donc il passe l'entrée comme x, r. Et la sortie de g est définie comme suit. Nous évaluons donc la fonction f sur la première partie de l'entrée de g. Cela constitue la première partie de la sortie de g, et la seconde partie de l'entrée de g est copiée telle qu'elle est dans la sortie du g. Et ici la taille des 2 entrées de g, à savoir x et r sont de même ordre. C'est ainsi que nous définissons notre fonction g. Maintenant nous pouvons prouver formellement que si la fonction f avec laquelle nous commençons avec est une fonction d'une façon ou une façon de permutation, alors la fonction g que nous avons construite comme (f (x), r) est aussi une fonction d'une façon ou une façon de permutation, respectivement.Et la preuve est par un argument de réduction. À savoir, nous pouvons montrer que si vous avez un algorithme de temps polynomial pour inverser la sortie de la fonction g que vous avez construite sur une paire aléatoire d'entrée x, r. Cela signifie que si vous avez un algorithme qui sans connaître la paire aléatoire d'entrée x, r, mais simplement voir la valeur de g (x, r) peut vous redonner x, r en quantité polynomiale de temps. Ensuite, en utilisant le même algorithme d'inversion, nous pouvons construire un autre algorithme de temps polynomial, qui lorsqu'on lui donne la valeur de f (x) sur un x aléatoire sans connaître la valeur de x peut en fait vous redonner la valeur de x, ce qui est une contradiction avec le fait que f est une fonction à une façon ou une permutation d'une façon. Donc, maintenant, nous nous concentrerons sur la fonction g. Et ce que Goldreich-Levin théorème vous montre fondamentalement que si cette fonction g est une fonction d'une façon, alors nous pouvons associer un prédicte du noyau dur correspondant à cette fonction g. Le prédicat dur est la fonction booléenne, qui prend essentiellement la combinaison linéaire aléatoire des bits de l'entrée x, de droite. Ce que nous considérons ici, c'est que votre r est interprété comme une chaîne de longueur n, et que votre x est aussi considéré comme une chaîne de longueur n, il s'agit des 2 entrées pour la fonction g, et le prédicat noyau dur associé, qui est associé à la fonction g, est noté par la fonction gl. Et la fonction gl est essentiellement une combinaison linéaire aléatoire des bits du x, où les combinateurs sont définis par la représentation binaire de l'entrée r. Et ce que le théorème de Goldreich-Levin prétend fondamentalement que cette fonction gl (x, r) est le prédicat noyau dur associé à la fonction g. Cela signifie que si quelqu'un vous donne la valeur de la fonction g (x, r), pour un aléatoire x et r, alors, sauf avec la probabilité à moitié plus négligeable aucun algorithme de temps polynomial ne peut calculer la valeur de gl (x, r). Et l'intuition derrière cela la preuve du théorème de Goldreich-Levin est que même si vous êtes donné f (x) puisque vous ne connaissez pas la valeur de x, fondamentalement le défi pour le calcul du Goldreich gl, la sortie de la fonction gl (x, r) est essentiellement de calculer la XOR des sous-ensembles aléatoires du bit de x, mais puisque l'adversaire ne connaît pas les bits exacts de x, il sera difficile pour l'adversaire de calculer que XOR des sous-ensembles aléatoires des bits de x. C'est essentiellement l'intuition de ce théorème. Cependant, il s'avère que la preuve de ce théorème est en effet difficile et involved.Donc, les étudiants qui sont intéressés à passer par la preuve de ce théorème de Goldreich-Levin ils peuvent se référer au livre de Katz et Lindel, où ils ont donné la preuve détaillée, mais pour notre discussion, nous supposerons que la fonction gl (x, r) est associée à notre candidat une façon de fonctionner g (x, r) à droite. (Voir Diapositive Heure: 23 :36) Donc, en supposant que nous avons maintenant un prédicat dur, et que nous avons une permutation d'un candidat nous voyons comment on peut construire PRG avec un minimum L'extension, et ce que nous entendons par extension minimale, c'est que nous supposerons que nous sommes donnés à un candidat des permutations à partir de l'ensemble des chaînes de n bit à l'ensemble de chaînes de n bit. Cela signifie que la fonction f prend une entrée qui est une chaîne de longueur n et elle produit une sortie qui est aussi une chaîne de longueur n. Et c'est une permutation d'une façon. Et associé à la fonction f, nous avons un coreprédicat dur. Maintenant, nous allons construire un générateur pseudo-aléatoire où la construction du pseudo-générateur aléatoire est la suivante. En effet, nous pouvons prouver qu'il n'existe pas de distinction de temps polynomial pour notre construction, sinon elle se réduit à la sécurité de la fonction sous-jacente d'une façon et du prédicat dur. J'espère que vous avez apprécié cette conférence. Je vous remercie.