💻 computer science

Post-Quantum Security of Block Cipher Constructions

Cet article établit les fondements théoriques de la sécurité post-quantique pour les chiffrements par blocs en fournissant les premières preuves de sécurité pour des constructions clés telles que FX, LRW, XEX et divers modes d'authentification, tant dans le modèle classique que dans le modèle de chiffrement idéal quantique.

Auteurs originaux : Gorjan Alagic, Chen Bai, Christian Majenz, Kaiyan Shi

Publié 2026-04-16

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Gorjan Alagic, Chen Bai, Christian Majenz, Kaiyan Shi

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🛡️ L'histoire des coffres-forts face aux super-héros quantiques

Imaginez que le monde de la cryptographie est un immense château fort. Pour protéger les trésors (vos données, vos messages, vos secrets bancaires), on utilise des coffres-forts appelés "chiffres par blocs" (comme le célèbre AES).

Pendant des décennies, nous avons cru que ces coffres étaient invincibles, à condition d'avoir une clé assez longue. Mais il y a un nouveau venu dans l'histoire : l'ordinateur quantique. C'est un super-héros capable de faire des milliards de calculs à la fois, comme s'il pouvait essayer toutes les clés d'un coffre en même temps.

La question que se posent les auteurs de ce papier est simple : Nos coffres-forts actuels résisteront-ils à cette attaque quantique ?

Jusqu'à présent, les experts savaient comment protéger les serrures des portes principales (cryptographie asymétrique), mais ils avaient un peu peur pour les coffres-forts à l'intérieur (cryptographie symétrique). Ce papier vient combler ce vide et nous donne les plans de sécurité pour le futur.

🔑 Le problème : Le "Grover" et la clé perdue

Dans le monde classique, si vous voulez ouvrir un coffre avec une clé perdue, vous devez essayer les clés une par une. C'est lent.
Avec un ordinateur quantique, le célèbre algorithme de Grover agit comme un détecteur de métaux magique : il peut trouver la bonne clé beaucoup plus vite, en divisant par deux le temps de recherche.

L'analogie du labyrinthe :

Classique : Vous marchez dans un labyrinthe sombre, essayant chaque chemin jusqu'à trouver la sortie.
Quantique : Vous avez un super-pouvoir qui vous permet de marcher sur tous les chemins en même temps. Vous trouvez la sortie beaucoup plus vite.

Pour contrer cela, la solution habituelle est de doubler la taille de la clé (rendre le labyrinthe deux fois plus grand). Mais est-ce suffisant ? Est-ce que c'est trop ? Ce papier dit : "Oui, on peut faire mieux que de deviner, on peut le prouver mathématiquement."

🧪 Les trois grandes découvertes de l'équipe

Les auteurs (Gorjan, Chen, Christian et Kaiyan) ont développé de nouvelles techniques pour prouver la sécurité de trois types de constructions cryptographiques.

1. Le "FX" : L'extension de la clé (Le coffre-fort avec deux serrures)

Parfois, une seule clé ne suffit pas. Le schéma FX prend un petit coffre et ajoute des couches de protection supplémentaires (comme ajouter une deuxième serrure et des plaques de blindage).

La découverte : Ils ont prouvé que même avec un ordinateur quantique, ce système reste très solide.
L'analogie : Imaginez que vous avez un coffre-fort. Le schéma FX ajoute une couche de ciment et une deuxième serrure. Les auteurs montrent qu'un voleur quantique ne peut pas casser ce système plus vite que prévu, même s'il a des super-pouvoirs. Ils ont même prouvé que c'est la limite maximale de sécurité possible (on ne peut pas faire mieux).

2. Les "Tweakable Ciphers" : Les coffres-forts avec étiquettes (LRW et XEX2)

Certains coffres ont besoin d'une "étiquette" (appelée tweak) en plus de la clé. Par exemple, pour chiffrer un disque dur, on veut que le même fichier chiffré à deux endroits différents donne deux résultats différents. C'est crucial pour la sécurité des disques durs (comme le standard XTS-AES).

La découverte : Ils ont prouvé que ces systèmes, très utilisés dans les ordinateurs et les disques durs, résistent bien aux attaques quantiques.
L'analogie : C'est comme si chaque coffre avait une étiquette unique. Même si le voleur quantique essaie de deviner la clé, l'étiquette change la donne à chaque fois, rendant l'attaque beaucoup plus difficile. Ils ont montré que le risque de collision (deux étiquettes qui se trompent de chemin) reste très faible.

3. Les "Modes" : La façon d'empiler les briques (CBC, GCM, etc.)

Un chiffre par bloc est comme une brique. Pour construire un mur (chiffrer un long message), on utilise des "modes" (des recettes pour empiler les briques).

