Loading
Study Reminders
Support
Text Version

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 – 6Introduction to Computational Security (Se reporter à la diapositive: 00 :31) Bonjour à tous, bienvenue à la conférence 6. Le plan de cette conférence est le suivant. Nous discuterons de la naissance de la cryptographie moderne, à savoir l'approche que nous utilisons dans la cryptographie moderne. Nous allons également discuter de la notion de sécurité computationnelle et des maux nécessaires qui sont associés à la sécurité informatique, et enfin, nous définissons mathématiquement ce que nous entendons par des algorithmes efficaces et une probabilité négligeable. (Référez-vous à la diapositive: 00 :54) Donc, juste pour rappeler au cours des deux dernières conférences, nous avons discuté de la notion de secret parfait, ce qui est toujours souhaitable parce que c'est la plus forte notion de secret que nous pouvons réaliser. Parce que le secret est atteint contre un adversaire qui est sans limite de calcul, dont le temps de fonctionnement est illimité, mais nous avons aussi discuté que nous devons payer un lourd tribut pour obtenir le secret parfait, à savoir dans tout processus de cryptage parfaitement sécurisé, votre clé doit être le plus grand comme un message et chaque instance du chiffrement doit utiliser une nouvelle clé.Donc ces 2 restrictions sont peu pratiques, parce que dans la pratique, nous visons à concevoir un processus de cryptage où nous pouvons utiliser une clé courte pour crypter de longs messages et nous aimerions avoir un schéma de chiffrement où la même clé courte pourrait être utilisée pour chiffrer la séquence de messages multiples. Cela signifie que le chiffrement pratiquement parfaitement sécurisé n'est tout simplement pas possible, c'est une sorte de tricherie. Donc, si quelqu'un prétend que son processus de cryptage est pratique aussi bien qu'il vous offre le secret parfait, alors c'est une tricherie claire, ce qui nous amène à l'approche que suit la cryptographie moderne. Le principe que nous suivons dans la cryptographie moderne est qu'au lieu de parvenir à un secret parfait, nous tenterons de nous rapprocher le plus possible du secret parfait et en retour, nous réaliserons deux objectifs pratiques que nous visons. Nous réalisons un processus de cryptage où nous pouvons utiliser la même clé courte pour crypter plusieurs messages. C'est donc le genre de compromis que nous utilisons dans la cryptographie moderne. (Référez-vous à la diapositive: 02 :35) Donc, voyons l'approche que nous utilisons dans la cryptographie moderne. Rappelez-vous, dans le modèle de secret parfait, notre adversaire est sans limite computationnelle et un objectif de secret dans le modèle du secret parfait est que nous voulons faire en sorte que l'adversaire n'apprenne absolument rien sur le texte en clair et ensuite nous formalisons rigoureusement cette notion: qu'est-ce que nous voulons dire par l'adversaire apprend absolument rien sur le texte en clair? Nous avons aussi discuté que les conséquences de cet objectif, à savoir l'objectif de réaliser que l'adversaire n'apprend absolument rien, c'est que vous devez avoir une clé aussi grande que le texte en clair et que vous ne pouvez pas vous permettre de réutiliser la clé. Donc, c'était les conséquences ou les restrictions du secret parfait. (Référez-vous à la diapositive: 03 :33) Maintenant, les changements que nous allons faire dans la cryptographie moderne sont les suivants: au lieu de supposer que notre adversaire est sans limite de calcul ou de calcul illimité, nous supposons que notre adversaire est des techniques limitées par le calcul, ce qui signifie que nous n'allons plus supposer que l'adversaire pourrait exécuter son algorithme pour briser le schéma ou attaquer le système pour une durée illimitée. Nous verrons comment formuler mathématiquement cette notion de l'adversaire délimité par les calculs. La seconde détente que nous allons faire dans le modèle du secret parfait est qu'au lieu de demander à l'adversaire d'apprendre absolument rien sur le texte en clair, nous nous sommes fixé pour atteindre l'objectif suivant: nous nous sommes fixé pour objectif de parvenir à ce que l'adversaire apprenne des informations supplémentaires sur le texte en clair avec une probabilité négligeable. Cela signifie que nous sommes maintenant prêts à laisser l'adversaire apprendre quelque chose sur le texte en clair, mais c'est une information supplémentaire ou la probabilité avec laquelle l'adversaire pourrait apprendre les informations supplémentaires est si faible qu'il est si négligeable que pour presque tous les objectifs pratiques que nous pouvons ignorer. (Référez-vous à la diapositive: 04 :42) Dès que nous faisons ces deux relaxations et le modèle de secret parfait, nous devrions espérer que nous devrions avoir les deux implications suivantes, à savoir que notre processus de chiffrement devrait utiliser la clé courte et que la même clé courte devrait être utilisable pour chiffrer une séquence de messages. Il s'avère que si nous faisons ces deux relaxations dans le modèle du secret parfait, nous pouvons atteindre les deux objectifs souhaités, à savoir la même clé courte peut être utilisée pour crypter la séquence de messages longs et c'est ce que l'approche de la cryptographie moderne. La notion de secret que nous obtenons en faisant ces deux relaxations est ce que nous appelons le secret computationnel, parce que la sécurité est atteinte contre un adversaire dont la puissance de calcul est maintenant limitée, plutôt que de dire que la puissance de calcul accusatoire est illimitée. Donc, c'est l'approche que nous allons suivre dans la cryptographie moderne (voir Diapositive: 05 :38) Donc les deux relaxations que nous allons faire est que nous cherchons maintenant à atteindre la sécurité uniquement contre des adversaires efficaces, et ce que je veux dire par un adversaire efficace est de manière informelle ces algorithmes ou ces algorithmes accusatoires dont le temps de fonctionnement est pratique ou dont le temps de fonctionnement qui prend un temps qui est faisable dans la pratique. Nous définissons mathématiquement ce que nous entendons exactement par des adversaires efficaces très bientôt. La seconde détente que nous allons maintenant faire est de supposer que les adversaires ont permis de briser le schéma avec une certaine probabilité, mais la probabilité avec laquelle l'adversaire peut casser le schéma est si petite que nous ne nous embêtons pas à une telle probabilité. Encore une fois, nous allons très bientôt mathématiquement et rigoureusement définir ce que nous entendons exactement par une si petite probabilité d'erreur. De plus, comme nous le verrons au cours du cours, au fur et à mesure que le cours se déroule, on suppose que, dans une certaine mesure, le temps que l'adversaire aura besoin de briser le schéma avec cette petite probabilité sera de l'ordre de quelques temps de vie. Cela contraste avec ce que nous réalisons dans le secret parfait. En secret parfait, même si nous donnons à l'adversaire un temps illimité, il n'y a absolument aucune probabilité qu'il apprend quoi que ce soit sur le texte sous-jacent. Mais dans la sécurité informatique, dans un modèle de sécurité informatique où notre but est d'atteindre une réutilisabilité clé si nous donnons beaucoup de temps à l'adversaire, alors il y a une chance que l'adversaire soit capable d'apprendre quelque chose sur le message sous-jacent, mais que quelque chose va être si petit qu'à des fins pratiques, nous pouvons l'ignorer. De plus, le temps qui va exiger pour l'adversaire d'apprendre le message, c'est une petite probabilité qui sera de l'ordre de quelques temps de vie. Il s'avère que cela est acceptable pour la plupart des applications pratiques parce que dans la plupart des applications pratiques, nous n'avons pas besoin d'une sécurité éternelle. Ce que je veux dire par cette dernière déclaration est le suivant: imaginez que vous voulez avoir un système sécurisé pour maintenir le secret de vos données de carte de crédit. Donc, si j'ai un processus de cryptage, qui garantit qu'il préservera la vie privée de vos coordonnées de carte de crédit, avec une grande probabilité. Cela signifie la probabilité que l'adversaire puisse apprendre les détails de votre carte de crédit en regardant dans le cryptage de vos coordonnées de carte de crédit avec très, très peu de probabilité et le temps que l'adversaire prendra pour en savoir sur vos coordonnées de carte de crédit est d'ordre dire 35 ans ou 40 ans, alors c'est bien parce que idéalement, vous exigerez que le secret de vos coordonnées de carte de crédit ne soit maintenu que pendant quelques années. Vous n'avez pas besoin du secret, ni de la confidentialité de vos coordonnées de carte de crédit à conserver pour toujours. C'est donc acceptable. Comme il s'avérera que plus de deux relaxations que nous faisons dans le modèle du secret computationnel sont absolument nécessaires si notre but ultime est de parvenir à la réutilisation des clés. En effet, dans les prochaines diapositives, nous allons discuter de ce que si nous voulons concevoir le processus de cryptage où notre objectif est de faire en sorte que la même clé courte soit utilisée pour chiffrer des messages multiples, alors il faut absolument que les deux relaxations dont je parle ici, à savoir la première relaxation, c'est que nous soyons prêts à laisser l'adversaire apprendre quelque chose sur le message sous-jacent avec une petite probabilité et une seconde détente, c'est que nous ne devrions cibler la sécurité que contre des adversaires efficaces. (Référez-vous à la diapositive: 09 :16) Voyons la nécessité de ces deux relaxations. Le premier assouplissement est que nous ne devrions maintenant cibler la sécurité que contre des adversaires efficaces. Donc, pour voir pourquoi cette relaxation est nécessaire, pensez à un processus de cryptage arbitraire, où vous allez utiliser la même clé pour crypter la séquence de messages et à savoir, la même clé va être utilisée pour crypter plusieurs messages. Et imaginez que nous sommes dans le modèle d'attaque du modèle d'attaque en clair (KPA). Juste pour vous rappeler, dans le modèle d'attaque de KPA, nous supposons que l'adversaire voit des cryptions de plusieurs messages, et cela signifie qu'il connaît à la fois les messages sous-jacents ainsi que leurs cryptions sous une clé inconnue, où la même clé va être conservée pour crypter les nouveaux messages. Imaginez que j'ai un processus de cryptage arbitraire, alors que l'expéditeur a des messages m1, m2. ..., mt et les algorithmes de chiffrement résultants sont C1, C2, ..., Ct et l'adversaire ont accès à ces paires (texte en clair, texte chiffré). Il sait que chacun des ciphertext de chacune de ces paires a le chiffrement du texte normal correspondant sous une clé inconnue k, que la clé n'est pas connue de l'attaquant. L'adversaire connaît également la description du processus de chiffrement et il sait aussi que la même clé inconnue k sera conservée par l'expéditeur pour le chiffrement de la séquence suivante des messages. Donc, dans ce scénario, l'adversaire peut toujours courir ce que nous appelons l'attaque de la récupération de la force brute. L'idée derrière cette attaque de récupération de la force brute est que ce que l'adversaire peut faire est qu'il connaît la description de l'espace clé, il peut essayer chaque clé candidate k appartenant à l'espace clé et déchiffrer chacun des codes de chiffrement dans ses paires de (??,???) Et voyez qu'il existe un candidat clé k ∈? Chacune des?? Dans ses paires de (??,??) De déchiffrer le texte normal correspondant sous cette clé candidate k?S'il le pouvait, il y a certainement un candidat clé k et dès qu'il a atteint la clé de ce candidat k, il peut trouver quelle est la clé que l'expéditeur va utiliser pour chiffrer la prochaine séquence de messages. Donc vous pouvez voir que la probabilité de succès de cette attaque par la force brute? une attaque de récupération en est une parce que pour certains k ∈?, telle que pour Deck (?? ): = ??, pour chaque (??,?? ), le temps de fonctionnement de cet algorithme de récupération de la force brute est? (|? |). Si nous supposons que notre espace clé est important pour nous, par exemple, imaginez que l'espace clé est l'ensemble de toutes les chaînes 256 bits possibles. Cela signifie que j'imagine que mon espace clé est 2256. Maintenant, cette force brute |? | = 2256 va prendre énormément de temps, c'est peu pratique. Cela signifie que si je fais la relaxation que je ne tolérerai pas ou que je ne suis pas dérangé par les adversaires dont le temps de fonctionnement est impraticable, alors cette attaque de récupération de la force brute ne sera pas considérée comme une attaque dans mon modèle d'attaque. C'est donc la nécessité de la première relaxation si votre but est de réaliser un schéma de chiffrement, où la même clé va être utilisée pour le chiffrement de plusieurs messages. Cela nous montre la nécessité de la première relaxation. (Référez-vous à la diapositive: 12 :54) Maintenant, voyons la nécessité de la seconde relaxation si votre but est d'atteindre la réutilisabilité des clés. La seconde détente est que vous devriez permettre que le schéma soit cassé avec une petite probabilité. Encore une fois, considérons une instance d'un processus de chiffrement arbitraire où la même clé k a été utilisée pour chiffrer plusieurs messages dans l'ordre et dire que l'adversaire est dans le modèle d'attaque KPA, où il a accès à plusieurs (??,??) Et la clé n'est pas connue de l'adversaire. Mais l'adversaire connaît le texte de chiffrement correspondant ou le cryptage du texte en clair correspondant dans chacune des paires, et l'adversaire sait que la même clé inconnue k sera conservée par l'expéditeur pour le cryptage de la séquence de message suivante. Maintenant, l'adversaire peut toujours lancer ce que nous appelons ça comme une attaque de devinage. L'idée qui sous-tend une attaque devine est l'adversaire peut simplement obtenir une valeur candidate de clé, dire k de l'espace clé et vérifier si cette clé candidate qu'il a deviné est effectivement la bonne clé ou pas en effectuant l'opération suivante: devinez aléatoirement un k ∈?, et vérifiez si Deck (?? ): = ??,, pour chaque (??,?? ), puis il a frappé la bonne clé. Maintenant, quelle est la probabilité de succès de cette attaque? La probabilité de succès de cette attaque est 1 / |? |. Quel est le temps d'exécution de l'attaque ou l'algorithme de l'attaquant ’? Le temps de fonctionnement de l'algorithme de l'adversaire est? (| 1 |) parce qu'il ne fait plus de force brute sur l'espace clé, il suffit de deviner la valeur de la clé candidate.Encore une fois, si je suppose que mon espace clé est extrêmement grand, cela veut dire imaginer à nouveau pour le moment que votre espace clé si l'ordre 2256, alors la probabilité de succès de cette attaque est de 1/2256, ce qui est très, très petit. Cela signifie que même si l'adversaire a une chance de rompre le schéma, c'est-à-dire d'apprendre la clé, la chance qu'il puisse apprendre la clé est si petite que, c'est 1/2256 que nous pouvons l'ignorer à des fins pratiques. Donc, ceci démontre une fois de plus que si la réutilisabilité clé est votre but ultime, alors nous devons faire la deuxième relaxation dans notre modèle, à savoir, nous devrions être prêts à laisser l'adversaire briser le schéma avec une probabilité plus faible et qui est si petit que nous pouvons l'ignorer. (Référez-vous à la diapositive: 15 :19) Donc, juste pour résumer les deux maux nécessaires qui sont associés à notre but ultime de réutilisation des clés sont les suivants. Il y a deux attaques possibles, deux attaques extrêmes qui peuvent toujours être lancées contre un schéma arbitraire où la réutilisation des clés est l'objectif ultime. La première attaque est l'attaque de récupération de la force brute, dont le temps de fonctionnement est très grand, mais la probabilité de succès est de 100%. Il y a la deuxième attaque extrême contre un tel schéma où la réutilisabilité est l'objectif, où le temps de fonctionnement de l'attaquant est très faible, mais la probabilité de succès de l'agresseur est très faible, il est si petit que pour la plupart des raisons pratiques on peut ignorer. Donc si vous voyez que si nous faisons les deux relaxations dont j'ai parlé, à savoir la première relaxation où nous ne visons à obtenir le secret que contre des adversaires efficaces, alors l'attaque par force brute ne serait pas considérée comme une attaque dans notre modèle d'attaque parce que comme je l'ai dit, la complexité du temps de la récupération de la force brute L'attaque sera énorme. Si je fais la deuxième relaxation, à savoir où je suis prêt à laisser l'adversaire apprendre ou casser le schéma avec une très faible probabilité d'erreur, alors la deuxième attaque, à savoir l'attaque clé de récupération ne serait pas considérée comme une attaque dans notre modèle d'attaque. (Référez-vous à la diapositive: 16 :42) Donc, c'est le résumé des deux maux nécessaires qui sont associés à tout processus de chiffrement, où la réutilisation des clés est l'objectif. La première relaxation que vous devriez faire dans votre modèle est au lieu de cibler la sécurité contre un adversaire sans limite de calcul, vous ne devriez cibler le secret que contre des adversaires efficaces sur le plan informatique. Et la seconde relaxation que vous devriez faire dans votre modèle est au lieu de demander qu'absolument rien sur le texte sous-jacent ne doit être révélé, vous devriez être prêt à laisser l'adversaire apprendre quelque chose sur le texte en clair sous-jacent avec une petite probabilité d'erreur et que la probabilité devrait être si petite que pour la plupart des fins pratiques, vous pouvez l'ignorer. Maintenant, les défis à savoir comment exactement nous définissons mathématiquement des adversaires efficaces, à savoir quels algorithmes, quel algorithme antagoniste, que vous pouvez dire est un algorithme de confrontation efficace? Le deuxième défi est de savoir quelles quantités vous définiront, ou vous appellerez une petite quantité ou une petite probabilité d'erreur. Donc, ce que nous allons faire ici, c'est que nous allons mathématiquement définir ces deux termes en notation asymptotique (voir la diapositive: 17 :53) Donc, les gens qui connaissent le concept d'algorithmes, ils sauront ce que nous entendons exactement par notation asymptotique. Donc, quand je veux mesurer le temps d'exécution d'un algorithme, il y a deux approches par lesquelles nous pouvons mesurer le temps d'exécution de l'algorithme. L'une est l'approche concrète, où nous comparons deux algorithmes pour le même but, basé sur le temps de fonctionnement exact. Donc, vous avez dit, algorithme 1 algorithme 2 pour une tâche. Vous exécutez l'algorithme 1 sur des échantillons de différentes tailles, vous exécutez l'algorithme 2 sur des échantillons de différentes tailles, puis vous comparez les délais exacts de l'algorithme 1 et de l'algorithme 2, bien sûr sur le processeur que vous avez donné et ainsi de suite. Sur la base de cela, vous comparez si l'algorithme 1 est meilleur? Ou l'algorithme 2 est mieux? Mais la chute de cette approche est même si vous obtenez la comparaison concrète de l'algorithme 1 par rapport à l'algorithme 2, cette approche ne prend pas en compte la vitesse de calcul sous-jacente, le progrès de la vitesse de calcul et ainsi de suite. La seconde approche que nous suivons dans le monde des algorithmes pour comparer 2 algorithmes est une notation asymptotique, où nous comparons le temps d'exécution des 2 algorithmes pour résoudre la même tâche dans des notations asymptotiques, à savoir en notation O. Nous comparons le temps d'exécution en mesurant le nombre d'étapes de base de l'algorithme 1 et le nombre d'étapes de base de l'algorithme 2 où le nombre d'étapes de base est calculé en fonction de la taille d'entrée. Selon l'algorithme qui prend moins d'étapes, nous définissons si l'algorithme 1 est meilleur? Ou l'algorithme 2 est mieux? Vous avez différentes notations asymptotiques comme la notation O, la notation thêta, la notation oméga basée sur laquelle vous pouvez comparer 2 algorithmes. Donc, quand nous voulons définir ce que nous entendons par efficacité, algorithme de probabilité négligeable dans le contexte de la cryptographie, nous allons suivre cette dernière approche, à savoir que nous allons définir ces termes asymptotiquement. Pour définir ces termes asymptotiquement, nous devons introduire quelque chose que nous appelons un paramètre de sécurité que nous dénotent par n. La raison pour laquelle nous voulons introduire ce paramètre de sécurité est qu'une fois que nous avons introduit le paramètre de sécurité n, alors toutes les trois quantitiesà savoir le temps d'exécution des utilisateurs, le temps d'exécution de l'algorithme de génération de clé, le temps d'exécution de l'algorithme de chiffrement, le temps d'exécution de l'algorithme de déchiffrement. De même, le temps de fonctionnement de l'algorithme de l'agresseur, et la probabilité de succès de l'attaquant, seront tous exprimés en fonction du paramètre de sécurité. Typiquement, dans le contexte du processus de chiffrement de clé symétrique, le paramètre de sécurité est la taille de la clé secrète, qui est généralement à des fins pratiques de 128, 256, et ainsi de suite. (Référez-vous à la diapositive: 20 :41) Donc, définissons d'abord ce que nous entendons par des algorithmes efficaces asymptotiquement. Informellement, nous disons qu'un algorithme est efficace si son temps d'exécution est une fonction polynomiale du paramètre de sécurité. Namely, Algorithm? A un temps d'exécution polynomial, s'il existe un polynôme? (.), par exemple pour chaque entrée? ∈ { 0, 1 } ∗, le calcul de? (?) se termine à l'intérieur? (|? |) étapes, où |? | indique la longueur de la chaîne? .Si c'est le cas, alors nous disons que notre algorithme A a du temps d'exécution polynomial et nous appellerons notre algorithme A pour être un algorithme efficace. Alors que, si nous ne pouvons pas respecter le temps de fonctionnement de notre algorithme A par une fonction polynomiale dans la taille de son entrée, alors nous disons que notre algorithme n'est pas efficace. C'est la définition d'un algorithme efficace. Maintenant, une fois que nous avons défini une notion d'algorithme efficace, l'exigence que nous mettons sur n'importe quel algorithme est la suivante: rappelez-vous que nous avons l'exigence de la correction, nous avons l'exigence de confidentialité, et à part que nous avons maintenant la troisième exigence de tout processus de cryptage. La nouvelle exigence est que le temps d'exécution de l'algorithme de génération de clés, l'algorithme de chiffrement et l'algorithme de déchiffrement devraient être une fonction polynomiale de ce paramètre de sécurité n. Si le temps de fonctionnement n'est pas une fonction polynomiale, alors nous ne considérerions pas que l'algorithme ou le code de chiffrement est un algorithme efficace. (Référez-vous à la diapositive: 22 :15) Maintenant, définissons la notion de probabilité négligeable en fonction du paramètre de sécurité. De façon informelle, nous disons qu'une fonction du paramètre de sécurité est négligeable si elle devient presque 0, la valeur de votre paramètre de sécurité n tend vers l'infini ou la fonction du paramètre de sécurité sera appelée comme une fonction négligeable si elle est asymptotiquement plus petite que l'inverse de chaque fonction polynomiale. Si f (n) est une fonction, alors nous dirons que f (n) est une fonction négligeable si pour chaque fonction polynomiale p (n), il existe une certaine valeur de n, à savoir N, de telle que f (n) est strictement inférieur à l'inverse de la fonction polynomiale p (n) pour toutes les valeurs de n > N. Si cela se maintient, alors nous disons que notre La fonction f (n) est une fonction négligeable. Une autre définition équivalente de cette fonction négligeable est pour chaque constante?, existe-t-il?, par exemple? (?) <? (−?), pour tous? >?, alors nous disons que notre fonction f (n) est une fonction négligeable. La raison pour laquelle ces 2 définitions sont équivalentes est que n'importe quelle fonction polynomiale (n), vous pouvez toujours l'écrire sous forme de nc. Donc, si f (n) est strictement inférieur à l'inverse de la fonction polynomiale pour chaque fonction polynomiale, alors je peux le réécrire comme? (?) <? (−?) pour chaque constante c.Donc, vous pouvez utiliser l'une de ces deux définitions pour prouver ou réfute si une fonction donnée f (n) est une fonction négligeable en n ou non. Donc, ici, par exemple, quelques fonctions qui sont toutes des fonctions négligeables. Chacune des fonctions est strictement inférieure à l'inverse de chaque fonction polynomiale, où la valeur de N est différente pour les fonctions polynomiales correspondantes. Donc, même si toutes ces fonctions sont des fonctions négligeables, c'est-à-dire si je continue à faire en sorte que la valeur de petite n soit grande et que n a tendance à l'infini, chacune de ces fonctions candidates deviendra nulle à la fin. Cependant, le taux auquel chacune de ces fonctions approche de zéro est différent. Par exemple, si je considère la fonction 2-nand si je considère la deuxième fonction, alors certainement 2-n approche la valeur zéro plus vite par rapport à la valeur de la fonction et ainsi de suite. D'autre part, si je considère la fonction 1 /n10, alors il ne s'agit pas d'une fonction négligeable. Parce que l'exigence d'une fonction négligeable est que la fonction doit être strictement inférieure à l'inverse de chaque fonction polynomiale, mais vous pouvez facilement voir que pour aucune valeur de n, la fonction, ce n'est pas possible pour chaque valeur de n. Par conséquent, elle enfreint la définition de la probabilité négligeable. (Référez-vous à la diapositive: 25 :34) Ainsi, nous avons défini mathématiquement ce que nous entendons par algorithme efficace et nous avons défini la probabilité que vous pouvez considérer comme une petite probabilité. Donc maintenant la famille de fonctions négligeables et polynomiales répondent à de jolies propriétés de fermeture. Voyons les propriétés de fermeture satisfaites par la classe des fonctions polynomiales. Donc, si vous considérez deux fonctions polynomiales arbitraires, dites P1 (n) et P2 (n), ainsi que les fonctions polynomiales. Quelle est l'implication de la première propriété de fermeture? Il dit que si vous avez deux sous-routines pour interpréter la première propriété de fermeture est la suivante: imaginez que vous avez deux sous-routines, où le temps d'exécution de la première sous-routine est une fonction polynomiale dans n et que le temps de fonctionnement de la seconde procédure est aussi une fonction polynomiale dans n, et si vous avez une routine plus grande, qui appelle en fait ces sous-procédures, alors le temps d'exécution de l'algorithme plus grand est aussi une fonction polynomiale, un algorithme plus grand qui cause ces deux fonctions plus petites dans l'ordre va aussi être considéré comme un algorithme efficace. Algorithme. C'est l'interprétation de la première propriété de fermeture. Juste pour résumer, dans cette conférence, nous avons discuté que si la réutilisation des clés est notre but ultime, à savoir si nous voulons concevoir un schéma où nous voulons conserver la même clé pour le chiffrement de multiples messages, alors nous devons faire des relaxations au modèle du secret parfait.La première relaxation que nous devons faire est qu'au lieu de supposer que notre adversaire est sans limite de calcul, nous devons supposer que notre adversaire est délimité par les calculs et que nous avons également vu que ce que nous entendons par, comment mesurer si le temps de l'adversaire est limité par le calcul ou non. De la même façon, la seconde détente que nous devons faire dans notre modèle est au lieu de dire que l'adversaire ne doit pas n'apprendre absolument rien sur le message sous-jacent, nous devrions donner à l'adversaire une chance de briser votre schéma. Cette possibilité de briser le système devrait être si petite que, pour la plupart des raisons pratiques, nous pouvons l'ignorer. Donc, nous avons aussi vu comment définir mathématiquement une si petite probabilité de rupture de l'adversaire. Nous avons vu que ces deux relaxations sont des maux nécessaires pour tout schéma de cryptage où l'objectif est de parvenir à une réutilisation des clés. Parce que si vous ne faites pas ces deux relaxations, alors il y a toujours des attaques extrêmes qui sont possibles, à savoir l'attaque de devinages et une attaque par force brute. La probabilité de succès de l'attaque de deviner sera très, très petite, mais le temps de fonctionnement de cette attaque sera pratique, alors que la probabilité de succès de l'attaque par la force brute sera de 100%, mais le temps de course de l'attaque par la force brute sera extrêmement grand. Donc, nous devons vraiment faire ces deux relaxations. J'espère que vous avez apprécié cette conférence. Je vous remercie.