Des chercheurs proposent un circuit de factorisation quantique plus petit et plus tolérant au bruit pour la cryptographie

Le dernier e-mail que vous avez envoyé a probablement été chiffré à l’aide d’une méthode éprouvée qui repose sur l’idée que même l’ordinateur le plus rapide serait incapable de décomposer efficacement un nombre gigantesque en facteurs.

Les ordinateurs quantiques, eux, promettent de déchiffrer rapidement des systèmes cryptographiques complexes qu’un ordinateur classique ne serait peut-être jamais capable de déchiffrer. Cette promesse repose sur un algorithme de factorisation quantique proposé en 1994 par Peter Shor, aujourd’hui professeur au MIT.

Mais même si les chercheurs ont fait de grands progrès au cours des 30 dernières années, les scientifiques n’ont pas encore construit un ordinateur quantique suffisamment puissant pour exécuter l’algorithme de Shor.

Alors que certains chercheurs s’efforcent de construire des ordinateurs quantiques plus grands, d’autres tentent d’améliorer l’algorithme de Shor afin qu’il puisse fonctionner sur un circuit quantique plus petit. Il y a environ un an, Oded Regev, informaticien à l’Université de New York, a proposé une amélioration théorique majeure. Son algorithme pourrait fonctionner plus rapidement, mais le circuit nécessiterait davantage de mémoire.

S’appuyant sur ces résultats, les chercheurs du MIT ont proposé une approche qui combine la vitesse de l’algorithme de Regev avec l’efficacité mémoire de celui de Shor. Ce nouvel algorithme est aussi rapide que celui de Regev, nécessite moins de blocs de construction quantiques appelés qubits et présente une plus grande tolérance au bruit quantique, ce qui pourrait le rendre plus facile à mettre en œuvre dans la pratique.

À long terme, ce nouvel algorithme pourrait éclairer le développement de nouvelles méthodes de cryptage capables de résister à la puissance de décryptage des codes des ordinateurs quantiques.

« Si des ordinateurs quantiques à grande échelle sont construits un jour, la factorisation sera alors une utopie et nous devrons trouver un autre moyen d’utiliser la cryptographie. Mais cette menace est-elle réelle ? Pouvons-nous rendre la factorisation quantique pratique ? »

« Notre travail pourrait potentiellement nous rapprocher d’une mise en œuvre pratique », déclare Vinod Vaikuntanathan, professeur d’ingénierie de la Fondation Ford, membre du Laboratoire d’informatique et d’intelligence artificielle (CSAIL) et auteur principal d’un article décrivant l’algorithme.

L’auteur principal de l’étude est Seyoon Ragavan, étudiant diplômé du département de génie électrique et d’informatique du MIT. La recherche a été présentée lors de la Conférence internationale sur la cryptologie 2024 (Crypto 2024).

Décryptage de la cryptographie

Pour transmettre des messages en toute sécurité sur Internet, les fournisseurs de services tels que les clients de messagerie et les applications de messagerie s’appuient généralement sur RSA, un système de chiffrement inventé par les chercheurs du MIT Ron Rivest, Adi Shamir et Leonard Adleman dans les années 1970 (d’où le nom « RSA »). Le système repose sur l’idée que la factorisation d’un entier de 2 048 bits (un nombre à 617 chiffres) est trop difficile à réaliser pour un ordinateur dans un délai raisonnable.

Cette idée a été bouleversée en 1994 lorsque Shor, alors employé chez Bell Labs, a introduit un algorithme qui a prouvé qu’un ordinateur quantique pouvait factoriser suffisamment rapidement pour casser la cryptographie RSA.

« Ce fut un tournant. Mais en 1994, personne ne savait comment construire un ordinateur quantique suffisamment grand. Et nous en sommes encore assez loin. Certains se demandent s’ils seront un jour construits », explique Vaikuntanathan.

On estime qu’un ordinateur quantique aurait besoin d’environ 20 millions de qubits pour exécuter l’algorithme de Shor. À l’heure actuelle, les plus grands ordinateurs quantiques disposent d’environ 1 100 qubits.

Un ordinateur quantique effectue des calculs à l’aide de circuits quantiques, tout comme un ordinateur classique utilise des circuits classiques. Chaque circuit quantique est composé d’une série d’opérations appelées portes quantiques. Ces portes quantiques utilisent des qubits, qui sont les plus petits éléments constitutifs d’un ordinateur quantique, pour effectuer des calculs.

