💻 computer science

Quantum Cryptanalysis on IBM Quantum Hardware: Extending Even--Mansour Period Recovery from $N=4$ to $N=10$

Cet article présente une démonstration authentique, non compilée, sur du matériel quantique réel d'IBM, d'une cryptanalyse quantique conforme aux modèles théoriques utilisant l'algorithme de Simon pour récupérer des périodes cachées pour des structures de chiffrement de type Even-Mansour et Feistel jusqu'à des tailles records (N=10), tout en fournissant une évaluation comparative complète de cinq attaques à travers quatre paradigmes de chiffrement symétrique avec des réserves explicites concernant leur portée, leur dépendance à l'atténuation des erreurs et l'absence de menace pour le chiffrement moderne à grande échelle.

Auteurs originaux : Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

Publié 2026-07-22

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

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

Imaginez un monde où les codes secrets ne sont pas seulement enfermés dans un coffre-fort, mais cachés à l'intérieur d'un labyrinthe que seul un fantôme peut traverser. C'est le domaine de la cryptanalyse quantique, une branche de la science où les chercheurs utilisent les règles étranges et mystérieuses de la physique quantique pour tester la solidité de nos verrous numériques. Pour comprendre cela, vous devez connaître trois choses simples. Premièrement, les « chiffrements symétriques » sont comme une clé unique qui verrouille et déverrouille un coffre au trésor ; si vous avez la clé, vous pouvez l'ouvrir, mais si vous ne l'avez pas, vous êtes bloqué. Deuxièmement, les « ordinateurs quantiques » sont des machines spéciales qui peuvent essayer de nombreux chemins dans un labyrinthe en même temps, contrairement aux ordinateurs normaux qui doivent essayer un chemin, puis un autre, puis un autre. Enfin, il existe une astuce célèbre appelée « l'algorithme de Simon », qui est comme un détective super intelligent capable de trouver un motif caché dans un désordre chaotique beaucoup plus rapidement qu'un détective ordinaire, mais seulement si le désordre possède une structure répétitive très spécifique.

Pourquoi est-ce important ? Parce que si un ordinateur quantique peut trouver ces motifs facilement, les clés secrètes protégeant nos comptes bancaires, nos messages et nos secrets nationaux pourraient être cassées. Mais voici le hic : construire un ordinateur quantique assez grand et assez silencieux pour réellement faire cela est incroyablement difficile. Ils sont actuellement très bruyants, comme si l'on essayait d'entendre un murmure lors d'un concert de rock. Ce document traite d'une équipe de chercheurs qui ont tenté d'enseigner à un véritable ordinateur quantique bruyant comment trouver ces motifs cachés dans des codes secrets, repoussant les limites de ce qui est actuellement possible dans le monde réel.

L'article : Un détective quantique sur une scène bruyante

Les chercheurs, travaillant avec un véritable ordinateur quantique fabriqué par IBM (plus précisément la puce « ibm_kingston »), ont décidé de jouer à un jeu de « trouver le motif caché ». Ils se sont concentrés sur un type spécifique de structure de code secret appelé le chiffrement Even-Mansour. Imaginez ce chiffrement comme une machine qui prend un nombre secret (la clé) et brouille un message. Le but de l'attaque est de trouver la « période » — un rythme répétitif caché dans la façon dont la machine brouille les données. Si vous trouvez le rythme, vous pouvez découvrir la clé secrète.

Par le passé, les scientifiques n'avaient réussi à faire cela sur du matériel réel que pour des versions très petites et simples du code (où le nombre secret ne faisait que 4 bits de long). Cette équipe voulait voir jusqu'où elle pouvait pousser la machine réelle. Ils ont réussi à trouver le rythme caché pour une version où le nombre secret faisait 10 bits de long. Cela ne vous semblera peut-être pas énorme, mais dans le monde du matériel quantique, passer de 4 à 10 est un bond massif. C'est comme passer de l'équilibre sur un pied à la course d'un marathon sur une corde raide.

Ils ne se sont pas arrêtés là. Ils ont également testé leurs talents de détective sur d'autres types de structures de code :

Le Feistel à 3 tours : Une structure utilisée dans les anciens codes (comme le célèbre DES). Ils ont réussi à trouver le rythme caché pour des tailles de blocs de 6 et 8.
Bernstein-Vazirani : Un puzzle linéaire plus simple. Ils ont trouvé un secret de 16 bits en une seule question (requête), ce qui est exactement ce que les mathématiques promettaient.
Recherche de Grover : Ils ont testé une méthode de recherche de clés non structurées, montrant que l'ordinateur quantique pouvait trouver une clé en environ 13 étapes, alors qu'un ordinateur normal en aurait besoin de 256.

Le test de réalité : À quel point était-ce efficace ?

C'est la partie la plus importante de l'histoire, et celle où les auteurs sont très, très honnêtes. Bien qu'ils aient trouvé les motifs, ils n'ont pas cassé le code d'une manière qui leur permettrait de voler votre compte bancaire aujourd'hui.

