Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

Ce papier propose une approche novatrice qui exploite la structure circulante des couches linéaires en cryptographie symétrique pour construire des séquences de transformations, permettant aux algorithmes heuristiques d'obtenir des comptages de XOR et des profondeurs de circuits nettement plus efficaces pour des chiffrements par blocs tels que Whirlwind et AES par rapport aux résultats antérieurs de l'état de l'art.

L'essentiel

Imaginez que vous êtes un architecte maître d'œuvre tentant de construire une machine complexe en utilisant un ensemble spécifique de briques Lego. Dans le monde de la cryptographie (la science des codes secrets), ces « machines » sont appelées couches linéaires, et ce sont les chevaux de trait qui brouillent les données pour les maintenir en sécurité.

Pendant des années, les architectes ont tenté de construire ces machines en utilisant le moins de briques possible (pour économiser de l'espace) et le temps le plus court possible (pour gagner en vitesse). Le document que vous avez fourni présente une nouvelle façon de concevoir ces machines en remarquant un motif caché dans les plans.

Voici la décomposition de leur découverte, expliquée simplement :

1. Le Problème : Le « Mur de Briques » de la Complexité

Considérez une couche linéaire cryptographique comme un mur massif d'interrupteurs. Pour brouiller un message, vous devez actionner ces interrupteurs dans un ordre très spécifique.

• L'Objectif : Vous voulez actionner les interrupteurs en utilisant le moins de mouvements possible (pour économiser de l'énergie/l'espace) et en un minimum d'étapes (pour le rendre rapide).
• L'Ancienne Méthode : Les méthodes précédentes traitaient le mur comme un gigantesque chaos d'interrupteurs. Elles utilisaient des algorithmes d'essai-erreur pour trouver le meilleur ordre, mais comme le mur était si grand et désordonné, elles manquaient souvent le chemin le plus efficace. C'était comme essayer de résoudre un labyrinthe en heurtant les murs au hasard.

2. La Découverte : Le Motif de la « Roue Rotative »

Les auteurs ont remarqué que beaucoup de ces murs cryptographiques ne sont pas réellement aléatoires. Ils possèdent une Structure Circulante.

• L'Analogie : Imaginez un manège. Si vous prenez une photo des chevaux, puis que vous faites pivoter la photo, le motif des chevaux semble presque identique, simplement décalé.
• En termes mathématiques, la matrice (le plan des interrupteurs) est construite en décalant une seule ligne encore et encore. C'est un motif répétitif et rotatif.
• L'Insight : Les architectes précédents ignoraient ce motif de « manège » et traitaient le mur comme un chaos. Les auteurs ont réalisé que si vous reconnaissez ce motif, vous pouvez démonter le mur beaucoup plus efficacement.

3. La Solution : L'Astuce du « Pliage »

Au lieu d'essayer de résoudre tout le mur géant d'un coup, les auteurs ont développé une méthode pour plier le problème.

• La Métaphore : Imaginez que vous avez une grande et lourde couette avec un motif répétitif. Au lieu d'essayer de plier l'ensemble d'un coup, vous réalisez que, puisque le motif se répète, vous pouvez plier la moitié gauche sur la moitié droite, puis le haut sur le bas.
• En utilisant cette technique de « pliage » (transformant mathématiquement la matrice), ils peuvent transformer un mur massif et complexe en une forme beaucoup plus simple, triangulaire.
• Une fois le mur simplifié en cette forme triangulaire, des outils standards peuvent facilement terminer le travail. C'est comme transformer une pelote de laine emmêlée en une ligne droite et nette avant d'essayer de faire un nœud.

4. Les Résultats : Des Machines Plus Rapides et Plus Petites

Les auteurs ont testé cette nouvelle méthode de « pliage » sur de vraies machines cryptographiques utilisées dans des systèmes de sécurité populaires. Les résultats étaient impressionnants :

• La Machine « Tourbillon » :

  • Vitesse : Ils ont réduit le temps nécessaire pour exécuter la machine de 39 %. Imaginez une voiture qui prenait auparavant 28 secondes pour parcourir un mile et qui le fait maintenant en 17 secondes.
  • Taille : Ils ont réduit le nombre de « briques » (portes logiques) nécessaires d'environ 30 %. Cela signifie que la machine est plus petite et consomme moins d'énergie.

• La Machine « AES » (La Référence) :

  • AES est le standard de chiffrement le plus célèbre au monde. Sa partie « MixColumn » est un puzzle notoirement difficile à résoudre efficacement.
  • La Réalisation : Les auteurs ont construit un système automatisé qui a résolu ce puzzle presque aussi bien qu'un expert humain ayant passé des semaines à ajuster manuellement la conception.
  • La Nuance : La conception de l'expert humain utilisait 105 « briques ». La conception automatisée des auteurs en utilisait 107. Ce n'est que 2 briques supplémentaires pour un résultat obtenu automatiquement, et non à la main. Ils ont également égalé le record de la vitesse la plus rapide (profondeur).

5. Pourquoi Cela Compte

• Pour l'Avenir : À mesure que les ordinateurs deviennent plus puissants (y compris les ordinateurs quantiques), ces « machines » doivent être plus rapides et plus petites pour rester sécurisées.
• L'Essentiel : En reconnaissant simplement que le plan possède un motif répétitif et rotatif (comme un manège), les auteurs ont trouvé un raccourci que les méthodes précédentes avaient manqué. Ils n'ont pas inventé un nouveau type de brique ; ils ont simplement trouvé un moyen plus intelligent de les empiler.

En résumé : Le document dit : « Nous avons découvert que de nombreux codes de sécurité sont construits sur un motif répétitif. En utilisant ce motif pour simplifier d'abord la conception, nous pouvons construire les systèmes de sécurité plus rapidement et plus petits que jamais, battant même certains des meilleurs experts humains. »

Résumé technique

Résumé technique : Exploitation de la structure circulante pour optimiser les implémentations des couches linéaires

Énoncé du problème
L'optimisation des couches linéaires en cryptographie symétrique est cruciale tant pour les implémentations légères (contraintes par le nombre de portes et la surface) que pour les évaluations de sécurité quantique (contraintes par la profondeur du circuit et le coût DW). Bien que des algorithmes heuristiques existent pour synthétiser des circuits CNOT (quantique) et des circuits XOR (classique) pour des matrices inversibles générales, ils échouent souvent à exploiter pleinement les structures algébriques spécifiques inhérentes aux conceptions cryptographiques. De nombreuses matrices largement utilisées, telles que celles de MixColumn d'AES et de Whirlwind, possèdent une structure circulante. Les méthodes actuelles de l'état de l'art, comme celles de Shi et Feng [SF24], traitent ces matrices comme des matrices binaires générales $n \times n$, manquant potentiellement des opportunités de réduire la profondeur du circuit et le nombre de portes en exploitant leurs propriétés circulantes sous-jacentes.

Méthodologie
Les auteurs proposent un cadre novateur qui utilise explicitement la structure circulante des matrices pour guider la synthèse de circuits efficaces. La méthodologie centrale implique une stratégie de décomposition récursive qui transforme une matrice circulante sur une extension de corps (par exemple, $F_{2^k}$ ou $GL(F_2, m)$) en une forme plus simple, spécifiquement une matrice triangulaire supérieure, avant d'appliquer une optimisation heuristique standard.

Les composants techniques clés incluent :

1. Transformation récursive de blocs : Le théorème 3 établit qu'une matrice circulante $2^k \times 2^k$ sur $F_2[x]$ peut être transformée en une matrice triangulaire supérieure par blocs en utilisant des opérations élémentaires sur les lignes et les colonnes. L'algorithme divise récursivement la matrice en blocs $A$ et $B$ (où $M = \begin{smallmatrix} A & B \\ B & A \end{smallmatrix}$), appliquant des opérations pour annuler des blocs spécifiques (par exemple, transformer en $\begin{smallmatrix} A+B & B \\ A+B & \dots \end{smallmatrix}$).
2. Exploration des chemins de transformation : Les auteurs observent que différents choix d'opérations sur les lignes et les colonnes lors de l'étape récursive conduisent à des matrices intermédiaires différentes. L'algorithme (Algorithme 1) explore plusieurs chemins de transformation (jusqu'à $4^{2^k-1}$ possibilités pour de petits $k$) afin de trouver le chemin qui produit le circuit ultérieur le plus efficace.
3. Arrêt anticipé et solution de repli : Reconnaissant que le bénéfice de la récursion diminue avec la profondeur, les auteurs introduisent une stratégie (Algorithme 2) pour arrêter la récursion prématurément. L'algorithme itère à travers différentes « tailles de blocs », variant ainsi efficacement la profondeur de récursion. Si la récursion est arrêtée tôt, la matrice résultante est transmise à un optimiseur heuristique standard (Heu) pour la synthèse générale de CNOT/XOR. Cela inclut une stratégie de « solution de repli » où la profondeur de récursion est nulle, traitant efficacement la matrice comme un cas général.
4. Optimisation automatisée : Contrairement aux approches manuelles précédentes (par exemple, Zhang et al. [ZSWS24] pour AES), cette méthode automatise le processus de recherche de la forme de matrice « plus simple » et des séquences de portes correspondantes, éliminant le besoin d'intervention humaine.

