💻 computer science

Quantum Key Search Algorithms under Side-channel Attack

Cet article propose un algorithme de recherche de clé quantique amélioré qui exploite les distributions d'erreurs induites par les attaques par canaux auxiliaires pour obtenir une accélération super-quadratique par rapport aux méthodes classiques et surpasse les approches quantiques existantes comme celle de Glaser, tout en abordant les défis de préparation des états d'entrée grâce à une implémentation efficace des états de Dicke.

Auteurs originaux : Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

Publié 2026-08-12

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

Article original sous licence CC BY 4.0 (https://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 que vous essayez de craquer le code d'un cadenas sur un coffre-fort géant et ultra-technologique. Dans le monde de la sécurité numérique, ce « cadenas » est une clé cryptographique — une longue chaîne de 0 et de 1 qui protège vos messages, vos comptes bancaires et vos secrets. Pendant des décennies, la seule façon d'ouvrir ce coffre-fort était d'essayer toutes les combinaisons possibles, une par une, jusqu'à ce que la chance tourne. C'est comme essayer chaque clé sur un énorme trousseau ; s'il y a un milliard de clés, vous devrez peut-être en essayer un demi-milliard avant de trouver la bonne. C'est la méthode « classique » pour faire les choses, et c'est lent.

Puis, les scientifiques ont découvert un outil magique appelé « ordinateur quantique ». Voyez-le non pas comme une calculatrice plus rapide, mais comme un sorcier capable de regarder beaucoup de clés en même temps. En utilisant un célèbre tour de passe-passe appelé l'algorithme de Grover, ce sorcier peut trouver la bonne clé bien plus vite que l'ancienne méthode — réduisant le temps d'un milliard d'essais à environ trente mille. Mais voici le rebondissement : et si vous n'aviez pas à partir de zéro ? Et si un voleur sournois avait déjà jeté un coup d'œil au coffre et obtenu une version « bruitée », floue, de la clé ? Peut-être a-t-il vu que la clé était « principalement » 101010, mais avec quelques bits flous. C'est ce qu'on appelle une « attaque par canal auxiliaire » (side-channel attack). C'est comme trouver une empreinte digitale sur le coffre qui donne un indice, même si celui-ci n'est pas parfait. La grande question pour les scientifiques est la suivante : pouvons-nous utiliser ces indices flous pour rendre le sorcier quantique encore plus intelligent et plus rapide ?

Cet article, écrit par une équipe de chercheurs de l'Information Engineering University, plonge au cœur de précisément ce scénario. Ils demandent : si un attaquant possède une clé bruitée avec des erreurs (comme une photo floue de la solution), comment pouvons-nous utiliser les ordinateurs quantiques pour trouver la vraie clé plus rapidement que jamais ?

Les chercheurs ont d'abord examiné comment un ordinateur classique gérerait cela. Ils ont réalisé que si l'on sait que la clé est « principalement » correcte, il ne faut pas deviner au hasard. Au lieu de cela, on devrait commencer par deviner la clé qui ressemble exactement à la version bruitée, puis deviner les clés qui ont une seule petite erreur, puis deux erreurs, et ainsi de suite. C'est comme chercher dans une bibliothèque en commençant par les livres qui ressemblent le plus à celui que l'on cherche, plutôt que d'entrer et de saisir des livres au fond de la pièce. Ils ont calculé exactement combien de tentatives cette méthode classique « intelligente » nécessiterait.

Ensuite, ils ont construit un nouvel algorithme quantique pour faire la même chose, mais avec la puissance de la mécanique quantique. Ils ont remarqué que les méthodes quantiques précédentes tentaient de diviser l'espace de recherche en blocs dont la taille augmentait selon un schéma géométrique (1, puis 10, puis 100). Cependant, les chercheurs ont découvert que les indices de la « clé bruitée » créent en réalité un schéma très spécifique basé sur le nombre d'erreurs (la distance de Hamming). Au lieu d'utiliser un schéma géométrique, ils ont décidé de regrouper les clés par nombre d'erreurs : un groupe pour les clés avec 0 erreur, un groupe pour 1 erreur, un groupe pour 2 erreurs, et ainsi de suite.

Ils ont conçu une stratégie où l'ordinateur quantique s'attaque à ces groupes un par un, en commençant par le groupe qui est le plus susceptible de contenir la réponse. Pour que cela fonctionne, ils ont dû résoudre un problème délicat : comment préparer l'ordinateur quantique pour qu'il ne regarde que les clés ayant, par exemple, exactement 3 erreurs, sans perdre de temps avec les autres. Ils ont résolu cela en utilisant un état quantique spécial appelé « état de Dicke ». Vous pouvez imagander un état de Dicke comme un jeu de cartes parfaitement organisé où chaque carte possède exactement le même nombre de cœurs rouges. Une fois qu'ils ont cet état organisé, ils peuvent facilement retourner les cartes pour qu'elles correspondent à la clé bruitée qu'ils possèdent. Cette préparation est efficace et ne nécessite pas d'équipement supplémentaire et désordonné.

Lorsqu'ils ont lancé des simulations pour tester leur nouvelle méthode, les résultats ont été impressionnants. Ils ont utilisé une clé de 256 bits (une clé très longue et sécurisée) avec un taux d'erreur infime de 1 % (ce qui signifie que la clé bruitée était correcte à 99 %).

Un ordinateur classique standard aurait besoin d'environ $2^{256}$ tentatives s'il n'avait aucun indice.
Avec l'indice bruité, un ordinateur classique intelligent aurait toujours besoin d'environ $2^{62,29}$ tentatives.
Leur nouvel algorithme quantique n'a nécessité qu'environ $2^{19,77}$ tentatives.

Cela signifie que leur méthode quantique est nettement plus rapide que la méthode classique intelligente. Ils ont calculé un « facteur d'accélération » de 3,15, ce qui est supérieur à l'accélération de 2,73 obtenue par les méthodes précédentes (comme celles de Glaser). En termes simples, leur sorcier quantique ne se contente pas de regarder plus de clés à la fois ; il regarde les bonnes clés en premier, grâce à la manière spécifique dont ils ont organisé leur recherche.

L'article argumente également explicitement contre l'utilisation de l'ancienne stratégie de croissance géométrique des blocs (comme l'algorithme de Montanaro) pour ce type spécifique de problème de clé bruitée. Ils démontrent que, puisque les erreurs suivent une « distribution de Bernoulli » spécifique (un schéma de basculements aléatoires), l'approche géométrique n'est pas la plus efficace. Leur approche par « distance de Hamming », qui regroupe les clés par le nombre exact d'erreurs, est mieux adaptée à la réalité.

