Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

Cet article présente une implémentation de circuit quantique optimisée en qubits du chiffrement hybride ARX-SPN léger GFSPX et évalue sa sécurité post-quantique par une attaque de Grover parallélisée, révélant un coût quantique total de $1,12 \times 2^{159}$ portes qui, bien qu'inférieur aux seuils du niveau 1 du NIST, démontre une résistance supérieure par rapport à d'autres conceptions légères.

L'essentiel

Imaginez que vous possédez une serrure numérique très spéciale et légère (appelée GFSPX), conçue pour protéger les données sur de petits appareils tels que des capteurs intelligents ou des étiquettes RFID. Cette serrure est conçue pour être rapide et consommer très peu d'énergie, ce qui la rend parfaite pour l'« Internet des objets ».

Cependant, un nouveau type d'« super-outil » appelé ordinateur quantique émerge. Contrairement aux ordinateurs classiques qui vérifient les clés une par une, un ordinateur quantique peut vérifier de nombreuses clés simultanément, potentiellement en cassant ces serrures beaucoup plus rapidement. Cet article pose une question simple : Si un ordinateur quantique tente de casser cette serrure spécifique, combien cela sera-t-il réellement difficile ?

Voici la décomposition de leurs résultats à l'aide d'analogies quotidiennes :

1. La conception de la serrure : un moteur hybride

La serrure GFSPX n'est pas construite avec un seul type de mécanisme. C'est un hybride, comme une voiture qui utilise à la fois un moteur à essence et un moteur électrique.

• La partie « Essence » (ARX) : Elle utilise des opérations mathématiques simples (Addition, Rotation, OU Exclusif) qui sont très efficaces mais peuvent être un peu lentes pour propager les changements dans les données.
• La partie « Électrique » (SPN) : Elle utilise un réseau de substitution complexe (comme mélanger un jeu de cartes) qui propage les changements très rapidement.
• Le résultat : En les combinant, la serrure est rapide et efficace. Les auteurs ont construit un plan numérique de cette serrure spécifiquement pour un ordinateur quantique afin de voir exactement comment elle fonctionne à l'intérieur.

2. Le plan quantique : construire le circuit

Pour tester la serrure, les chercheurs ont dû construire un « circuit quantique ». Imaginez cela comme la construction d'une usine miniature et réversible où chaque étape peut être annulée parfaitement (de sorte qu'aucune information ne soit perdue).

• Le défi : Les ordinateurs quantiques sont fragiles. Vous ne pouvez pas simplement copier les données ; vous devez être très prudent avec les « qubits » (les bits quantiques, comme de minuscules toupies).
• La solution : Les chercheurs ont optimisé la conception pour utiliser le nombre de qubits le plus faible possible (209 d'entre eux). Ils ont utilisé une astuce ingénieuse appelée « additionneur à propagation de retenue » pour les parties mathématiques, ce qui est comme une chaîne de montage très efficace qui ne gaspille pas d'espace.
• L'empreinte : Le plan final est compact, nécessitant un « plancher d'usine » de 209 qubits et un nombre spécifique d'étapes (portes) pour exécuter un chiffrement complet.

3. L'attaque : la recherche « Grover »

Pour casser la serrure, un ordinateur quantique utilise l'algorithme de Grover.

• L'analogie : Imaginez que vous avez une immense bibliothèque contenant $2^{128}$ livres (un nombre si énorme qu'il est difficile à comprendre), et qu'un seul livre contient la clé correcte.
  • Un ordinateur classique est comme un bibliothécaire qui vérifie un livre à la fois. Cela prendrait une éternité.
  • Un ordinateur quantique est comme un bibliothécaire magique qui peut vérifier de nombreux livres simultanément. Il trouve le bon livre en environ la racine carrée du temps.
• Le piège : Pour s'assurer que l'ordinateur quantique ne choisit pas le mauvais livre (un « faux positif »), les chercheurs ont fait en sorte que l'ordinateur vérifie trois serrures différentes (en utilisant trois paires différentes de messages verrouillés/déverrouillés) en même temps. Si une clé ouvre les trois, c'est définitivement la bonne.

4. Le verdict : solide, mais pas une preuve « post-quantique »

Les chercheurs ont calculé le « coût » total de cette attaque quantique.

