Sécurité sémantique

La sécurité sémantique est une notion de sécurité importante dans le cadre des preuves de sécurité des protocoles cryptographiques. Cette notion a été introduite en 1984 par Shafi Goldwasser et Silvio Micali^[1].

Elle est définie indépendamment du type de cryptographie du système (c’est-à-dire symétrique ou asymétrique), mais est principalement utilisée dans les preuves des schémas à clef publique.

La sécurité sémantique traduit formellement le fait qu’il doit être difficile de retrouver de l’information sur le message originel en ayant accès au chiffrement de ce message et aux informations publiques du protocole.

Pour atteindre la sécurité sémantique, n’importe quel adversaire ne peut dériver d'information sur un message chiffré sans connaître la clef privée. Cela se traduit par la notion d’indistinguabilité, c’est-à-dire par l’incapacité, étant donné deux messages et un chiffré d’un des deux messages, à différencier lequel des deux messages a été chiffré. En effet, si un adversaire était capable de répondre à cette question, alors il obtiendrait au moins un bit d’information sur le texte chiffré.

Dans le cas d’un cryptosystème de cryptographie asymétrique, il faut qu’un adversaire possédant une puissance de calcul limitée soit incapable d'obtenir des informations significatives sur le message en clair à partir du texte chiffré et de la clé publique.

De manière plus formelle, on considère un attaquant ${\displaystyle {\mathcal {A}}}$ et un challenger ${\displaystyle {\mathcal {C}}}$ qui suivent le jeu suivant^[2] :

${\displaystyle {\begin{array}{ccc}{\mathcal {C}}&&{\mathcal {A}}\\\hline (pk,sk)\gets {\mathsf {GenClefs}}(1^{\lambda })&pk\\&\longrightarrow \\\\b\hookleftarrow {\mathcal {U}}(\{0,1\})&m_{0},m_{1}&{\text{Choisit }}(m_{0},m_{1})\\&\longleftarrow \\\\c={\mathsf {Chiffrer}}(m_{b})&c\\&\longrightarrow \\&&{\text{Renvoie }}b'\in \{0,1\}\end{array}}}$

On définit l’avantage de ${\displaystyle {\mathcal {A}}}$ comme étant la quantité: ${\displaystyle {\text{Advt}}_{\text{CPA}}^{\mathcal {A}}:=\left|\Pr _{\mathcal {A}}\left[b'=1\mid b=1\right]-\Pr _{\mathcal {A}}\left[b'=1\mid b=0\right]\right|}$.

Un schéma de chiffrement (GenClefs, Chiffrer, Déchiffrer) est sémantiquement sûr s'il n'existe pas d'algorithme probabiliste tournant en temps polynomial ${\displaystyle {\mathcal {A}}}$ qui puisse gagner à ce jeu avec un avantage non négligeable, c'est-à-dire plus grand que ${\displaystyle 2^{-\lambda }}$ pour λ bits de sécurité.

Une autre façon de décrire cette propriété consiste à dire que le schéma de chiffrement (GenClefs, Chiffrer, Déchiffrer) est sémantiquement sûr s'il n'existe pas d'algorithme probabiliste tournant en temps polynomial ${\displaystyle {\mathcal {A}}}$ qui gagne plus souvent qu'un adversaire qui se contenterait de répondre au hasard. Cela revient à demander que l'avantage

${\displaystyle {\text{Advt}}_{\text{CPA}}^{\mathcal {A}}=\left|\Pr _{\mathcal {A}}\left[b'=b\right]-{\frac {1}{2}}\right|}$

soit négligeable.

La sécurité sémantique ne considère que le cas d'un adversaire « passif » qui observe des textes chiffrés. L'attaquant ne peut demander que certains textes soient déchiffrés (ce scénario correspond à ce qu’on appelle une attaque à texte chiffré choisi). Plusieurs cryptosystèmes considérés comme sûrs du point de vue sémantique ne le sont plus dans le cas d’un attaquant pouvant déchiffrer certains messages. Le critère sémantique est désormais considéré comme insuffisant puisqu’il est possible de monter une attaque active dans le monde réel, comme l’a montré Daniel Bleichenbacher (en) en 1998^[3].

• [Bleichenbacher 1998] (en) Daniel Bleichenbacher, « Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 », Advances in Cryptology, Berlin, Springer, lecture Notes in Computer Science, vol. 1462 « CRYPTO '98, 18th Annual International Cryptology Conference Santa Barbara, California, USA August 23–27, 1998 Proceedings »,‎ 1998 (ISBN 978-3-540-64892-5, ISSN 0302-9743, DOI 10.1007/BFb0055716, lire en ligne [PDF]).
• [Goldwasser et Micali 1984] (en) Shafi Goldwasser et Silvio Micali, « Probabilistic Encryption », Journal of Computer and System Science, Elsevier,‎ 1984 (DOI 10.1016/0022-0000(84)90070-9).
• [Katz et Lindell 2007] (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography: Principles and Protocols, Chapman and Hall/CRC, 2007 (lire en ligne).

• Preuve de sécurité

• Portail de la cryptologie