Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

Cet article présente une architecture de circuit logique quantique détaillée pour l'optimisation de l'addition de points sur des courbes elliptiques sur des corps premiers, atteignant une réduction de 6,5 % à 10 % du nombre de portes Toffoli pour secp256k1 par rapport aux résultats basés sur les preuves à divulgation nulle de connaissance de Babbush et al., tout en n'entraînant qu'une augmentation marginale de 1,5 % de l'utilisation de qubits.

L'essentiel

Imaginez que vous essayez de crocheter une serrure très complexe. Depuis des décennies, les mathématiciens savent qu'un type spécial de « super-clé » (un ordinateur quantique) pourrait ouvrir cette serrure presque instantanément, brisant la sécurité de la majeure partie de l'internet et de son chiffrement. C'est ce qu'on appelle l'Algorithme de Shor.

Cependant, construire cette super-clé est incroyablement coûteux et difficile. Cela nécessite une quantité massive d'« énergie magique » (ressources quantiques) pour fonctionner. L'objectif de cet article est de découvrir comment construire une version plus petite et plus efficace de cette clé.

Voici la décomposition de ce qu'André Schrottenloher a accompli, expliquée à travers des analogies de la vie quotidienne.

1. Le gros problème : Le sac à dos lourd

Imaginez que courir l'algorithme de Shor ressemble à une randonnée en montagne. Pour atteindre le sommet (craquer le code), vous devez porter un sac à dos lourd rempli de fournitures (bits quantiques, ou « qubits »).

• Tentatives précédentes : D'autres chercheurs ont récemment construit un sac à dos très efficace, plus léger que jamais auparavant. Cependant, ils gardaient les plans secrets, utilisant un « tour de magie » (une preuve à divulgation nulle de connaissance) pour convaincre tout le monde que le sac était léger sans montrer comment il était fabriqué.
• L'objectif de cet article : L'auteur voulait construire un sac à dos tout aussi léger que le modèle secret, mais avec des plans entièrement ouverts pour que n'importe qui puisse vérifier le travail.

2. La tâche principale : Ajouter des points sur une courbe

La tâche principale de l'algorithme est d'effectuer une opération mathématique spécifique appelée « addition de points » sur une courbe elliptique.

• L'analogie : Imaginez que vous marchez sur un trampoline géant et incurvé. Vous devez sauter d'un endroit à un autre en suivant un ensemble de règles. Réaliser ce saut parfaitement est difficile.
• Le goulot d'étranglement : La partie la plus difficile du saut est un mouvement spécifique appelé « multiplication en place ». C'est comme essayer de multiplier deux nombres ensemble alors que vous n'avez le droit d'utiliser que l'espace sur lequel vous vous trouvez actuellement, sans aucun espace supplémentaire pour écrire vos brouillons.

3. La solution : La « danse en deux étapes »

Pour résoudre ce problème de « manque de papier brouillon », l'auteur a utilisé une stratégie astucieuse en deux étapes (basée sur une méthode appelée l'Algorithme d'Euclide Étendu) :

• Étape 1 : Le ruban de mémoire (Enregistrer les mouvements)
  Au lieu de faire le calcul et de garder le résultat, l'ordinateur enregistre d'abord quels mouvements il aurait faits sur un long ruban de bits. Il ne fait pas encore le gros du travail ; il écrit simplement les instructions. Ce ruban est étonnamment court.
• Étape 2 : La reconstruction (Jouer les mouvements)
  Une fois le ruban écrit, l'ordinateur le joue en sens inverse. Il utilise les instructions sur le ruban pour effectuer le calcul réel sur les nombres.
• Pourquoi cela aide : En séparant la « planification » de l'« exécution », l'ordinateur économise énormément d'espace. C'est comme écrire une recette sur un post-it avant de commencer à cuisiner, afin de ne pas avoir à tenir tous les ingrédients dans vos mains en même temps.

4. Le raccourci : Le nombre premier « Pseudo-Mersenne »

L'article se concentre sur un type de serrure spécifique appelé secp256k1 (utilisé par Bitcoin). Cette serrure a une forme spéciale.

