Loading
Notes d'étude
Study Reminders
Support
Text Version

Sécurité sémantique

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 ProfessorInternational Institute of Information Technology – BangaloreLecture – 7Semantic Security (Référez-vous à la diapositive: 00 :32) Bonjour à tous, bienvenue à la conférence 7. Le plan de cette conférence est le suivant. Nous définissons la notion de sécurité sémantique dans le modèle de chiffrement uniquement et nous allons voir une version équivalente de cette définition basée sur le jeu d'indistinction et nous allons également introduire des preuves basées sur la réduction qui sont au cœur de la cryptographie. (Voir Heure de la diapositive: 00 :51) Donc, commençons par la définition de sécurité sémantique dans le modèle d'attaque du texte de chiffrement seulement et le scénario est le suivant. Donc, nous sommes dans le modèle d'attaque seulement où nous avons un adversaire, et maintenant nous allons considérer un adversaire délimité par les calculs. Parce que rappelez-vous, lors de la dernière conférence, nous avons discuté que si la réutilisation des clés est votre but ultime, alors vous devez vous assurer que votre adversaire est calcultationnellement illimité. Donc, nous supposons que nous avons un adversaire calculé sur le plan informatique, qui voit un texte chiffré c d'un message inconnu m chiffré par l'expéditeur à l'aide d'une clé inconnue k selon l'algorithme de chiffrement, où les étapes de l'algorithme de chiffrement sont connues de l'adversaire. Intuitivement, nous dirons que notre processus de cryptage est sûr sémantiquement dans ce modèle de chiffrement uniquement si le texte de chiffrement ne révèle pas d'informations supplémentaires sur le texte en clair sous-jacent à l'attaque.En outre, cela devrait tenir même si l'adversaire a des informations externes sur le texte en clair sous-jacent, qui auraient pu être divulgués à l'agresseur par tout autre moyen avant que le texte de chiffrement n'ait été communiqué. Même si cette intuition est très simple à comprendre, il est extrêmement difficile de formaliser l'intuition ci-dessus. Alors, passons à formaliser cette intuition, à droite. (Référez-vous à la diapositive: 02 :11) Ainsi, nous introduisons ici une fonction abstrai, à savoir h (m), qui modéle tout type d'information externe préalable sur le texte en clair sous-jacent, qui pourrait être divulgué à l'adversaire par d'autres moyens avant que n'importe quel texte chiffré ait été communiqué. Donc, ce h (m) est une sorte de fonction de l'histoire. Il se peut qu'il y ait dans un certain contexte ou dans un scénario où l'adversaire n'aurait absolument aucune information externe préalable, dans ce cas, ma fonction h (m) sera une fonction vide, mais il pourrait y avoir un scénario où l'adversaire pourrait avoir des informations externes sur le texte en clair sous-jacent, qui a été divulgué à l'adversaire par d'autres moyens. Donc, quel que soit le cas, nous introduisons cette fonction abstraise pour modéliser cette information externe antérieure sur le texte en clair sous-jacent, que l'adversaire a. Nous allons ensuite introduire une autre fonction f (m), qui modérait essentiellement les informations supplémentaires sur le texte en clair sous-jacent, que l'adversaire aimerait calculer après avoir vu le texte chiffré ou que l'adversaire aimerait savoir, n'est-ce pas? Donc, ce modèle les informations supplémentaires et intuitivement, le but de la sécurité sémantique est de s'assurer de ce qui suit. Nous disons que notre processus de cryptage est sûr sémantiquement si la probabilité avec laquelle l'adversaire peut calculer ces informations supplémentaires, à savoir la fonction f (m) en utilisant le code de chiffrement et en utilisant l'aide de la fonction d'historique ou les informations précédentes est presque la même avec laquelle l'adversaire aurait pu calculer la fonction f (m) en utilisant juste les informations précédentes en l'absence du texte chiffré. Si c'est le cas, alors l'implication que nous obtenons ici est que le texte chiffré n'est d'aucune aide pour l'attaquant dans le calcul de f (m). (Référez-vous à la diapositive: 04 :04) Ce que je veux dire par là est le suivant. Donc vous imaginez que dans ce monde, nous avons un adversaire, qui voit en fait un texte chiffré, qui est un cryptage d'un message inconnu sous la clé inconnue et que l'adversaire a aussi accès à la fonction d'histoire, à savoir tout type d'information préalable, qui aurait été divulguée à l'adversaire par un mécanisme externe sans la connaissance du texte chiffré. Donc l'adversaire dans ce monde est appelé A. Vous comparez en imaginant un autre monde où nous avons encore un autre adversaire, par exemple A ’, qui ne voit pas le texte chiffré et cet adversaire A ’ n'a accès qu'à la fonction d'historique, à savoir les informations préalables sur le texte en clair sous-jacent, que l'expéditeur peut communiquer sur le canal. Maintenant, l'intuition derrière la sécurité sémantique est que la probabilité avec laquelle A et A ’ pourrait calculer le f (m), à savoir les informations supplémentaires sur le texte explicité sous-jacent sont presque identiques, à savoir, nous dirons que notre processus de chiffrement est sécurisé sémantique dans le modèle d'attaque de chiffrement si la différence absolue entre les deux probabilités suivantes est bornée par une fonction négligeable. Alors, nous voyons plus près. Examinons de plus près ces probabilités respectives, à savoir: ?? [? ? ???? , h? =?? ] et?? [? ’ (h (?)) =? (?) ] Donc votre première probabilité est la probabilité avec laquelle l'adversaire A, à savoir l'adversaire dans le premier monde, génère la valeur de f (m), où l'adversaire est donné le texte de chiffrement ainsi que la fonction d'historique. Alors que la seconde probabilité est la probabilité avec laquelle l'adversaire dans le deuxième monde, à savoir l'adversaire A ’, calcule la valeur de f (m) juste à l'aide de la fonction de la valeur de l'histoire. Donc si la différence absolue entre ces deux probabilités est bornée par une probabilité négligeable, alors ce que cela signifie, c'est que n'importe quel adversaire aurait pu calculer en voyant le texte, c'est-à-dire tout ce que l'adversaire aurait pu connaître à propos de f (m) en utilisant l'aide de c avec presque la même probabilité que l'adversaire aurait pu calculer f (m) sans vraiment voir le c. Si c'est le cas, alors cela signifie que notre processus de cryptage est si bon que le chiffrement est une sorte de chaînes de bits aléatoires, et qu'il aide ou ne fournit aucune sorte d'aide à l'adversaire dans le calcul de f (m) avec un avantage significatif, c'est-à-dire l'intuition derrière la notion de sécurité sémantique (voir Diapositive: 06 :42) Donc il s'agit de la définition d'origine de la sécurité sémantique, et il s'avère que si nous voulons prouver la sécurité sémantique d'un processus de cryptage arbitraire selon cette définition d'origine, alors c'est un peu compliqué, où parce qu'ici vous devez apporter aussi la fonction d'historique Comme ici vous devez apporter la fonction arbitraire f (m) que l'adversaire aimerait calculer. Ce que nous allons faire, c'est que nous allons voir une version équivalente de cette définition basée sur une expérience basée sur l'indistinction. Cette définition alternative basée sur l'expérience basée sur l'indistinction, vous pouvez imaginer que c'est la variante de l'indistinction basée sur la définition de l'indistinction basée sur la définition du secret parfait, à droite. (Voir la diapositive: 07 :27) Donc, rappelons d'abord la définition basée sur l'indistinction que nous utilisons pour définir le secret parfait. Ainsi, l'essence de cette définition d'indistinction basée sur la définition du secret parfait est que si vous avez un scénario où un expéditeur a 2 messages m0 ou m1 et qu'il a crypté au hasard un de ces messages, et si l'adversaire est conscient du fait que l'expéditeur a soit chiffré m0 ou m1, alors même après avoir cette information préalable et vu le texte chiffré c, l'adversaire ne devrait pas être en mesure d'identifier ce qui a été chiffré dans le code de chiffrement c avec une probabilité meilleure que la moitié. C'était l'intuition que nous voulions saisir par l'indistinction de la définition basée sur le secret parfait. Cette expérience a été très bien capturée par l'expérience suivante, à droite. Donc c'est l'expérience, que nous utilisons pour définir la notion de secret parfait, où nous avons un schéma connu publiquement, à savoir un triplet d'algorithmes sur un espace de message, et dans le modèle du secret parfait, nous avions un adversaire sans limite de calcul, et le nom de l'expérience était ceci:? ?????, Π? ??. Pour rappel, la nomenclature de l'expérience est la suivante. PrivK signifie que nous voulons modéliser une expérience, qui dans le contexte d'une clé privée ou d'un chiffrement symétrique, eav signifie que nous envisageons un adversaire qui est une écoute, A est le nom de l'algorithme du contradictoire et Π est le nom du schéma, et dans cette expérience, les règles sont les suivantes. Adversary est autorisé à soumettre n'importe quelle paire de messages à partir de l'espace de texte en clair avec la restriction que la taille du texte en clair doit être identique, et l'expérience ou le vérificateur, le vérificateur hypothétique fait ce qui suit: Il génère au hasard une clé en exécutant un algorithme de génération de clé et il chiffre au hasard un des messages utilisant la clé, et le défi pour l'adversaire est d'identifier ce que le texte en clair a été chiffré dans le texte de chiffrement défi c, qu'il soit m0 ou m1. Donc les sorties adverses un peu, à savoir sa supposition sur ce qui a été crypté dans le texte de défier le texte. Nous définissons le schéma Π pour être parfaitement sécurisé ou nous disons qu'un schéma est parfaitement indiscernable si la probabilité avec laquelle l'adversaire a pu identifier avec succès quel message a été crypté est délimitée par la moitié. Donc si l'adversaire pouvait identifier avec succès quel message a été chiffré dans le texte de chiffrement du défi, alors nous disons que l'adversaire a gagné le jeu ou nous disons que la sortie de l'expérience est égale à 1. Cela signifie que cette notation que la sortie de l'expérience est 1 indique la probabilité que b ’ égal à b. Donc, dans le contexte du secret parfait, notre exigence était qu'un adversaire de probabilité puisse identifier b, b ’ égal à b correctement doit être délimité par la moitié. (Voir Heure de la diapositive: 10 :25) Maintenant, voyons la définition basée sur l'indistinction pour modéliser la notion de sécurité sémantique dans le modèle de chiffrement uniquement. Nous allons apporter les changements suivants. Le premier changement que nous allons faire est le suivant. Au lieu de supposer que notre adversaire est sans limite de calcul, nous supposerons que notre adversaire est délimité par des calculs. C'est pour modéliser la première relaxation que nous avons convenue que nous devrions faire dans le modèle de sécurité informatique. Donc, souvenez-vous de la dernière conférence dont nous avons discuté que si la réutilisabilité clé est votre but ultime, alors nous ne devrions viser à atteindre la sécurité qu'à l'encontre d'un adversaire délimité par les calculs, à savoir un adversaire dont le temps d'exécution est délimité par une fonction polynomiale du paramètre de sécurité. Donc, c'est pourquoi nous avons fait ce premier changement dans l'expérience, nous ne réfléchissons pas à un adversaire dont le temps de fonctionnement est sans limite de calcul. Par conséquent, le nom de l'expérience va être? ?????, Π??? Donc, au lieu de dire EAV, j'appelle maintenant cette expérience ACO pour indiquer qu'il s'agit de l'expérience d'indistinction dans le modèle d'attaque de chiffrement uniquement et que la seconde différence dans la nomenclature est que je suis en train d'introduire ce paramètre de sécurité n parce que le temps de fonctionnement de l'adversaire va être délimité par une fonction polynomiale du paramètre de sécurité, alors que si vous voyez dans la nomenclature pour l'expérience basée sur l'indistinction dans le monde du secret parfait, aucun paramètre de sécurité de ce type n'était là parce que notre adversaire était autorisé à avoir un fonctionnement illimité Donc c'est la seconde détente. C'est le deuxième changement de l'expérience, et le troisième changement est qu'au lieu de dire que notre processus de cryptage est parfaitement indiscerne, nous dirons que notre processus de cryptage est indiscerne de l'informatique. Si la probabilité avec laquelle l'adversaire a pu identifier correctement ce qui a été crypté dans le texte de chiffrement est délimitée par une fonction négligeable plus la moitié, c'est un troisième changement que nous allons faire dans notre expérience. Donc dans l'expérience pour le secret parfait, l'exigence était que l'adversaire ne devrait pas être capable d'identifier ce qui a été crypté dans le texte de chiffrement avec une probabilité meilleure que la moitié, mais maintenant nous donnons à l'adversaire un avantage supplémentaire négligeable pour identifier correctement ce qui a été crypté dans le texte de chiffrement défi c. Cet avantage supplémentaire, à savoir un avantage de fonction négligeable et l'avantage d'une probabilité négligeable, est de modéliser la seconde relaxation que nous avons à faire dans le modèle de sécurité informatique si la réutilisabilité clé est votre but ultime. Donc, rappelez-vous lors de la dernière conférence, nous avons vu que si vous voulez concevoir un schéma où la réutilisation des clés est votre but ultime, qu'au lieu d'exiger que l'adversaire n'apprenne rien de plus, vous devriez être prêt à laisser l'adversaire apprendre quelque chose sur votre message sous-jacent ou laisser l'adversaire briser votre schéma avec d'autres Probabilité et que la probabilité supplémentaire devrait être si faible dans laquelle elle devrait être une probabilité négligeable, ce qui pour la plupart des raisons pratiques vous pouvez l'ignorer. C'est pourquoi j'apporte cet avantage supplémentaire de fonction négligeable de n dans ma définition de sécurité. Il s'agit donc de l'expérience de la version basée sur l'indistinction basée sur l'indistinction dans le modèle d'attaque de chiffrement uniquement. L'essence de cette expérience est donc la suivante. Ce que nous voulons saisir par cette expérience est le suivant. Si vous avez un scénario où un expéditeur a une paire de message, par exemple m0 et m1 et si l'adversaire est conscient de cela là où notre adversaire est délimité par les calculs, si l'un de ces 2 messages m0ou m1 a été crypté par l'expéditeur et communiqué au récepteur et que notre adversaire intercepte un texte chiffré, alors nous avons besoin de la propriété suivante de notre processus de cryptage. Nous avons besoin qu'un adversaire délimité par ordinateur ne soit pas en mesure de déterminer si le chiffrement c qu'il voit est un chiffrement de m0 ou s'il s'agit d'un chiffrement de m1avec une probabilité supérieure à la moitié plus négligeable. C'est ce qui est le scénario ou le scénario réel que nous essayons de saisir à travers cette expérience. (Référez-vous à la diapositive: 14 :33) Nous avons maintenant les deux définitions suivantes. La première définition est en fait la définition d'origine de la sécurité sémantique dans le modèle d'attaque de chiffrement uniquement, où nous voulons capturer que l'avantage de l'adversaire dans le premier monde et l'adversaire dans le second monde est délimité par une probabilité négligeable, alors que la seconde définition est la définition basée sur l'indistinction. Il s'avère que ces deux définitions sont équivalentes. À savoir si nous avons un processus de cryptage qui satisfait à la première condition, alors nous pouvons prouver que pour le même processus de cryptage dans la seconde condition aussi tenir et vice versa. En effet, si nous avons un processus de cryptage où la deuxième condition est retenue, alors pour le même processus de cryptage, la première condition est également valable. Je voudrais souligner ce qui suit. Dans l'expérience, que nous avons discutée quand je dis que la probabilité que l'adversaire identifie correctement ce qui a été crypté dans le texte de chiffrement doit être borné par la moitié plus négligeable, alors cette probabilité est sur le caractère aléatoire de l'expérience. Rappelez-vous donc que l'expérience a pu choisir le message m0 à chiffrer dans le texte de chiffrement challenge avec la probabilité la moitié et avec la probabilité la moitié de l'expérience ou le vérificateur pourrait choisir le message m1 à chiffrer dans le texte chiffré c. Cette probabilité d'identifier correctement tout ce qui a été crypté dans c devrait également être au-dessus du hasard de l'adversaire, de droite, parce que toute l'expérience va être une expérience randomisée, à droite. Donc, comme je l'ai dit, ces 2 notions de sécurité ou ces 2 définitions sont équivalentes, et la preuve que ces 2 définitions sont équivalentes est un peu compliquée et en raison de l'intérêt du temps, nous n'allons pas entrer dans les détails de la preuve. Cependant, si vous voulez avoir un aperçu de haut niveau de la preuve, vous pouvez vous référer au livre de Katz et Lindell. Fait intéressant, il s'avère que l'équivalence de ces 2 définitions tient également dans les autres modèles, de sorte que, actuellement, ce que nous envisageons actuellement est le modèle d'attaque du chiffrement uniquement et dans le modèle de chiffrement seulement, l'adversaire a accès au chiffrement de certains messages, mais si je vais au modèle d'attaque plus élevé, par un modèle d'attaque plus élevé signifie un modèle d'attaque plus puissant, par exemple le modèle d'attaque de l'ACP où à part le chiffrement, l'adversaire a aussi accès à l'oracle de chiffrement, alors nous pouvons avoir une version correspondante de la définition que nous sommes actuellement en train de donner ici pour Le modèle de l'ACO, non. À savoir, nous aimerions dire que l'avantage de l'adversaire ou la différence des probabilités absolues de calcul contradictoire de la fonction f (n) dans les 2 mondes doit être borné par une fonction négligeable, où dans le premier monde à part le texte chiffré, l'adversaire aura aussi accès à l'oracle de cryptage si nous prenons cette définition au modèle d'attaque CPAattentat. De la même façon, si nous prenons cette définition au modèle d'attaque de la CCA, à part le texte chiffré, l'adversaire dans le premier monde aura accès à l'oracle de cryptage, il aura accès à l'oracle de décryptage et ainsi de suite. Donc, nous pouvons trouver une version semi-sécurisée, nous pouvons trouver une version de la sécurité sémantique dans le modèle CPA, dans le modèle de la CCA, et ainsi de suite où l'essence de la définition sera que la différence absolue entre les deux probabilités de calcul de l'adversité f (m) dans le premier monde et f (m) dans le deuxième monde devrait être bornée par une probabilité négligeable, qui sera L'essence de la définition de sécurité sémantique dans CPAmodel, modèle CCA, etc. Il s'avère que quel que soit le modèle, nous pouvons trouver une définition basée sur l'indistinction correspondante et nous pouvons prouver que la version semi-sécurisée de la définition, la version originale de la sécurité sémantique sera équivalente à la définition basée sur l'indistinction. Donc, pour le reste du cours, nous n'allons pas voir la version originale de la définition de sécurité sémantique. Nous allons plutôt suivre la définition de sécurité basée sur l'indistinction et selon que nous sommes dans le monde CPA, le monde de la CCA, nous améliorerons l'expérience basée sur l'indistinction, à droite. (Référez-vous à la diapositive: 18 :53) Donc, c'est la définition basée sur l'indistinction dans le modèle d'attaque du texte de chiffrement seulement et il s'avère que nous pourrions trouver une autre version de cette définition, pas vrai. Ainsi, la définition d'origine exige que la probabilité que notre adversaire soit capable d'identifier correctement le message qui est crypté dans c devrait être délimité par la moitié plus négligeable, c'est-à-dire quelle est la définition initiale. La définition alternative exige que la sortie de l'adversaire soit la même indépendamment de ce qui est exactement le message qui a été crypté dans le chiffrement challenge c.Donc, souvenez-vous que puisque cette définition basée sur l'indistinction est une expérience randomisée avec la probabilité moitié, mon b pourrait être égal à zéro et avec probabilité la moitié du message qui a été chiffré et le chiffon c pourrait être m1, droite. Le but de l'adversaire est de déterminer s'il est m0 qui est crypté en c ou s'il est m1 qui a été crypté en c. Par conséquent, cette autre définition exige que la sortie de l'adversaire soit la même, qu'elle soit m0 qui est chiffrée en c ou qu'elle soit m1 qui est chiffrée dans c. Plus formellement, il importe peu que le message m1 ait été chiffré ou que le message m0ait été crypté dans c, dans les deux cas, la sortie de l'adversaire doit être pratiquement la même, sauf avec une probabilité négligeable. Cela signifie un avantage absolu de l'adversaire qui distingue s'il voit un chiffrement de m0 dans le code de chiffrement c ou s'il voit un chiffrement de m1 dans le code de chiffrement c doit être délimité par une fonction négligeable. Si c'est le cas, alors nous disons que notre processus de cryptage ne peut pas être distingué par le chiffrement dans le modèle d'attaque du texte seul, non. Donc, une autre interprétation de cette différence de ces deux probabilités est bornée par une probabilité négligeable est qu'un avantage distinctif, vous pouvez voir la différence entre ces 2 probabilités comme l'avantage distinctif de notre adversaire, non? L'essence de cette définition alternative est donc que l'avantage distinctif de notre adversaire dans cette expérience devrait être délimité par une probabilité négligeable (voir la diapositive: 21 :12) Il s'avère que ces deux versions des définitions basées sur l'indistinction sont équivalentes. À savoir, nous pouvons dire que notre processus de cryptage est indiscernellement impossible à distinguer si la probabilité avec laquelle l'adversaire peut correctement générer b est égale à b ’ est délimitée par la moitié plus une fonction négligeable. La seconde définition dit que l'avantage distinctif de l'attaquant pour distinguer s'il est en train de voir un chiffrement de m0 ou s'il voit un chiffrement de m1 doit être délimité par une probabilité négligeable.Il s'avère que ces deux conditions sont équivalentes. En effet, nous pouvons prouver que si nous avons un processus de chiffrement Π où la première condition contient et pour le même processus de chiffrement, la deuxième condition est également valable et vice versa. Donc, ce que nous allons faire, c'est que nous suivrons l'implication dans la direction que la condition 2 implique la condition 1, c'est-à-dire que nous supposerons que nous avons un processus de cryptage où la condition 2 tient, c'est-à-dire que l'avantage distinctif de l'attaquant est délimité par une probabilité négligeable.Si c'est le cas, alors nous allons montrer qu'indépendamment de la façon dont l'adversaire participe à l'expérience basée sur l'indistinction, la probabilité que l'adversaire puisse identifier correctement b est égale à b ’ ou qu'elle est égale à b ’ est bornée par la moitié plus une fonction négligeable. Alors, prouons-nous. Donc, quelle est la probabilité que dans l'expérience basée sur l'indistinction, les sorties adverses b soient égales à b ’ parce que si les sorties adverses b sont égales à b ’, c'est ce qui est l'interprétation que l'expérience produit 1.Now, si vous vous souvenez, il y a 2 versions de l'expérience. Une version équivalente de cette définition est la définition basée sur l'indistinction, où l'exigence est que si l'adversaire voit un cryptage d'un message choisi au hasard à partir d'une paire de messages où la paire de messages est connue de l'attaquant, alors la probabilité avec laquelle il peut identifier s'il s'agit d'un chiffrement de ce 0e message ou le premier message est borné par la moitié plus négligeable. Ainsi, qui peut être également déclaré comme l'avantage distinctif de l'agresseur et distinguer si le texte de chiffrement qu'il voit dans l'expérience, dans l'expérience à base non distinguable appartient à m0 ou m1, il ne peut pas se séparer sauf avec une probabilité négligeable. Nous avons également vu une illustration où nous avons montré que si votre processus de chiffrement satisfait à la définition basée sur l'indistinction, cela implique en effet que l'adversaire ne peut pas calculer les bits sous-jacents du texte en clair. Dans cette illustration, nous avons introduit une preuve de réduction, qui est essentielle à la cryptographie. J'espère que vous avez apprécié cette conférence. Je vous remercie.