Mais les portes quantiques introduisent du bruit, et un nombre réduit de portes permettrait d’améliorer les performances d’une machine. Les chercheurs se sont efforcés d’améliorer l’algorithme de Shor afin qu’il puisse être exécuté sur un circuit plus petit avec moins de portes quantiques.

C’est exactement ce que Regev a fait avec le circuit qu’il a proposé il y a un an.

« C’était une grande nouvelle car c’était la première véritable amélioration du circuit de Shor depuis 1994 », explique Vaikuntanathan.

Le circuit quantique proposé par Shor a une taille proportionnelle au carré du nombre à factoriser. Cela signifie que si l’on devait factoriser un entier de 2 048 bits, le circuit aurait besoin de millions de portes.

Le circuit de Regev nécessite beaucoup moins de portes quantiques, mais il a besoin de beaucoup plus de qubits pour fournir suffisamment de mémoire. Cela pose un nouveau problème.

« Dans un sens, certains types de qubits sont comme des pommes ou des oranges. Si vous les conservez, ils se dégradent avec le temps. Il faut donc minimiser le nombre de qubits que vous devez conserver », explique Vaikuntanathan.

Il a entendu Regev parler de ses résultats lors d’un atelier en août dernier. À la fin de son exposé, Regev a posé une question : quelqu’un pourrait-il améliorer son circuit pour qu’il nécessite moins de qubits ? Vaikuntanathan et Ragavan ont répondu à cette question.

Ping-pong quantique

Pour factoriser un très grand nombre, un circuit quantique devrait s’exécuter de nombreuses fois, effectuant des opérations impliquant des puissances de calcul, comme 2 à la puissance 100.

Mais calculer des puissances aussi importantes est coûteux et difficile à réaliser sur un ordinateur quantique, car les ordinateurs quantiques ne peuvent effectuer que des opérations réversibles. La mise au carré d’un nombre n’est pas une opération réversible, donc chaque fois qu’un nombre est mis au carré, il faut ajouter de la mémoire quantique pour calculer le carré suivant.

Les chercheurs du MIT ont trouvé une méthode astucieuse pour calculer les exposants à l’aide d’une série de nombres de Fibonacci qui nécessite une simple multiplication, réversible, plutôt qu’une mise au carré. Leur méthode ne nécessite que deux unités de mémoire quantique pour calculer un exposant.

« C’est un peu comme un jeu de ping-pong, où nous commençons avec un nombre, puis nous rebondissons d’avant en arrière, en multipliant entre deux registres de mémoire quantique », ajoute Vaikuntanathan.

Ils ont également relevé le défi de la correction des erreurs. Les circuits proposés par Shor et Regev nécessitent que chaque opération quantique soit correcte pour que leur algorithme fonctionne, explique Vaikuntanathan. Mais des portes quantiques sans erreur seraient impossibles sur une machine réelle.

Ils ont surmonté ce problème en utilisant une technique permettant de filtrer les résultats corrompus et de traiter uniquement les bons.

Le résultat final est un circuit qui utilise beaucoup moins de mémoire. De plus, leur technique de correction d’erreur rendrait l’algorithme plus pratique à déployer.

« Les auteurs résolvent les deux principaux problèmes rencontrés dans l’algorithme de factorisation quantique. Bien que leur travail ne soit pas encore immédiatement applicable, il rapproche les algorithmes de factorisation quantique de la réalité », ajoute Regev.

À l’avenir, les chercheurs espèrent rendre leur algorithme encore plus efficace et, un jour, l’utiliser pour tester la factorisation sur un véritable circuit quantique.

« La question qui se pose avec ce travail est la suivante : est-ce que cela nous rapprochera réellement de la rupture de la cryptographie RSA ? Ce n’est pas encore clair ; ces améliorations ne se produisent actuellement que lorsque les entiers sont bien supérieurs à 2 048 bits. Pouvons-nous pousser cet algorithme et le rendre plus réalisable que celui de Shor, même pour les entiers de 2 048 bits ? » demande Ragavan.

Cet article est republié avec l’aimable autorisation de MIT News (web.mit.edu/newsoffice/), un site populaire qui couvre l’actualité de la recherche, de l’innovation et de l’enseignement au MIT.