Simon's Algorithm for the Even-Mansour Cipher on Quantum Hardware

Cet article présente une preuve de concept de cryptanalyse quantique du chiffreur Even-Mansour utilisant l'algorithme de Simon sur du matériel NISQ, ayant permis de récupérer avec succès des clés secrètes pour des constructions de 3 et 4 bits sur le processeur ibm_miami tout en mettant en évidence les goulots d'étranglement mémoire des outils d'optimisation de circuits actuels pour des longueurs de clés plus grandes.

L'essentiel

Imaginez que vous essayez de crocheter un coffre-fort doté d'une serrure très spécifique et astucieuse. Cet article porte sur une équipe de chercheurs qui a tenté de crocheter cette serrure en utilisant un nouveau type d'« outil surpuissant » appelé ordinateur quantique. Ils n'ont pas simplement deviné la combinaison ; ils ont utilisé une astuce mathématique ingénieuse pour découvrir le motif caché à l'intérieur de la serrure.

Voici la décomposition de leur expérience en termes simples :

La Serrure : Le Chiffrement Even-Mansour

Considérez le chiffrement Even-Mansour comme un coffre-fort simple mais robuste. Voici comment il fonctionne :

1. Vous introduisez un message (le texte clair) dans le coffre-fort.
2. Vous le mélangez avec une clé secrète (Clé 1).
3. Vous le faites passer dans une machine publique et chaotique (une permutation) qui le brouille.
4. Vous le mélangez à nouveau avec une deuxième clé secrète (Clé 2).
5. Le résultat est le message verrouillé.

L'objectif des attaquants (les chercheurs) était de déterminer quelles étaient ces deux clés secrètes.

L'Outil Surpuissant : L'Algorithme de Simon

Normalement, si vous vouliez trouver une clé secrète, vous pourriez devoir essayer des milliards de combinaisons une par une. C'est comme essayer chaque clé d'un énorme trousseau jusqu'à ce que l'une d'elles convienne.

Mais les chercheurs ont utilisé l'Algorithme de Simon. Imaginez cet algorithme comme un détective magique qui ne cherche pas la clé directement. Au lieu de cela, il cherche un rythme caché ou un motif.

• Les chercheurs ont mis en place un scénario spécial où la serrure se comporte de manière étrange : si vous tournez le cadran d'une certaine quantité (la clé secrète), la serrure se retrouve exactement dans la même position que si vous ne l'aviez pas tournée du tout.
• L'Algorithme de Simon est excellent pour trouver ces « rythmes cachés » (périodes) beaucoup plus rapidement qu'un ordinateur classique. C'est comme écouter une chanson et connaître instantanément le rythme, alors qu'un ordinateur classique doit compter chaque coup de caisse claire.

L'Expérience : Construire la Serrure sur un Ordinateur Quantique

Les chercheurs voulaient voir si ce détective magique pouvait réellement fonctionner sur du matériel physique réel. Ils ont construit une version miniature de la serrure sur un ordinateur quantique appelé IBM Miami.

1. Le Plan (Boîtes S) : Pour faire fonctionner la serrure, ils avaient besoin d'un « brouilleur » (appelé une boîte S). Ils ont construit ces brouilleurs en utilisant une logique similaire à celle employée dans le célèbre standard de chiffrement AES, mais beaucoup plus petite (pour des clés de 3 bits et 4 bits).
2. Le Problème de Traduction : Les ordinateurs quantiques parlent une langue différente de celle des ordinateurs classiques. Les chercheurs ont dû traduire leurs conceptions classiques de « brouilleurs » dans une langue que l'ordinateur quantique pouvait comprendre. Ils ont utilisé un outil appelé DORCIS pour effectuer cette traduction.
   • Le Goulot d'Étranglement : Cet outil fonctionnait très bien pour les petites serrures de 3 bits et 4 bits. Cependant, lorsqu'ils ont essayé de traduire une serrure légèrement plus grande de 5 bits, l'outil a manqué de mémoire. C'était comme essayer de plier une carte massive dans une toute petite poche ; le papier ne rentrait tout simplement pas. Cela les a empêchés de tester des clés plus grandes.
3. Le Bruit : Les ordinateurs quantiques sont actuellement très sensibles, comme une maison de cartes dans une tempête de vent. Pour maintenir l'expérience stable, les chercheurs ont utilisé des techniques spéciales (comme le « découplage dynamique ») pour calmer les qubits, de la même manière que vous pourriez tenir un appareil photo stable pour prendre une photo nette dans le vent.

Les Résultats

Ils ont lancé l'expérience sur deux petites serrures : l'une avec une clé de 3 bits et l'autre avec une clé de 4 bits.