• Le coût : Ils ont découvert que casser la serrure nécessiterait une quantité massive de puissance de calcul, équivalente à environ $1,12 \times 2^{159}$ opérations.
• La norme : L'Institut national des normes et de la technologie des États-Unis (NIST) a fixé une « barre de sécurité » pour l'avenir. Pour être considéré comme vraiment sûr contre les ordinateurs quantiques (niveau de sécurité 1), une serrure doit avoir un coût d'au moins $2^{170}$.
• Le résultat : La serrure GFSPX est en dessous de la barre de sécurité. Elle n'est pas assez sûre pour les normes post-quantiques les plus strictes.
  • Cependant, l'article note que par rapport à d'autres serrures légères, GFSPX est en réalité l'une des plus difficiles à casser. Elle se situe dans un « juste milieu » où elle est très efficace pour les petits appareils, mais offre tout de même une résistance décente contre les attaques quantiques, même si elle ne passe pas le test de sécurité le plus élevé.

5. L'essentiel

L'article conclut que, bien que cette serrure hybride soit excellente pour les appareils actuels aux ressources limitées, la taille de la clé de 128 bits est tout simplement trop petite pour survivre à une attaque quantique déterminée dans le futur.

• Le compromis : Vous pouvez avoir une serrure qui est petite et rapide (bonne pour les capteurs d'aujourd'hui), ou une serrure qui est massive et lente (bonne pour la sécurité quantique future), mais cette conception spécifique tente de faire les deux et échoue légèrement sur le front de la « sécurité future ».
• Conseils pour l'avenir : Pour rendre cette conception véritablement invulnérable aux quantiques, les auteurs suggèrent soit d'allonger la clé (comme 192 ou 256 bits), soit d'ajuster les parties mathématiques pour les rendre encore plus difficiles à traiter par les ordinateurs quantiques.

En bref : GFSPX est une serrure très ingénieuse et efficace, plus difficile à casser que la plupart de ses pairs, mais elle n'est tout simplement pas assez forte pour résister aux ordinateurs quantiques surpuissants de l'avenir sans quelques mises à niveau.

Résumé technique

Résumé Technique : Réalisation de Circuit Quantique et Cryptanalyse de Grover du Chiffre Hybride ARX-SPN GFSPX

Énoncé du Problème
L'émergence de l'informatique quantique remet fondamentalement en cause la sécurité des primitives symétriques classiques. Alors que l'algorithme de Shor menace la cryptographie à clé publique, l'algorithme de Grover offre une accélération quadratique pour la recherche non structurée, réduisant efficacement de moitié la marge de sécurité des constructions à clé symétrique. Par conséquent, les chiffrements par blocs légers (BC), conçus pour des environnements à ressources limitées comme l'Internet des Objets (IoT) et la RFID, nécessitent une réévaluation rigoureuse de leur résilience post-quantique. Plus précisément, il est nécessaire de quantifier les ressources quantiques requises pour mener une attaque de récupération de clé sur des conceptions hybrides combinant les paradigmes Addition-Rotation-XOR (ARX) et Réseau de Substitution-Permutation (SPN).

Méthodologie
Les auteurs présentent une réalisation complète de circuit quantique et une cryptanalyse de Grover de GFSPX, un chiffrement par blocs léger disposant d'un bloc de données de 64 bits et d'une clé secrète de 128 bits. GFSPX utilise une Structure de Feistel Généralisée (GFS) à 4 branches intégrant deux blocs fonctionnels distincts : une fonction basée sur ARX ($F_1$) pour la non-linéarité et une structure SPN de 32 bits ($F_2$) pour une diffusion rapide.

La méthodologie se déroule en trois étapes :

1. Réalisation de Circuit Quantique : La structure classique de GFSPX est mappée dans un circuit quantique réversible. Les auteurs exploitent la réversibilité inhérente du réseau de Feistel pour minimiser l'utilisation de qubits auxiliaires.
   • $F_1$ (ARX) : Implémentée à l'aide d'un additionneur à propagation de retenue (RCA) compact basé sur l'architecture de Cuccaro et al. Cette approche minimise la surcharge en qubits en omettant le bit de retenue final pour l'addition modulaire et en utilisant des portes de majorité (MAJ) et d'UnMajority-and-Add (UMA) in situ.
   • $F_2$ (SPN) : La couche de boîtes-S (basée sur PRESENT) est synthétisée à l'aide d'un ensemble minimal de portes CNOT et Toffoli sans ancillae supplémentaires. La couche de permutation (couche P) est implémentée via des portes SWAP parallélisables pour maintenir une faible profondeur de circuit.
   • Génération de Clés : La génération de clés maîtresse de 128 bits est réalisée comme une évolution unitaire impliquant une rotation cyclique gauche de 113 bits, des substitutions par boîtes-S et des XOR avec des compteurs de tour, optimisée pour une exécution in situ.