La découverte : C'est la partie la plus excitante ! Ils ont montré que la plupart des recettes utilisées aujourd'hui sur Internet (pour sécuriser vos emails, vos achats en ligne) sont déjà sûres contre les ordinateurs quantiques, à condition d'utiliser une clé assez longue.
L'analogie : Imaginez que vous construisez un mur avec des briques. Les auteurs disent : "Ne changez pas la recette du mortier ! Tant que vos briques (le chiffre de base) sont solides, le mur entier résistera aux tremblements de terre quantiques." Ils ont créé une règle générale qui s'applique à presque tous les systèmes actuels.

🛠️ Comment ont-ils fait ? (La technique du "Re-échantillonnage")

Pour prouver tout cela, ils ont inventé un nouvel outil mathématique qu'ils appellent le "Re-échantillonnage" (Resampling).

L'analogie du magicien :
Imaginez un magicien (l'ordinateur quantique) qui essaie de deviner comment fonctionne un tour de magie.

Le magicien observe le tour plusieurs fois.
Soudain, le prestidigitateur (le chercheur) modifie subtilement le tour pendant que le magicien regarde, mais seulement à un endroit précis.
La question est : Le magicien s'en rend-il compte ?

Les auteurs ont prouvé que, sauf si le magicien a fait un nombre astronomique d'observations, il ne peut pas détecter ce petit changement. C'est comme essayer de trouver une aiguille dans une botte de foin en changeant subtilement la botte de foin pendant que le magicien cherche. Si la botte est assez grande, il ne verra rien.

Cette technique leur permet de "simuler" des attaques et de prouver mathématiquement que le voleur quantique échouera.

🚀 Conclusion : Que faut-il retenir ?

Ce papier est une étape majeure. Il nous dit que :

Pas de panique : La cryptographie symétrique (coffres-forts) n'est pas morte avec l'arrivée des ordinateurs quantiques.
On sait quoi faire : En augmentant légèrement la taille des clés (par exemple, passer de 128 bits à 256 bits pour AES), nos systèmes resteront sécurisés pendant des décennies.
La science avance : Nous avons maintenant des preuves rigoureuses, pas juste des suppositions.

En résumé, les auteurs ont construit un bouclier mathématique qui nous assure que nos secrets resteront secrets, même face aux super-héros quantiques de demain. C'est une excellente nouvelle pour la sécurité d'Internet, des banques et de nos données personnelles.

1. Problématique et Contexte

La sécurité des cryptosystèmes face aux ordinateurs quantiques est un enjeu majeur. Alors que la sécurité post-quantique de la cryptographie à clé publique (menacée par l'algorithme de Shor) fait l'objet d'une attention intense, celle de la cryptographie à clé symétrique, et plus particulièrement des chiffrements par blocs (comme AES), reste un domaine largement inexploré.

Bien qu'il n'existe pas encore d'attaques quantiques dramatiques contre les schémas symétriques déployés, les raisons de s'y intéresser sont multiples :

Il est possible que certains schémas actuels ne soient pas sécurisés face à un adversaire quantique.
La plupart des preuves de sécurité classiques ne se traduisent pas directement au contexte quantique.
Les bornes de sécurité fines (nécessaires pour le choix des paramètres) sont souvent absentes dans le cadre post-quantique.
L'hypothèse courante selon laquelle il suffit de doubler la longueur de la clé pour contrer l'algorithme de Grover s'avère parfois excessive ou, au contraire, insuffisante selon les constructions.

Le défi principal réside dans la modélisation de l'adversaire : dans le modèle idéal de chiffrement par blocs (ICM), l'adversaire a un accès quantique (en superposition) au chiffrement par bloc sous-jacent (oracle idéal), tandis que l'adversaire n'a qu'un accès classique aux constructions utilisant des clés secrètes. Ce modèle est appelé Q1 (ou modèle post-quantique).

2. Méthodologie et Techniques Clés

Les auteurs établissent les fondements d'une théorie de la sécurité post-quantique pour les chiffrements par blocs en utilisant deux approches principales : le modèle de chiffrement par bloc idéal quantique (QICM) et le modèle standard (plain model).

A. Lemme de Rééchantillonnage pour le Chiffrement Idéal (Ideal Cipher Resampling)

La contribution technique centrale est un nouveau lemme de rééchantillonnage adapté au modèle de chiffrement idéal quantique.

Fonctionnement : Ce lemme permet de quantifier la capacité d'un adversaire quantique à détecter des modifications locales effectuées sur un chiffrement idéal (par exemple, lors d'une simulation dans une preuve par hybridation).
Résultat : Il démontre qu'un adversaire ne peut pas détecter ces modifications (comme un échange de valeurs dans la table de permutation) à moins d'avoir effectué un nombre très élevé de requêtes quantiques avant la modification.
Différence avec l'état de l'art : Les lemmes précédents s'appliquaient aux fonctions aléatoires ou aux permutations aléatoires, mais pas aux chiffrements idéaux (qui sont des permutations indexées par une clé). Ce nouveau lemme comble cette lacune.

B. Technique d'Hybridation Adaptée

Les auteurs adaptent la technique d'hybridation (introduite par Alagic et al. pour le chiffrement Even-Mansour) au contexte des chiffrements par blocs.

L'idée est de passer progressivement d'un monde réel (où les requêtes classiques répondent via le chiffrement réel) à un monde idéal (où elles répondent via une permutation aléatoire).
Pour éviter les arguments circulaires (où l'adversaire pourrait extraire la clé pour distinguer les mondes), les auteurs modifient le chiffrement sous-jacent à chaque étape de l'hybridation et utilisent le lemme de rééchantillonnage pour prouver que ces modifications sont indétectables.

3. Contributions et Résultats Principaux

L'article fournit les premières preuves de sécurité post-quantique rigoureuses pour plusieurs constructions fondamentales :

A. Construction FX (Extension de longueur de clé)

Sujet : La construction FX transforme un chiffrement par bloc $E$ en un chiffrement avec une clé plus longue : $FX(x) = E_{k_0}(x \oplus k_1) \oplus k_2$ .
Résultat : Les auteurs prouvent la sécurité post-quantique dans le modèle QICM.
Borne de sécurité : L'avantage de distinction est borné par :
$\text{Adv} \leq 4(q_C\sqrt{q_Q} + q_Q\sqrt{q_C}) \cdot 2^{-(m+n)/2} + q_Q^2 \cdot 2^{-m}$
où $q_C$ est le nombre de requêtes classiques et $q_Q$ le nombre de requêtes quantiques.
Optimalité : Ces bornes sont serrées (tight). Elles correspondent aux attaques connues combinant Grover et BHT (Brassard-Høyer-Tapp) ou l'algorithme de Simon hors ligne (Offline-Simon).
Applications : Cela établit la sécurité post-quantique des chiffrements légers PRINCE et PRIDE, qui sont des variantes de FX.

B. Chiffrements par Blocs Réglables (Tweakable Block Ciphers)

Sujets : Les constructions LRW (Liskov-Rivest-Wagner) et XEX2 (base du mode XTS-AES pour le chiffrement de disque).
Résultat : Preuves de sécurité dans le modèle standard et le modèle QICM.
Borne : Pour LRW, la borne inclut un terme supplémentaire $6q_C^2 \cdot 2^{-n}$ correspondant à une attaque par collision classique, en plus des termes quantiques.
Signification : Cela valide la sécurité de XTS-AES (utilisé par la plupart des systèmes d'exploitation) face aux attaques quantiques, sous réserve que les clés soient suffisamment longues.

C. Modes de Chiffrement par Blocs

Théorème de Relèvement (Lifting Theorem) : Les auteurs proposent un théorème général permettant de déduire la sécurité post-quantique d'un mode de chiffrement (comme CBC, CTR, GCM, CMAC) à partir de la sécurité du chiffrement par bloc sous-jacent.
Formule :
$\text{Adv}_{\text{Mode}}^{\text{PQ}} \leq \text{Adv}_{\text{Bloc}}^{\text{SPRP-PQ}} + \delta(q)$
où $\delta(q)$ est la sécurité informationnelle classique du mode (indépendante de la puissance de calcul).
Conséquence : La plupart des modes utilisés dans les communications Internet sécurisées (GCM, CBC, etc.) conservent leur sécurité post-quantique, à condition que le chiffrement par bloc sous-jacent (ex: AES) soit sécurisé et que les paramètres soient ajustés (notamment la taille des clés et des tags).

4. Signification et Impact

Ce travail représente une avancée significative pour la cryptographie symétrique post-quantique :

Fondation Théorique : Il établit un cadre rigoureux pour analyser la sécurité des constructions symétriques face aux ordinateurs quantiques, comblant le vide laissé par la littérature précédente qui se concentrait principalement sur la cryptographie asymétrique.
Validation des Standards : Il confirme que les constructions largement utilisées (FX, LRW, XEX2, GCM) sont robustes, mais fournit les bornes exactes nécessaires pour dimensionner correctement les clés (par exemple, confirmer que doubler la clé est souvent suffisant, mais pas toujours optimal).
Nouvelles Outils : Le lemme de rééchantillonnage pour le modèle de chiffrement idéal quantique est un outil puissant qui pourra être réutilisé pour prouver la sécurité d'autres constructions futures.
Distinction des Modèles : L'article clarifie l'importance cruciale de distinguer l'accès quantique à l'oracle public (le chiffrement par bloc) de l'accès classique aux oracles construits (qui utilisent la clé secrète), évitant ainsi des modèles de sécurité irréalistes (modèle Q2).

En résumé, cette étude fournit aux ingénieurs et chercheurs les outils mathématiques nécessaires pour évaluer et garantir la sécurité des systèmes de chiffrement symétrique à l'ère quantique, en passant de l'hypothèse empirique à la preuve formelle.