• Succès : Dans les deux cas, l'ordinateur quantique a trouvé avec succès le rythme caché. À partir de ce rythme, les chercheurs ont calculé les clés secrètes.
• Reproductibilité : Ils ont exécuté le test cinq fois pour chaque taille de serrure, et cela a fonctionné à chaque fois.
• La Limitation : Comme mentionné, ils n'ont pas pu tester une serrure de 5 bits car l'outil de traduction (DORCIS) a planté en raison des limites de mémoire.

La Conclusion

L'article conclut deux points principaux :

1. Cela Fonctionne (pour l'instant) : L'Algorithme de Simon est une méthode réelle et fonctionnelle pour casser ce type spécifique de chiffrement sur le matériel quantique actuel, mais uniquement pour des clés très petites. Cela prouve que les ordinateurs quantiques peuvent théoriquement trouver ces motifs cachés de manière exponentiellement plus rapide que les ordinateurs classiques.
2. Les Outils Ont Besoin d'une Mise à Niveau : Bien que l'ordinateur quantique ait fait son travail, le logiciel utilisé pour préparer les « plans » de l'ordinateur quantique a atteint un mur. Pour casser des serrures plus grandes et plus réalistes à l'avenir, nous avons besoin d'outils meilleurs pour traduire ces conceptions en circuits quantiques sans manquer de mémoire.

En bref : Ils ont prouvé que le concept fonctionne à petite échelle, mais que l'« équipe de construction » (les outils logiciels) doit devenir plus forte avant de pouvoir construire les grands gratte-ciels.

Résumé technique

1. Énoncé du problème

L'article aborde la faisabilité pratique de l'exécution d'attaques de cryptanalyse quantique sur des chiffrements symétriques en utilisant le matériel quantique actuel à échelle intermédiaire bruyant (NISQ). Plus précisément, il cible le chiffrement Even-Mansour (EM), une construction de chiffrement par bloc minimaliste basée sur une permutation publique et deux clés secrètes.

Bien que le cadre théorique pour casser le chiffrement EM en utilisant l'algorithme de Simon soit bien établi (offrant une accélération exponentielle par rapport aux attaques classiques en trouvant une période cachée), sa mise en œuvre pratique a été limitée. Les défis principaux incluent :

• Contraintes matérielles : Les dispositifs NISQ souffrent de bruit, de décohérence et d'une connectivité limitée des qubits, rendant l'exécution de circuits profonds (nécessaires pour des permutations complexes) difficile.
• Goulots d'étranglement de la synthèse de circuits : La conversion de permutations cryptographiques classiques (boîtes S) en circuits quantiques réversibles optimisés est coûteuse en calcul. Les outils existants échouent souvent à passer à l'échelle pour des longueurs de clés plus grandes en raison de contraintes de mémoire.
• Implémentation de l'oracle : L'attaque nécessite d'implémenter la fonction de chiffrement comme un oracle quantique, ce qui implique de synthétiser des permutations non linéaires en portes quantiques.

2. Méthodologie

Les auteurs ont mis en œuvre une attaque de concept sur le processeur IBM ibm_miami. La méthodologie comprenait trois étapes principales :

A. Construction cryptographique

• Chiffrement : Le schéma Even-Mansour $EM_{k_1, k_2}(x) = P(x \oplus k_1) \oplus k_2$, où $P$ est une permutation publique et $k_1, k_2$ sont des clés secrètes.
• Permutation ($P$) : Pour $N=3$ et $N=4$, les auteurs ont construit des applications bijectives inspirées de la boîte S de l'AES. Celles-ci étaient définies comme une inversion dans le corps fini $F_{2^N}$ suivie d'une transformation affine.
• Vecteur d'attaque : L'attaque définit une fonction $f(x) = EM(x) \oplus P(x)$. Cette fonction possède une période cachée $k_1$. L'algorithme de Simon est utilisé pour trouver $k_1$, après quoi $k_2$ est récupéré classiquement ou via une requête quantique simple.

B. Synthèse de circuits quantiques (DORCIS)

• Chaîne d'outils : Les auteurs ont utilisé l'outil DORCIS (Depth Optimized Quantum Implementation of Substitution Boxes) pour synthétiser les tables de permutations classiques en circuits quantiques réversibles.
• Optimisation : DORCIS décompose les permutations en portes élémentaires (Pauli-X, Toffoli/CCNOT, SWAP) et minimise la profondeur du circuit.
• Limite de mise à l'échelle : L'outil a généré avec succès des circuits pour $N=3$ et $N=4$, mais a échoué pour $N=5$ en raison d'un goulot d'étranglement de mémoire sur un CPU haute performance (3,9 TiB de RAM), empêchant la génération de circuits pour des instances plus grandes.

C. Exécution matérielle et atténuation des erreurs

Pour exécuter l'attaque sur le processeur bruyant ibm_miami, l'équipe a employé des stratégies d'atténuation spécifiques :

• Mappage des qubits : Ils ont mappé manuellement les qubits logiques sur des sous-graphes de qubits physiques spécifiques ($[0, 1, 2, 12, 11, 10]$ pour $N=3$ et $[0, 1, 2, 3, 13, 12, 11, 10]$ pour $N=4$) pour exploiter la topologie du réseau et éviter les frais de routage automatique.
• Découplage dynamique (DD) : Des séquences symétriques d'unitaires (par exemple, des impulsions X alternées) ont été appliquées sur les qubits inactifs pour supprimer le bruit environnemental basse fréquence et les interférences croisées.
• Tournage de Pauli : Des paires d'opérateurs de Pauli logiquement équivalents ont été insérées aléatoirement avant et après les portes pour convertir les erreurs cohérentes en erreurs de Pauli stochastiques, empêchant les distorsions de phase systématiques qui pourraient masquer les collisions structurelles de l'algorithme.

3. Contributions clés

1. Première démonstration pratique : Il s'agit d'une preuve de concept réussie démontrant la récupération de clé secrète pour le chiffrement Even-Mansour sur du matériel quantique réel ($N=3$ et $N=4$).
2. Validation de l'atténuation des erreurs : L'article valide que la combinaison du découplage dynamique et du tournage de Pauli permet à l'algorithme de Simon de fonctionner efficacement malgré les profondeurs de circuits élevées et le bruit inhérent aux dispositifs NISQ.
3. Identification des goulots d'étranglement classiques : L'étude met en évidence que le facteur limitant pour la mise à l'échelle de ces attaques est actuellement le prétraitement classique (synthèse de circuits) plutôt que le matériel quantique lui-même. L'outil DORCIS a échoué à $N=5$ en raison de contraintes de mémoire.
4. Données empiriques : Les auteurs fournissent des distributions statistiques détaillées des résultats de mesure, montrant que les résultats expérimentaux s'alignent sur les prédictions théoriques lorsque le bruit est pris en compte.

4. Résultats

• Cas 3 bits ($N=3$) :
  • Récupération réussie de la clé secrète $k_1 = (0, 1, 0)$ et $k_2 = (1, 1, 0)$.
  • La profondeur du circuit était de 23 (T-depth 3).
  • Après 5 expériences indépendantes (105 tirs chacune), la distribution de mesure présentait un pic clair aux vecteurs orthogonaux à la vraie période, permettant une récupération réussie de la clé par algèbre linéaire.
• Cas 4 bits ($N=4$) :
  • Récupération réussie de $k_1 = (0, 1, 0, 1)$ et $k_2 = (1, 1, 0, 1)$.
  • La profondeur du circuit est passée à 54 (T-depth 7).
  • Malgré l'augmentation de la profondeur et du bruit, la distribution des résultats restait suffisamment distincte pour résoudre le système d'équations linéaires pour la clé.
• Analyse des erreurs :
  • Les auteurs ont modélisé le bruit comme un canal dépolarisant. Ils ont estimé un paramètre de bruit $p \approx 0,434$ basé sur les taux d'erreur des portes et le nombre total d'impulsions.
  • Les données expérimentales correspondaient à la distribution théorique bruitée, confirmant que les écarts étaient dus au bruit matériel plutôt qu'à un échec algorithmique.
• Échec de la mise à l'échelle : L'outil DORCIS n'a pas pu générer un circuit pour $N=5$, indiquant que les outils de synthèse classiques actuels ne sont pas encore évolutifs pour des longueurs de clés plus grandes.

5. Importance

• Validation théorique : Les résultats confirment que l'accélération exponentielle théorique de l'algorithme de Simon est réalisable en pratique pour les chiffrements symétriques, à condition que la longueur de la clé soit suffisamment petite pour le matériel actuel.
• Implications pour la sécurité : Cela renforce la vulnérabilité des constructions symétriques comme Even-Mansour (et par extension, l'AES sur 1 tour) aux attaques quantiques si un oracle de chiffrement est accessible en superposition.
• Goulot d'étranglement matériel vs logiciel : L'article déplace le focus du défi de « pouvons-nous exécuter l'algorithme quantique ? » vers « pouvons-nous synthétiser le circuit ? ». Il suggère que les progrès futurs en cryptanalyse quantique dépendent fortement du développement d'outils de synthèse classiques plus évolutifs (potentiellement utilisant l'apprentissage automatique ou des heuristiques) plutôt que de simplement attendre de meilleurs qubits.
• Viabilité NISQ : Il démontre qu'avec une atténuation sophistiquée des erreurs et un mappage manuel des qubits, des algorithmes cryptanalytiques complexes peuvent produire des résultats corrects sur du matériel actuel et bruyant.