En résumé, cette recherche suggère qu'en combinant les « indices flous » des attaques par canal auxiliaire avec une stratégie de recherche quantique intelligemment organisée, nous pouvons craquer les clés beaucoup plus vite qu'auparavant. Bien que ces résultats soient actuellement basés sur des simulations et des preuves mathématiques plutôt que sur un ordinateur quantique physique exécutant le code, les mathématiques montrent une voie claire vers une recherche de clé quantique ultra-rapide qui surpasse à la fois les devinettes de la vieille école et les tentatives quantiques précédentes. L'équipe conclut que cette méthode est non seulement théoriquement solide, mais aussi pratiquement réalisable, car la préparation de l'« état de Dicke » qu'ils proposent peut être effectuée avec un nombre gérable d'étapes et sans nécessiter de matériel supplémentaire complexe.

Résumé Technique : Algorithmes de recherche de clés quantiques sous attaque par canal auxiliaire

Énoncé du problème
Cette recherche traite du problème de la recherche de clés dans les algorithmes cryptographiques lorsqu'un attaquant possède une clé bruitée dérivée d'attaques par canaux auxiliaires (SCA). Dans ce scénario, l'attaquant obtient une clé $Y$ qui diffère de la véritable clé cible $k^*$ par un certain nombre de basculements de bits (distance de Hamming). La distribution de probabilité de l'espace des clés n'est pas uniforme ; elle suit une distribution de Bernoulli à $n$ épreuves déterminée par le taux d'erreur binaire (BER), $\alpha$ . Le défi consiste à rechercher efficacement cet espace de clés non uniforme pour trouver $k^*$ , en exploitant l'information préalable fournie par la clé bruitée. Alors qu'une recherche par force brute classique nécessite $O(N)$ requêtes et que l'algorithme de Grover standard offre $O(\sqrt{N})$ , aucun des deux n'exploite pleinement la structure spécifique de la distribution de Bernoulli induite par les SCA. De plus, les approches quantiques existantes, telles que l'algorithme de Montanaro, rencontrent des difficultés pour préparer les états de superposition initiaux spécifiques requis pour les blocs de clés ayant des probabilités postérieures égales.

