Alice & Bob estime que RSA-2048 pourrait tomber avec environ 23 000 cat qubits

Alice & Bob, le développeur d'ordinateurs quantiques à cat qubits basé à Paris et à Boston, a publié le 29 octobre une estimation de ressources selon laquelle une machine tolérante aux fautes construite sur son architecture pourrait factoriser une clé RSA de 2048 bits avec 22 593 qubits physiques en 3,14 jours. L'entreprise présente ce résultat comme un nouveau plancher pour les ressources quantiques totales, mesurées en qubits multipliés par la durée d'exécution, nécessaires pour exécuter l'algorithme de Shor contre le chiffrement à clé publique actuel. Il s'agit d'une projection théorique publiée sous forme de prépublication, et non d'une démonstration sur du matériel.

Ce qui a été annoncé

Les chiffres proviennent de l'article "Shor's algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days", déposé sur la Cryptology ePrint Archive de l'IACR par une équipe de chercheurs d'Alice & Bob avec un coauteur d'Inria et de l'université de Rennes. Outre RSA-2048, l'équipe estime que le problème du logarithme discret sur courbe elliptique de 256 bits (ECDLP), qui sous-tend les signatures utilisées par Bitcoin et Ethereum, pourrait être résolu avec au plus 29 588 qubits physiques en 61,8 minutes. Elle propose aussi un banc d'essai plus modeste, FFDLP-512, à environ 6 700 qubits et 21 minutes.

Selon l'annonce de l'entreprise, le chiffre obtenu pour RSA nécessite 40 fois moins de qubits physiques que l'estimation de 2025 de Craig Gidney, de Google Quantum AI, qui plaçait RSA-2048 sous le million de qubits bruités pour moins d'une semaine d'exécution sur une machine à code de surface.

Recevez la newsletter de DesignQuantum

Actualités et articles de fond gratuits sur l’informatique quantique, chaque affirmation étant liée à sa source. Quotidienne, hebdomadaire ou mensuelle, au choix.

Website

Adresse e-mail FréquenceQuotidienneHebdomadaireMensuelle LangueEnglishEspañol简体中文हिन्दीالعربيةPortuguês (Brasil)FrançaisDeutsch日本語Русский한국어Bahasa IndonesiaTürkçeItalianoTiếng ViệtPolskiNederlandsไทยفارسیУкраїнськаবাংলাاردوKiswahiliBahasa Melayuעברית M’abonner gratuitement

Gratuit. Désabonnement en un clic à tout moment. Politique de confidentialité

Les détails techniques

Plutôt que de multiplier un nombre de qubits logiques par un surcoût moyen, les auteurs compilent les parties les plus coûteuses de l'algorithme jusqu'aux opérations de chaque qubit physique, avec plans de puce et ordonnancements complets. Alice & Bob attribue les gains à trois ingrédients : des cat qubits qui suppriment les erreurs de basculement de bit (bit-flip) au niveau matériel, de sorte que la correction d'erreurs n'a plus à traiter que les basculements de phase ; les codes LDPC-cat, qui, selon l'entreprise, divisent par plus de deux le nombre de qubits pour RSA-2048 par rapport à son approche antérieure fondée sur un code de répétition (de 49 649 à 22 593) ; et un additionneur reconstruit pour les cat qubits, qui fonctionne à cadence régulière sans attendre la correction d'erreurs. Côté algorithmique, l'équipe s'appuie sur des travaux récents de Google et de chercheurs d'Inria.

Les hypothèses comptent. L'article suppose un cycle de correction d'erreurs de 1 microseconde, un temps de réaction de 10 microsecondes, une probabilité d'erreur de phase de 5 × 10⁻⁴ et aucun basculement de bit, ce qui correspond à un temps de bit-flip d'environ 100 ans. Si les basculements de bit survenaient environ une fois par heure, une couche d'encodage supplémentaire serait nécessaire et l'estimation pour RSA-2048 grimperait à environ 45 000 qubits. La conception permet aussi d'échanger de l'espace contre du temps : environ 611 000 qubits ramèneraient l'exécution de RSA à 1,25 heure, tandis qu'environ 21 188 qubits l'allongeraient à 8,08 jours.

Pourquoi c'est important

Les estimations de ressources pour l'algorithme de Shor ne cessent de baisser à mesure que progressent la correction d'erreurs et la conception d'algorithmes, et chaque baisse resserre l'horizon sur lequel les équipes de sécurité se projettent. Alice & Bob dit s'attendre à ce que les progrès du matériel et la baisse des besoins convergent au début des années 2030, tout en reconnaissant d'importants défis d'ingénierie. Ali El Kaafarani, fondateur et PDG de PQShield, a déclaré dans le communiqué que gouvernements et entreprises devaient « déployer la PQC immédiatement là où c'est le plus critique ».

Ce qu'il faut surveiller

Les chiffres phares reposent sur des cat qubits dotés de temps de bit-flip extrêmement longs, qui n'ont pas encore été démontrés à grande échelle : le véritable test sera donc la progression du matériel vers ces hypothèses. L'évaluation par les pairs de la prépublication et l'examen indépendant de ses choix de compilation seront également à suivre. Alice & Bob indique informer les acteurs publics et industriels et invite les organisations à engager dès maintenant leur migration vers la cryptographie post-quantique, en rappelant que les recommandations américaines et britanniques visent un achèvement d'ici 2035.