Sécurité sémantique

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és.

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].