Méthodologie
Les auteurs proposent un cadre complet comprenant la modélisation théorique, la conception d'algorithmes et la préparation d'états :

Modélisation probabiliste : L'étude modélise la distribution de l'espace des clés en supposant des basculements de bits indépendants et identiquement distribués (i.i.d.) avec une probabilité $\alpha$ . En utilisant le théorème de Bayes, il est démontré que la probabilité postérieure d'une clé candidate dépend uniquement de sa distance de Hamming $d$ par rapport à la clé bruitée $Y$ . Cela établit que les clés ayant la même distance de Hamming partagent la même probabilité postérieure.
Référence classique : Un algorithme de recherche de clé classique est dérivé, qui parcourt les clés candidates par ordre décroissant de leur probabilité postérieure (c'est-à-dire en commençant par la distance de Hamming $d=0$ jusqu'à $d=n$ ). La complexité de requête attendue $G_c$ est strictement calculée sur la base de la distribution binomiale des clés candidates à chaque distance.
Algorithme quantique amélioré :
- Stratégie de partition : Contrairement à l'algorithme de Montanaro, qui partitionne l'espace des clés en blocs à croissance géométrique $\{1, c, c^2, \dots\}$ , cet article propose de partitionner l'espace des clés en $(n+1)$ blocs $\{R_0, R_1, \dots, R_n\}$ basés strictement sur la distance de Hamming $d$ . Chaque bloc $R_d$ contient les $\binom{n}{d}$ clés candidates ayant exactement $d$ erreurs de bits.
- Exécution de la recherche : L'algorithme itère à travers ces blocs dans l'ordre décroissant de probabilité (croissance de $d$ ). Pour chaque bloc $R_d$ , il prépare une superposition uniforme des clés de ce bloc et applique l'algorithme de Grover.
- Analyse de complexité : La complexité de requête quantique $G_q$ est dérivée en sommant les coûts de la recherche de Grover sur chaque bloc, pondérés par la probabilité que la clé cible réside dans ce bloc.
Préparation de l'état initial : Pour résoudre la difficulté de préparation de l'état de superposition spécifique pour chaque bloc $R_d$ $R_{d}$ , les auteurs établissent une équivalence entre l'état de la clé candidate et l'état de Dicke $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ . Ils prouvent que la superposition uniforme des clés à une distance de Hamming $d$ $d$ de $Y$ $Y$ peut être générée en appliquant un produit tensoriel de portes Pauli-X ( $X^{\otimes Y}$ $X^{\otimes Y}$ ) à l'état de Dicke $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ .
- Implémentation : L'état de Dicke est préparé à l'aide d'un circuit de type "diviser pour régner" à faible profondeur (basé sur les travaux de Bärtschi et Eidenbenz) ne nécessitant aucun qubit auxiliaire. L'état final est obtenu en appliquant $O(d)$ portes X basées sur la clé bruitée $Y$ .