• L'analogie : Imaginez qu'une serrure générique est un carré parfait. Mais la serrure Bitcoin est un carré avec un petit coin coupé.
• L'optimisation : Parce que le coin est coupé, le calcul nécessaire pour ouvrir la serrure est légèrement plus facile. L'auteur a conçu des outils spéciaux qui tirent parti de ce « coin coupé » pour sauter des étapes inutiles.
  • Pour une serrure générique (n'importe quel nombre premier), les outils sont standards et légèrement plus lourds.
  • Pour la serrure Bitcoin (secp256k1), les outils sont rationalisés et plus légers car ils savent exactement où se trouve le coin manquant.

5. Les résultats : Un sac à dos légèrement plus léger

L'auteur a construit le plan complet de ce nouveau sac à dos et l'a testé.

• Espace (Qubits) : Le nouveau sac à dos est environ 1,5 % plus lourd que le modèle secret des autres chercheurs. C'est un compromis minime.
• Énergie (Portes) : Cependant, le nouveau sac à dos est de 6,5 % à 10 % plus efficace en termes d'énergie (portes Toffoli) nécessaire pour le faire fonctionner.
• Fiabilité : L'auteur a prouvé que ce sac à dos fonctionne aussi de manière fiable que le modèle secret. Si vous l'utilisez sur des entrées aléatoires, il réussit presque à chaque fois, tout comme la version secrète.

Résumé

En termes simples, cet article dit : « Nous avons trouvé comment construire l'ordinateur quantique nécessaire pour craquer le chiffrement moderne. Nous n'avons pas seulement deviné ; nous avons écrit les instructions exactes. Notre version est légèrement plus grande en taille, mais consomme moins d'énergie pour fonctionner que la version "secrète" précédente, et nous avons prouvé qu'elle fonctionne pour les serrures génériques ainsi que pour la serrure spécifique utilisée par Bitcoin. »

L'auteur souligne qu'il s'agit d'une conception logique (le plan théorique). Cela ne signifie pas que nous pouvons le construire aujourd'hui, mais cela nous indique exactement quelle quantité d'« énergie magique » nous aurons besoin lorsque les ordinateurs quantiques seront enfin assez puissants pour tenter l'expérience.

Résumé technique

Énoncé du problème
L'article traite de l'estimation des ressources de l'algorithme de Shor pour le calcul des logarithmes discrets sur courbes elliptiques (ECDL), une menace primaire pour la cryptographie à clé publique actuelle. Bien que des travaux récents de Babbush et al. (arXiv 2026) aient démontré des réductions significatives du nombre de portes et de qubits pour la courbe secp256k1, ils reposaient sur une preuve à divulgation nulle de connaissance (zero-knowledge proof) pour valider leurs résultats sans révéler les circuits quantiques logiques sous-jacents. Ce manque de transparence entrave la reproductibilité et la vérification indépendante. L'article vise à fournir une architecture de circuit quantique logique entièrement détaillée et reproductible qui atteint une efficacité comparable à celle de Babbush et al. tout en révélant explicitement les principes de conception et les détails d'implémentation.

Méthodologie
Les auteurs emploient une approche descendante (top-down), partant de la structure de haut niveau de l'algorithme de Shor et affinant les composants arithmétiques. Le cœur de l'optimisation réside dans l'implémentation de l'addition de points fenêtrée (windowed point addition) sur des courbes elliptiques sur des corps premiers.

1. Structure de haut niveau : L'algorithme utilise une transformée de Fourier semi-classique avec recyclage de qubits pour réduire la multiplication de points $|u, v\rangle|0\rangle \to |u, v\rangle|[u]P + [v]Q\rangle$ en une séquence d'additions de points fenêtrées. Les points sont représentés en coordonnées affines.
2. Multiplication modulaire en place : L'opération la plus coûteuse dans l'addition de points est la multiplication modulaire en place $|x, y\rangle \to |x, yx \pmod q|$. Les auteurs adaptent une technique de [14] qui découple l'algorithme d'Euclide étendu (EEA) en deux phases distinctes :
   • Algorithme d'Euclide (Avant) : Au lieu de calculer directement les coefficients de Bézout, cette phase traite les entrées $(q, x)$ et produit un vecteur de bits « de rebut » (garbage) encodant la séquence d'opérations (swaps, soustractions, divisions par 2). Cela réduit la complexité spatiale.
   • Reconstruction de Bézout (Arrière) : Cette phase prend le vecteur de bits de rebut et applique les opérations enregistrées à une paire $(y, 0)$ pour calculer $|y, yx^{-1} \pmod q\rangle$. En exécutant cela en sens inverse ou avec des entrées spécifiques, les auteurs parviennent à réaliser simultanément la multiplication et l'inversion en place.
3. Optimisation arithmétique :
   • Compromis Espace vs Portes : Les auteurs basculent stratégiquement entre l'additionneur CDKM (faible espace) et l'additionneur Gidney (faible nombre de portes, espace plus élevé) selon la disponibilité des qubits ancillaires lors des différentes étapes de l'algorithme.
   • Arithmétique approximative : Pour réduire le nombre de portes, les auteurs introduisent des circuits arithmétiques approximatifs. Les comparaisons sont effectuées en utilisant uniquement les bits les plus significatifs (MSB) plutôt que des comparaisons sur toute la largeur. Cela introduit une probabilité d'échec, qui est gérée en optimisant les constantes pour garantir le succès sur des entrées aléatoires avec une haute probabilité (spécifiquement, probabilité d'échec $\le 2^{-13.3}$).
   • Optimisation spécifique à l'instance : Pour la courbe secp256k1, qui utilise un nombre premier pseudo-Mersenne ($q = 2^{256} - 4294968273$), les circuits de réduction modulaire sont davantage simplifiés. Les auteurs exploitent la faible différence $f$ sous la forme $2^u - f$ pour remplacer les coûteuses soustractions modulaires par des manipulations de bits simples et des additions de $f$.