2. Estimation des Ressources : Le coût quantique est calculé en utilisant des métriques de décomposition standard (coût NOT et CNOT = 1, coût Toffoli = 6). L'analyse évalue à la fois un coût de base (excluant la surcharge de routage SWAP) et une borne supérieure (décomposant les SWAPs en trois CNOTs).
3. Cryptanalyse de Grover : Une oracle Grover parallélisée ($U_f$) est construite pour évaluer le chiffrement contre les attaques de récupération de clé. Pour éliminer les correspondances erronées dans l'espace de clés de 128 bits, l'oracle utilise trois paires texte clair-texte chiffré ($r=3$). La complexité de l'attaque est estimée en multipliant les métriques de ressources de l'oracle par le nombre optimal d'itérations de Grover ($\approx \frac{\pi}{4}2^{64}$).

Contributions Clés

• Implémentation Quantique Optimisée : L'article fournit un circuit quantique optimisé en qubits pour GFSPX, atteignant une empreinte de 209 qubits. La conception réalise un coût quantique de base de 32 498 portes avec une profondeur de circuit de 7 617.
• Analyse de l'Architecture Hybride : L'étude détaille la distribution des ressources d'une conception hybride ARX-SPN, démontrant que bien que le primitif d'addition modulaire domine le nombre total de portes, les couches de permutation parallélisées dans le composant SPN aident à maintenir un rapport porte-profondeur compétitif.
• Évaluation Quantitative de la Sécurité : Les auteurs construisent une oracle Grover utilisant trois paires texte clair-texte chiffré et calculent le coût total de l'attaque dans le cadre MAXDEPTH du NIST. L'analyse révèle un coût total d'attaque quantique d'environ $1,12 \times 2^{159}$ portes pour $r=3$.
• Étalonnage Comparatif : L'implémentation est comparée à d'autres chiffrements légers (par exemple, PRESENT, GIFT, SIMON, SPECK). GFSPX atteint le meilleur rapport coût-profondeur (4,27) parmi les conceptions comparées, indiquant une haute efficacité d'exécution parallèle.

Résultats

• Métriques de Ressources : Le circuit complet GFSPX de 20 tours nécessite 209 qubits. Le coût de base est de 32 498, s'élevant à 47 789 lorsque la surcharge de routage SWAP est incluse. La profondeur du circuit est de 7 617.
• Complexité de l'Attaque : Le coût quantique total pour une attaque de récupération de clé est estimé à $1,12 \times 2^{159}$ (pour $r=3$).
• Classification de Sécurité : Dans le cadre de la cryptographie post-quantique du NIST, le seuil de sécurité de niveau 1 (équivalent à AES-128) nécessite un coût total d'attaque d'au moins $2^{170}$. Le coût estimé pour GFSPX ($2^{159}$) est inférieur à ce seuil.
• Compromis de Conception : Bien que GFSPX démontre une résistance supérieure aux attaques quantiques par rapport à de nombreuses conceptions SPN pures (qui se situent autour de $2^{152}$), il ne répond pas aux critères stricts de sécurité de niveau 1 pour une longueur de clé de 128 bits. Le coût de la conception hybride est fortement influencé par le composant ARX (addition modulaire), plaçant son profil de sécurité plus proche de celui des chiffrements basés sur ARX comme SIMON et SPECK.

Importance
L'article affirme que ses résultats fournissent des informations cruciales sur l'équilibre entre l'efficacité matérielle classique et la résilience quantique pour les conceptions cryptographiques de nouvelle génération. L'étude met en évidence un compromis fondamental : bien que les conceptions hybrides ARX-SPN offrent des performances classiques robustes et une meilleure résistance quantique que les conceptions SPN pures, une longueur de clé de 128 bits reste structurellement insuffisante pour atteindre la sécurité de niveau 1 du NIST face à des adversaires quantiques avancés. Les auteurs suggèrent que les recherches futures devraient se concentrer sur l'extension des longueurs de clés (par exemple, à 192 ou 256 bits) ou sur l'optimisation des primitives d'addition modulaire réversibles pour améliorer les marges de sécurité. La méthodologie établie dans ce travail sert de cadre rigoureux pour évaluer d'autres conceptions hybrides dans des environnements à ressources limitées.