Perfect secrecy, one-time pad et théorème de Shannon

Cryptographie · Confidentialité informationnelle

En cryptographie, on veut chiffrer un message pour qu’un adversaire qui intercepte le ciphertext ne puisse rien apprendre sur le plaintext. Il existe une notion extrême (et très élégante) qui formalise exactement cette idée : la confidentialité parfaite (perfect secrecy).

1) Schéma de chiffrement (Gen, Enc, Dec)

Un schéma de chiffrement symétrique se décrit par trois algorithmes : Gen (génération de clé), Enc (chiffrement), Dec (déchiffrement), ainsi qu’un espace de messages M avec |M| > 1.

• Gen est probabiliste et produit une clé k selon une distribution (fixée par le schéma).
• Enc prend k et un message m et produit un ciphertext c, noté c := Enc_k(m).
• Dec est correcte si Dec_k(c) = m lorsque c = Enc_k(m).

Point important : la distribution sur K (l’espace des clés) est fixée par le schéma, tandis que la distribution sur M dépend des utilisateurs (les messages “réels” envoyés).

2) Définition : perfect secrecy

Intuition : après avoir vu le ciphertext, l’adversaire ne doit pas pouvoir mettre à jour ses croyances sur le message. Formellement, le schéma est parfaitement secret si, pour toute distribution sur M, pour tout m et tout c avec Pr[C=c] > 0 :

Pr[M=m | C=c] = Pr[M=m]

On peut reformuler cette condition de plusieurs façons équivalentes (très utiles en preuve) :

• Pr[C=c | M=m] = Pr[C=c] : le ciphertext est indépendant du message.
• Pr[C=c | M=m0] = Pr[C=c | M=m1] : deux messages quelconques induisent la même distribution de ciphertexts.

3) Une définition “par jeu” (adversaire eavesdropper)

On peut aussi définir la perfect secrecy via une expérience : l’adversaire choisit deux messages m0 et m1, un challenger choisit un bit secret b, chiffre mb et donne le ciphertext à l’adversaire, qui doit deviner b.

Si le schéma est parfaitement secret, alors l’adversaire ne fait pas mieux qu’un pile-ou-face :

Pr[PrivK^eav = 1] = 1/2

4) Le one-time pad (OTP)

Le one-time pad est le cas “parfait” classique :

• M = K = C = {0,1}^ℓ
• Gen choisit k uniformément dans {0,1}^ℓ
• Enc_k(m) = k ⊕ m
• Dec_k(c) = k ⊕ c

Pourquoi c’est parfaitement secret ? Parce que pour tout couple (m, c), il existe exactement une clé k = c ⊕ m qui relie les deux. Comme la clé est uniforme, chaque ciphertext est aussi “uniforme”, indépendamment du message.

5) Les limites : la clé doit être au moins aussi grande que le message

La confidentialité parfaite a un prix : si un schéma est parfaitement secret sur M et que K est l’espace des clés, alors on doit avoir :

|K| ≥ |M|

En clair : pour chiffrer parfaitement, il faut autant de “possibilités de clé” que de “possibilités de message”. C’est précisément pourquoi l’OTP impose une clé aussi longue que le message — et pourquoi il est difficile à utiliser à grande échelle.

6) Théorème de Shannon (caractérisation)

Dans le cas où |M| = |K| = |C|, Shannon donne une caractérisation très nette : un schéma est parfaitement secret si et seulement si :

1. Les clés sont choisies uniformément : Pr[K=k] = 1/|K|.
2. Pour tout m et tout c, il existe une unique clé k telle que Enc_k(m)=c.

Cette condition “unique clé” signifie que, pour un message fixé, la fonction k ↦ Enc_k(m) agit comme une permutation de l’espace des ciphertexts. L’OTP est exactement de cette nature (via le XOR).

Conclusion. La perfect secrecy capture une notion idéale : le ciphertext ne révèle strictement rien. Le one-time pad l’atteint, et Shannon explique pourquoi : il faut une clé uniformément aléatoire et “aussi grande” que le message. C’est magnifique… et contraignant.