Contributions clés

• Cadre novateur : Il s'agit du premier travail à exploiter systématiquement la structure circulante des couches linéaires pour optimiser les implémentations de circuits, comblant le fossé entre les propriétés algébriques des matrices et les heuristiques de synthèse de circuits.
• Synthèse automatisée : Les auteurs fournissent un algorithme automatisé qui remplace les optimisations manuelles spécifiques à chaque cas. Il génère des séquences de matrices de transformation permettant aux heuristiques en aval de trouver des implémentations plus efficaces.
• Optimisation duale : Le cadre est applicable aux circuits quantiques (minimisation du nombre et de la profondeur des CNOT) et aux circuits classiques (minimisation des comptes XOR, spécifiquement g-XOR et s-XOR).

Résultats
Les auteurs ont évalué leur méthode sur un ensemble de données de couches linéaires provenant de chiffrements par blocs (incluant AES, Whirlwind, Clefia, PRIDE, etc.) et de matrices MDS construites.

• Profondeur de circuit quantique :

  • Whirlwind M0 : La méthode proposée a réduit la profondeur du circuit de 28 (état de l'art précédent par [SF24]) à 17, soit une amélioration de 39 %. Le nombre de portes a également été réduit de 286 à 200.
  • MixColumn d'AES : La méthode automatisée a atteint une profondeur de 10, égalant le résultat de l'état de l'art optimisé manuellement par Zhang et al. [ZSWS24]. Le nombre de portes était de 107, soit seulement 2 CNOT de plus que le résultat manuel (105) et nettement meilleur que les 131 CNOT obtenus par [SF24].
  • Autres matrices : Des réductions significatives de profondeur ont été observées pour des matrices à haute densité (par exemple, Whirlwind, SKOP15 8x8), tandis que les améliorations étaient marginales ou inexistantes pour les matrices clairsemées où les heuristiques fonctionnent déjà bien.

• Circuit classique (compte XOR) :

  • Whirlwind M0 : La méthode a atteint un compte s-XOR de 159, surpassant le meilleur précédent de 173 (Yuan et al. [YWS+24]) d'environ 8 %.
  • Performance générale : Bien que la méthode entraîne généralement une surcharge de taille pour de nombreuses matrices, elle a réussi à battre les résultats de l'état de l'art pour des matrices spécifiques à haute densité comme Whirlwind M0 et M1.

Signification et affirmations
L'article affirme que l'exploitation de la structure circulante est une voie puissante, jusque-là sous-utilisée, pour optimiser les couches linéaires. Les auteurs affirment que leur approche :

1. Surpasse les heuristiques existantes pour des matrices spécifiques et denses où les stratégies gourmandes standard peinent.
2. Automatise l'optimisation manuelle, obtenant des résultats comparables aux circuits ajustés par des experts humains (comme on le voit pour MixColumn d'AES) sans nécessiter d'intervention manuelle.
3. Fournit une nouvelle référence pour les évaluations de sécurité quantique, offrant des estimations de profondeur plus précises pour les couches linéaires, ce qui est crucial pour calculer le coût DW (Profondeur $\times$ Largeur) dans les évaluations de sécurité post-quantique.

Les auteurs concluent que si la méthode n'est pas universellement supérieure pour tous les types de matrices (en particulier les matrices clairsemées), elle offre un avantage significatif pour les matrices à structure circulante et à haute densité, démontrant le potentiel de l'intégration des propriétés algébriques dans la synthèse de circuits.