A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

Cet article présente une nouvelle méthode compacte pour encoder des formules logiques computationnelles en QUBO, permettant de réduire considérablement le nombre de variables nécessaires pour modéliser des algorithmes cryptographiques comme AES et SHA, ce qui accroît leur vulnérabilité potentielle face aux futurs recuits quantiques.

L'essentiel

Imaginez que vous essayez de résoudre un énorme casse-tête (un problème de cryptographie) en utilisant une machine spéciale appelée recuit quantique. Cette machine est très puissante, mais elle a deux limites majeures :

1. Elle ne peut pas tenir un nombre infini de pièces (variables) en même temps.
2. Elle ne supporte pas les pièces qui sont trop lourdes ou trop complexes (coefficients numériques trop grands).

Le but de ce papier est de dire : "Comment on peut réduire la taille de ce casse-tête pour qu'il rentre dans la machine, sans perdre une seule pièce ?"

1. Le Problème : Un Puzzle trop gros

Les algorithmes de sécurité comme AES (qui protège vos mots de passe) ou SHA (qui vérifie l'intégrité des fichiers) sont comme des usines géantes où des milliers de petits calculs logiques (ET, OU, OU exclusif) s'enchaînent.

Pour les résoudre avec un ordinateur quantique, il faut traduire ces usines en un langage spécial appelé QUBO.

• L'ancienne méthode : C'était comme essayer de transporter une maison entière en une seule fois. Le résultat était un "puzzle" gigantesque avec des dizaines de milliers de pièces inutiles. Les machines actuelles ne pouvaient pas le charger.
• Le problème : Plus le puzzle est gros, moins il a de chances d'être résolu par la machine quantique.

2. La Solution : Le "Télescopage" Intelligent

Les auteurs (Gregory Morse et son équipe) ont inventé une nouvelle façon de plier ce puzzle. Au lieu de prendre chaque petit calcul logiquement séparément, ils ont trouvé des modèles réutilisables (des "patrons").

Voici les trois analogies principales de leur méthode :

A. La règle du "Squeeze" (Écraser les racines)

Imaginez que vous devez vérifier si une somme de pièces est comprise entre 10 et 20.

• Méthode classique : Vous créez une case pour chaque nombre possible (10, 11, 12... 20). C'est long et lourd.
• Méthode de l'article : Ils utilisent une astuce mathématique (le "Root Squeezing Theorem") qui ressemble à un sac de compression de couette. Au lieu de créer une case pour chaque nombre, ils créent une seule formule qui "écrase" deux valeurs possibles en une seule variable.
  • Analogie : C'est comme si vous pouviez dire "Si le nombre est pair OU impair, je le mets dans le même tiroir, mais avec une étiquette spéciale". Cela permet de réduire le nombre de tiroirs (variables) de moitié !

B. Les "Étiquettes de Réutilisation" (Substitution Variables)

Dans un grand circuit, on répète souvent les mêmes calculs (par exemple, "A + B").

• Méthode classique : On recalcule "A + B" à chaque fois qu'on en a besoin, comme si on cuisinait un gâteau à chaque fois qu'on voulait une part.
• Méthode de l'article : Ils utilisent des étiquettes (variables de substitution). Une fois qu'ils ont calculé "A + B", ils collent une étiquette dessus. La prochaine fois qu'ils ont besoin de ce résultat, ils utilisent juste l'étiquette.
  • Analogie : C'est comme préparer une sauce en avance et la mettre dans un bocal. Au lieu de mélanger les ingrédients 10 fois, vous utilisez le bocal 10 fois. Cela économise énormément d'ingrédients (variables).

C. Le "Découpage en Blocs" (Pour l'addition)

Pour les additions complexes (comme dans MD5 ou SHA), ajouter des nombres de 32 bits d'un coup crée des coefficients énormes (des poids trop lourds pour la machine).

• Méthode de l'article : Ils découpent l'addition en petits blocs (par exemple, des blocs de 6 bits).
  • Analogie : Au lieu de soulever un bloc de béton de 100 kg d'un coup (ce qui casse la machine), vous le coupez en 20 briques de 5 kg. Vous les transportez une par une, en reliant les briques par des cordes (les bits de retenue). C'est plus léger et plus sûr.

3. Les Résultats : Une Révolution pour la Cryptographie

Grâce à ces astuces, l'équipe a réussi à réduire drastiquement la taille des puzzles pour les algorithmes de sécurité les plus connus :

• AES-256 (le standard de sécurité le plus fort) : Ils ont réduit la taille du problème de plus de 8 fois par rapport aux méthodes précédentes.
  • Avant : Un puzzle de 250 000 pièces.
  • Maintenant : Un puzzle de 30 000 pièces.
• MD5 et SHA : Ils ont également réduit la taille de ces puzzles de milliers de pièces.

4. Pourquoi est-ce important ? (Le Danger et la Promesse)

C'est une épée à double tranchant :

• Le Danger : En rendant ces puzzles beaucoup plus petits, ils deviennent plus faciles à résoudre pour les futurs ordinateurs quantiques. Cela signifie que les méthodes de chiffrement actuelles (AES, SHA) pourraient devenir vulnérables plus tôt que prévu. C'est comme si on avait trouvé un moyen de plier un coffre-fort géant pour qu'il rentre dans un petit camion de déménagement.
• La Promesse : Cela montre aussi que les ordinateurs quantiques sont de plus en plus proches de pouvoir casser ces codes. Cela force les experts à développer de nouvelles protections (cryptographie post-quantique) avant que la technologie ne soit prête.

En résumé

Ces chercheurs ont inventé une nouvelle façon de plier les problèmes mathématiques. Au lieu de les laisser en vrac, ils les ont compressés intelligemment en utilisant des étiquettes réutilisables et des blocs plus petits.

Le résultat ? Ils ont réussi à faire entrer des "monstres" mathématiques (les algorithmes de sécurité) dans des "petites boîtes" (les ordinateurs quantiques actuels), prouvant que la sécurité de nos données numériques pourrait être menacée beaucoup plus vite que prévu par les machines de demain.

Résumé technique

1. Problématique

L'article aborde le défi de la formulation efficace de problèmes d'optimisation combinatoire, en particulier ceux liés à la cryptographie, sous la forme de QUBO (Quadratic Unconstrained Binary Optimization). Le QUBO est crucial pour l'exploitation des recuits quantiques (quantum annealers), des dispositifs capables de trouver le minimum global d'une fonction d'énergie, une propriété essentielle pour casser des algorithmes cryptographiques où les solutions sous-optimales sont inutiles.

Le problème central identifié par les auteurs est l'inefficacité des encodages QUBO existants pour les formules logiques complexes (comme les fonctions de hachage MD5, SHA ou les chiffrements AES). Les méthodes traditionnelles, souvent basées sur des transformations Tseitin vers la forme normale conjonctive (CNF), entraînent une explosion du nombre de variables binaires et une densité élevée de la matrice QUBO. Cela dépasse rapidement les capacités des machines quantiques actuelles et futures (qui gèrent environ 30 000 variables logiques). De plus, les coefficients de la matrice QUBO peuvent devenir trop grands pour la précision numérique limitée du matériel.

2. Méthodologie

Les auteurs proposent une approche systématique pour générer des encodages QUBO compacts en minimisant le nombre de variables de substitution (ancillary variables) nécessaires.

• Approche par Programmation Linéaire en Nombres Entiers (ILP) :
  La méthode fondamentale repose sur la résolution d'un problème ILP pour trouver les coefficients optimaux d'une fonction quadratique $g(x, s)$. L'objectif est de définir une fonction qui vaut 0 pour les termes minimaux (min-terms) valides du problème logique original et strictement supérieure à 0 pour tous les autres cas. Cette approche permet de découvrir des motifs d'encodage réutilisables plutôt que de simplement résoudre le problème logique.

• Théorème de « Root Squeezing » (Compression de Racines) :
  Un résultat théorique clé est le Root Squeezing Theorem. Il démontre que pour encoder des contraintes de plage (par exemple, $L \le \sum x_i \le H$), on peut utiliser le produit de deux fonctions linéaires $g(X)h(X)$ dont les racines sont distantes d'au plus 1. Cela permet de couvrir une plage de valeurs avec un nombre de variables de substitution réduit d'un bit par rapport aux méthodes de carré direct classiques.

• Encodage des Formes Normales (CNF, DNF, ANF) :

  • Parité (XOR) : Utilisation d'une représentation binaire « relâchée » pour les variables de substitution, permettant de couvrir des plages de nombres impairs avec moins de bits.
  • Conjonction (AND) et Disjonction (OR) : Application du théorème de compression de racines pour encoder les clauses multi-entrées avec un nombre minimal de variables supplémentaires.
  • Stratégie de Marqueurs Logiques : Au lieu de réduire tout le circuit cryptographique en CNF (ce qui est inefficace), les auteurs identifient des portes logiques multi-entrées (AND, OR, XOR) et leur attribuent des variables de substitution. Ces variables sont ensuite encodées directement en QUBO en utilisant les motifs optimisés découverts.

• Optimisation de l'Addition Modulaire :
  Pour les fonctions de hachage (MD5, SHA), l'addition modulaire est encodée par blocs (block-wise) pour limiter la magnitude des coefficients dans la matrice QUBO, évitant ainsi les problèmes de précision numérique tout en gérant les retenues (carry bits).

3. Contributions Clés

1. Découverte de Motifs d'Encodage Optimaux : Les auteurs ont généralisé des résultats précédents pour créer des encodages QUBO pour les formes normales ANF, DNF et CNF, réduisant significativement le nombre de variables nécessaires.
2. Réduction Massive des Variables : La méthode permet de réduire le nombre de variables logiques de plusieurs milliers par rapport aux états de l'art précédents.
3. Application à la Cryptographie : La méthodologie a été appliquée avec succès aux algorithmes de chiffrement symétrique (AES-128/192/256) et aux fonctions de hachage (MD5, SHA-1, SHA-256).
4. Gestion de la Complexité des S-Box : Pour AES, les auteurs ont décomposé l'inverse multiplicatif dans le corps fini $GF(2^8)$ en opérations plus simples ($GF(2^4)$ et $GF(2^2)$) et ont utilisé une recherche exhaustive (via ILP) pour trouver les circuits booléens les plus compacts possibles pour ces sous-composantes.

4. Résultats

Les résultats expérimentaux, présentés dans le tableau 3 de l'article, montrent des améliorations spectaculaires par rapport aux travaux antérieurs (notamment [36]) :

• AES-256 : L'encodage proposé ne nécessite que 29 330 variables pour le chiffrement et 31 242 pour le déchiffrement. Cela représente une réduction de plus de 8 fois (soit environ 12 % de la taille) par rapport aux meilleurs résultats précédents (~250 000 variables).
• AES-128/192 : Des réductions similaires sont observées (environ 24 % et 12 % des tailles précédentes respectivement).
• Fonctions de Hachage :
  • MD5 : Réduction à 10 272 variables (contre ~17 280 précédemment).
  • SHA-256 : Réduction à 30 255 variables (contre 47 808 précédemment).
• Sparsité et Coefficients : Les matrices QUBO générées sont très creuses (densité entre 0,04 % et 0,52 %), ce qui est idéal pour l'embedding sur les topologies de recuits quantiques. De plus, la stratégie de blocage permet de maintenir les coefficients à des niveaux gérables (par exemple, 55 pour SHA-256 avec des blocs de taille 1), facilitant l'exécution sur du matériel à précision limitée.

5. Signification et Impact

Ce travail a des implications majeures pour la sécurité informatique et le calcul quantique :

• Vulnérabilité Cryptographique : La réduction drastique de la taille des problèmes QUBO rend les algorithmes cryptographiques standards (comme AES-256) beaucoup plus vulnérables aux attaques par recuit quantique à mesure que ces machines mûrissent. Une machine capable d'encoder 30 000 variables pourrait théoriquement casser un AES-256 avec la méthode proposée, alors qu'elle était auparavant hors de portée.
• Avancement de l'État de l'Art en QUBO : L'article fournit un cadre méthodologique robuste pour convertir des problèmes logiques complexes en QUBO de manière optimale, dépassant les simples transformations Tseitin.
• Guide pour le Matériel Quantique : En démontrant comment gérer les compromis entre le nombre de variables et la magnitude des coefficients, l'article offre des conseils pratiques pour l'implémentation sur du matériel quantique réel, qui souffre souvent de bruit et de limitations de précision.

En conclusion, cette recherche établit un nouveau standard pour l'encodage QUBO, prouvant que des stratégies d'optimisation basées sur l'ILP et des motifs mathématiques spécifiques peuvent rendre des problèmes cryptographiques massifs traitables par les technologies quantiques émergentes.