Pour les puzzles plus grands (où le secret faisait 6 bits ou plus), l'ordinateur quantique est devenu un peu « bruyant » et confus. Il n'a pas indiqué la seule bonne réponse immédiatement. Au lieu de cela, il a donné une liste des meilleurs candidats. Les chercheurs ont ensuite utilisé un ordinateur classique pour vérifier les 16, 32, 64 ou 128 meilleurs candidats de la liste quantique. La véritable clé secrète se trouvait généralement très haut dans cette liste (souvent parmi les 63 premiers candidats), ce qui est bien mieux que de deviner au hasard.

Les auteurs sont très clairs : ce n'est pas encore un « avantage quantique ».

Pas de solution miracle : Ils n'ont pas cassé les versions réelles et complètes de codes célèbres comme l'AES ou le RSA. Ils n'ont cassé que des versions simplifiées et réduites de ces structures.
Pas de super-vitesse : Pour les puzzles plus grands, l'ordinateur quantique n'a pas résolu tout le problème seul. Il a réduit la liste des suspects, mais un ordinateur classique a dû effectuer le travail final. L'accélération observée concernait le nombre de questions posées, et non le temps total nécessaire pour casser le code.
Bruit vs Perfection : Ils ont utilisé l'« atténuation d'erreurs » (une façon élégante de dire qu'ils ont nettoyé les données bruitées) plutôt que la « correction d'erreurs » (qui corrigerait les erreurs parfaitement). Cela signifie que leurs résultats sont impressionnants pour la technologie actuelle, mais qu'ils ne constituent pas la solution finale et parfaite.

La vue d'ensemble

L'équipe a également lancé une simulation massive sur un supercalculateur pour voir jusqu'où cela pourrait aller si l'on disposait de machines parfaites et sans bruit. Ils ont découvert que, bien qu'un ordinateur quantique puisse théoriquement gérer ces puzzles facilement, un ordinateur normal manquerait de mémoire en essayant de simuler un ordinateur quantique de seulement 25 qubits (les unités de base de l'information quantique). Un puzzle légèrement plus grand nécessiterait 4,5 pétaoctets de mémoire — plus que ce que la plupart des centres de données possèdent !

Alors, quel est le point essentiel ? Cet article est un « record du monde » pour la taille de la structure de code secret qu'un véritable ordinateur quantique bruyant a réussi à analyser. Il prouve que les mathématiques fonctionnent sur du matériel réel, même si le matériel est encore un peu instable. C'est une preuve de concept qui dit : « Nous pouvons le faire, mais nous avons besoin de machines meilleures et plus silencieuses avant de pouvoir réellement briser les secrets du monde réel. » Les auteurs ont rendu leur code et leurs données publics afin que quiconque puisse vérifier leur travail, garantissant qu'il ne s'agit pas seulement d'une affirmation, mais d'une étape reproductible dans la course entre les ordinateurs quantiques et les codes secrets.

Résumé technique : Cryptanalyse quantique sur le matériel IBM Quantum

Énoncé du problème

La recherche théorique a longtemps établi que des structures de chiffres symétriques spécifiques, telles que le chiffrement d'Even–Mansour et les réseaux de Feistel à 3 tours, peuvent être réduites à des problèmes de période cachée solubles par l'algorithme de Simon. Cependant, un fossé important subsiste entre ces réductions théoriques et leur exécution pratique sur des dispositifs quantiques de taille intermédiaire bruyante (NISQ). Avant ce travail, les démonstrations de récupération de clés sur matériel réel étaient limitées à de très petits paramètres de sécurité (spécifiquement $N=4$ ) en raison du bruit des dispositifs et de l'absence de correction d'erreurs tolérante aux fautes. Le défi consiste à étendre ces attaques à des tailles de structures plus grandes ( $N > 4$ ) sur du matériel réel tout en maintenant une intégrité algorithmique « authentique » — ce qui signifie que les circuits doivent implémenter les applications clés réelles sans recours à des raccourcis de transpilation qui rendraient la recherche triviale.

Méthodologie

Les auteurs ont exécuté une cryptanalyse quantique « authentique, non compilée et fidèle au modèle théorique » sur le processeur IBM ibm_kingston (génération Heron) en utilisant le framework Qiskit. La méthodologie se caractérise par les composants suivants :

Portée algorithmique : L'étude cible quatre paradigmes de conception de chiffres symétriques :
1. Structure linéaire : Algorithme de Bernstein–Vazirani (requête unique).
2. Recherche non structurée : Algorithme de Grover appliqué à une recherche de clé SPN (Réseau de Substitution-Permutation) réduite.
3. Problèmes de période cachée : Algorithme de Simon appliqué à :
  - Le chiffrement d'Even–Mansour.
  - Une forge de CBC-MAC.
  - Une construction de Feistel à 3 tours (famille DES).
Stratégie d'exécution :
- Matériel réel : Les expériences ont utilisé une pile complète d'atténuation des erreurs de lecture (incluant le calibrage, le découplage dynamique et le twirling) plutôt qu'une correction d'erreurs tolérante aux fautes.
- Approche hybride pour $N > 5$ : Pour les instances d'Even–Mansour où le bruit empêchait une récupération propre de « rang 1 », les auteurs ont employé une méthode hybride de resserrement quantique + vérification classique. Le circuit quantique générait une liste restreinte de candidats de haut rang (par exemple, les 16 ou 128 premiers), qui étaient ensuite vérifiés classiquement.
- Validation : Tous les résultats matériels ont été validés par des contre-vérifications avec des clés de contrôle indépendantes pour s'assurer que les périodes récupérées n'étaient pas des artefacts liés à des sélections de clés spécifiques.
- Simulation : Un benchmark en largeur (breadth-first) a été réalisé à l'aide d'une simulation d'état vectoriel authentique (sur du matériel NVIDIA B200) jusqu'au plafond de la mémoire classique de 25 qubits pour valider les circuits non compilés.

Résultats clés

1. Extension de la frontière du matériel réel

L'article rapporte la récupération de la période cachée d'Even–Mansour jusqu'à un paramètre de sécurité $N = 10$ sur du matériel réel.

$N = 5$ : Récupération de rang 1 propre (Simon différentiel) où la véritable clé était le premier candidat.
$N = 6$ à $N = 10$ : Obtenue via l'approche hybride. Bien que la véritable clé ne soit pas toujours le premier résultat en raison du bruit, son rang suivait la limite de l'anniversaire (birthday bound) ( $2^{n/2}$ ), restant de plusieurs ordres de grandeur en dessous de l'attente aléatoire ( $2^{n-1}$ ).
Comparaison : Cela dépasse la plus grande taille précédemment rapportée sur matériel réel, soit $N = 4$ .

2. Récupération de structures Feistel et linéaires

Feistel à 3 tours : A récupéré proprement la période pour des tailles de blocs de 6 et 8 (rang 1, exact) sur matériel réel. Une instance de bloc-10 à 21 qubits a été vérifiée en simulation et soumise au matériel.
Bernstein–Vazirani : A extrait avec succès un secret linéaire de 16 bits en une seule requête sur matériel réel.

3. Séparation de la complexité

L'étude démontre la séparation théorique de la complexité de requête :

Attaques basées sur Simon : Complexité de requête classique exponentielle ( $2^{n/2}$ ) contre requêtes quantiques polynomiales ( $\Theta(n)$ ).
Attaques basées sur Grover : Accélération quadratique (par exemple, récupérer une clé de 8 bits en environ 13 itérations contre 256 évaluations classiques).

Signification et affirmations

Les auteurs cadrent explicitement leurs contributions en mettant l'accent sur l'honnêteté et la reproductibilité, évitant toute exagération de l'« avantage quantique ».

Démonstration sur matériel réel : La principale contribution est la démonstration d'une véritable cryptanalyse quantique sur du matériel réel à des tailles de structures records ( $N=10$ pour Even–Mansour), comblant le fossé entre les réductions théoriques et l'exécution physique.
Étendue de la couverture : Le travail fournit un benchmark complet à travers quatre paradigmes cryptographiques distincts (Linéaire, Non structuré, Période cachée) et cinq attaques spécifiques, le tout validé jusqu'au plafond de la simulation classique.
Absence d'avantage quantique de bout en bout : L'article stipule explicitement que ces attaques ne constituent pas un avantage quantique par rapport aux méthodes classiques en termes de coût de bout en bout. Les attaques suivent asymptotiquement la limite de l'anniversaire, ce qui signifie que la recherche de collisions classique atteint une mise à l'échelle comparable. La séparation concerne strictement la complexité de requête pour le discriminateur, et non le coût computationnel total.
Limites de portée :
- Les attaques ciblent des constructions réduites ou structurées (Even–Mansour, Feistel à 3 tours, SPN réduit), et non l'AES complet, le RSA ou le DES à 16 tours.
- Les résultats reposent sur l'atténuation d'erreurs, et non sur la correction d'erreurs tolérante aux fautes.
- Le modèle d'oracle Q2 (requête quantique) est supposé, bien que les auteurs reconnaissent ses limites pratiques et notent que les réductions offline-Simon peuvent assouplir certaines hypothèses vers le modèle Q1.

En résumé, ce document constitue un benchmark rigoureux et reproductible d'algorithmes quantiques authentiques sur du matériel NISQ, démontant que, bien que les dispositifs actuels ne puissent pas briser les chiffrements modernes à pleine échelle, ils peuvent exécuter avec succès des réductions cryptanalytiques complexes sur des primitives structurées à des tailles auparavant inaccessibles sur du matériel réel.