Principales contributions

• Architecture de circuit reproductible : L'article détaille le premier circuit quantique logique entièrement spécifié pour l'ECDL sur secp256k1 qui correspond aux revendications d'efficacité du travail opaque de Babbush et al. Le code est implémenté et disponible via la bibliothèque Qarton.
• Comptes de ressources optimisés : Les auteurs présentent deux variantes du circuit :
  • Optimisée pour l'espace : Utilise environ $4.36n + O(\sqrt{n})$ qubits.
  • Optimisée pour les portes : Utilise environ $4.36n + O(\sqrt{n})$ qubits mais réduit le nombre de portes Toffoli.
• Variante générique : Une version du circuit est fournie qui est valide pour n'importe quel corps premier, pas seulement pour secp256k1, bien qu'elle incurre un coût de portes légèrement plus élevé en raison de l'absence d'optimisations pseudo-Mersenne.
• Analyse détaillée des coûts : L'article fournit une décomposition granulaire des coûts de portes Toffoli, distinguant la construction du GCD, la reconstruction de Bézout et les composants d'arithmétique modulaire.

Résultats
Les auteurs rapportent les estimations de ressources suivantes pour la courbe secp256k1 (où $n=256$) :

• Nombre de qubits :
  • Variante optimisée pour l'espace : 1 192 qubits (comparé à 1 175 pour Babbush et al.).
  • Variante optimisée pour les portes : 1 446 qubits (comparé à 1 425 pour Babbush et al.).
  • Cela représente une légère augmentation d'environ 1,5 % du nombre de qubits.
• Nombre de portes (Toffolis) :
  • Variante optimisée pour l'espace : $2^{21.19}$ (environ $2,3 \times 10^6$).
  • Variante optimisée pour les portes : $2^{20.83}$ (environ $1,8 \times 10^6$).
  • Cela représente une réduction de 6,5 % à 10 % du nombre de portes Toffoli par rapport à Babbush et al.
• Coût de l'algorithme complet : Pour l'algorithme de Shor complet sur secp256k1, la variante optimisée pour les portes nécessite environ $2^{25.78}$ portes Toffoli et 1 462 qubits. C'est une amélioration significative par rapport aux travaux précédents de Litinski (arXiv 2023), qui nécessitaient environ $2^{27.57}$ portes Toffoli et le double du nombre de qubits.

Signification
L'article revendique sa signification principalement dans le domaine de la reproductibilité et de la transparence. En fournissant l'architecture explicite du circuit logique, les auteurs permettent à la communauté cryptographique de vérifier les estimations de ressources pour briser la cryptographie sur courbes elliptiques, qui étaient auparavant cachées derrière une preuve à divulgation nulle de connaissance. Le travail démontre qu'une efficacité similaire ou légèrement améliorée peut être obtenue grâce à des choix de conception explicites, spécifiquement la séparation de l'EEA en une phase d'enregistrement et une phase de reconstruction, combinée à l'arithmétique approximative. Les auteurs notent que leurs circuits ne sont pas exacts et reposent sur une haute probabilité de succès sur des entrées aléatoires, une propriété partagée avec le travail qu'ils répliquent. Les résultats confirment que le coût pour briser secp256k1 est inférieur à ce qui avait été estimé précédemment par certains modèles de circuits logiques, renforçant l'urgence de la migration post-quantique.