Contributions clés

Dérivation théorique : L'article fournit une dérivation rigoureuse de la complexité computationnelle pour la recherche de clés classique et quantique dans des conditions d'attaque par canal auxiliaire, en modélisant spécifiquement la distribution de Bernoulli à $n$ épreuves.
Amélioration algorithmique : Il introduit un algorithme de recherche de clé quantique amélioré qui utilise une stratégie de partition de blocs basée sur la distance de Hamming. Cette stratégie s'avère plus cohérente avec la distribution réelle des clés dans les scénarios SCA que la partition géométrique utilisée par l'algorithme de Montanaro.
Solution de préparation d'état : Le travail résout le goulot d'étranglement de la préparation de l'état d'entrée en transformant le problème en une préparation d'état de Dicke. Il démontre que l'état requis peut être généré avec $O(nd)$ portes CNOT et une faible profondeur de circuit ( $O(d \log \frac{n}{d})$ pour une topologie de piège à ions ou $O(\sqrt{nd})$ pour une topologie supraconductrice) sans qubits auxiliaires.

Résultats
Les résultats de simulation pour une clé cryptographique de 256 bits avec un taux d'erreur binaire (BER) de 1 % ( $\alpha = 0,01$ ) démontrent des gains de performance significatifs :

Réduction de la complexité : La complexité de requête pour l'algorithme classique dans des conditions de SCA chute de $2^{256}$ (sans SCA) à $2^{62,29}$ . L'algorithme quantique proposé réduit davantage cela à $2^{19,77}$ .
Facteur d'accélération : L'algorithme quantique proposé atteint un facteur d'accélération de 3,15 par rapport à l'algorithme classique dans des conditions de SCA. Ceci est comparé à un facteur d'accélération de 2,73 rapporté par Glaser et al. (qui ont analysé l'algorithme de Montanaro) dans les mêmes conditions. Les auteurs notent que leur efficacité de recherche est améliorée de 15,38 % par rapport à l'efficacité obtenue par l'algorithme à croissance géométrique de Montanaro proposé dans [9].
Comparaison avec les bornes : L'article affirme que la complexité de requête quantique dérivée ( $2^{19,77}$ ) est plus précise et plus serrée que les bornes supérieures/inférieures ( $2^{21,59}$ et $2^{17,59}$ ) estimées par Glaser pour l'algorithme de Montanaro dans ce scénario de distribution spécifique.
Efficacité des ressources : Le schéma de préparation d'état est montré comme étant réalisable avec des circuits de faible profondeur, avec des comptes de ressources spécifiques pour $n=256$ et $d=4$ (par exemple, 1024 portes CNOT, 0 qubit ancillaire).

Signification
L'article affirme que sa recherche fournit une solution complète, de l'analyse théorique à l'implémentation pratique, pour la cryptanalyse quantique sous attaques par canaux auxiliaires. En exploitant la structure spécifique du bruit de canal auxiliaire (distribution de Bernoulli), l'algorithme proposé atteint une accélération super-quadratique par rapport aux contreparties classiques, surpassant les adaptations précédentes de la recherche quantique comme celle de Montanaro. La capacité de préparer les états initiaux nécessaires à l'aide de circuits à faible profondeur et sans ancilla lève une barrière critique à l'implémentation pratique de la recherche de clés quantiques. Les auteurs affirment que ces résultats offrent une estimation de complexité plus précise et une stratégie de recherche plus efficace pour les scénarios où une information préalable sous forme de clé bruitée est disponible. Les travaux futurs identifiés consistent à explorer l'intégration de cet algorithme avec des chiffrements spécifiques (AES, SM4) et à analyser l'impact du bruit quantique.

Résumé Technique : Algorithmes de recherche de clés quantiques sous attaque par canal auxiliaire

Articles similaires