Le dernier e-mail que vous avez envoyé a probablement été crypté grâce à une méthode éprouvée, basée sur l’idée que même l’ordinateur le plus rapide ne pourrait pas efficacement décomposer un nombre gigantesque en facteurs.
En revanche, les ordinateurs quantiques promettent de déchiffrer rapidement des systèmes cryptographiques complexes qu’un ordinateur classique ne pourrait jamais résoudre. Cette promesse repose sur un algorithme de factorisation quantique proposé en 1994 par Peter Shor, aujourd’hui professeur au MIT.
Malgré les progrès significatifs réalisés au cours des 30 dernières années, un ordinateur quantique suffisamment puissant pour exécuter l’algorithme de Shor n’a pas encore été construit.
Alors que certains chercheurs s’efforcent de construire des ordinateurs quantiques plus grands, d’autres cherchent à améliorer l’algorithme de Shor pour qu’il fonctionne 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 nécessiterait plus de mémoire.
En s’appuyant sur ces résultats, des chercheurs du MIT ont proposé une approche combinant la vitesse de l’algorithme de Regev et l’efficacité mémoire de celui de Shor. Ce nouvel algorithme est aussi rapide que celui de Regev, nécessite moins de qubits (les blocs de construction quantiques) et présente une tolérance plus élevée au bruit quantique, rendant sa mise en œuvre plus pratique.
À long terme, ce nouvel algorithme pourrait influencer le développement de nouvelles méthodes de cryptage capables de résister aux capacités de décryptage des ordinateurs quantiques.
« Si un jour des ordinateurs quantiques à grande échelle sont construits, alors la factorisation sera compromise et nous devrons trouver d’autres méthodes pour la cryptographie. Mais quelle est la réalité de cette menace ? 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 à la Fondation Ford, membre du Laboratoire d’informatique et d’intelligence artificielle (CSAIL) et auteur principal d’une étude. article décrivant l’algorithme.
L’auteur principal de l’article est Seyoon Ragavan, étudiant diplômé du département de génie électrique et d’informatique du MIT. La recherche sera présentée lors de la Conférence internationale de cryptologie 2024.
Décrypter la cryptographie
Pour transmettre des messages en toute sécurité sur Internet, les fournisseurs de services comme les clients de messagerie et les applications de messagerie utilisent généralement RSA, un schéma de cryptage 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 de 617 chiffres) est trop difficile à réaliser pour un ordinateur dans un laps de temps raisonnable.
Cette idée a été bouleversée en 1994 lorsque Shor, alors aux Bell Labs, a introduit un algorithme prouvant qu’un ordinateur quantique pouvait factoriser assez rapidement pour briser la cryptographie RSA.
« Cela a été un tournant. Mais en 1994, personne ne savait comment construire un ordinateur quantique suffisamment grand. Et nous en sommes encore loin. Certaines personnes se demandent même 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. Actuellement, les plus grands ordinateurs quantiques possèdent 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 utilisent des qubits, les plus petits éléments constitutifs d’un ordinateur quantique, pour effectuer des calculs.
Mais les portes quantiques introduisent du bruit, donc avoir moins de portes améliorerait les performances d’une machine. Les chercheurs se sont efforcés d’améliorer l’algorithme de Shor pour qu’il puisse être exécuté sur un circuit plus petit avec moins de portes quantiques.
C’est précisément ce qu’a fait Regev 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 pris en compte. Cela signifie que si l’on factorisait 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 gardez, ils se détériorent avec le temps. Vous souhaitez 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 discours, 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 abordé cette question.
Ping-pong quantique
Pour factoriser un très grand nombre, un circuit quantique devrait s’exécuter plusieurs fois, effectuant des opérations impliquant des puissances de calcul, comme 2 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é, davantage de mémoire quantique doit être ajoutée pour calculer le carré suivant.
Les chercheurs du MIT ont trouvé un moyen astucieux de calculer les exposants en utilisant une série de nombres de Fibonacci qui nécessitent une simple multiplication, réversible, plutôt que la mise au carré. Leur méthode n’a besoin que de deux unités de mémoire quantique pour calculer n’importe quel exposant.
« C’est un peu comme un jeu de ping-pong, où nous commençons avec un nombre, puis rebondissons, 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 irréalisables sur une vraie machine.
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 nettement plus économe en mémoire. De plus, leur technique de correction d’erreurs rendrait l’algorithme plus pratique à déployer.
« Les auteurs résolvent les deux goulots d’étranglement les plus importants du précédent algorithme de factorisation quantique. Bien qu’ils ne soient pas encore immédiatement pratiques, leurs travaux rapprochent 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 après ce travail est la suivante : cela nous rapproche-t-il réellement de la rupture de la cryptographie RSA ? Ce n’est pas encore clair ; ces améliorations n’interviennent 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 des entiers de 2 048 bits ? » dit Ragavan.
Ce travail est financé par une bourse présidentielle d’Akamai, la US Defense Advanced Research Projects Agency, la National Science Foundation, le MIT-IBM Watson AI Lab, une bourse d’innovation en recherche de la faculté de la famille Thornton et un prix d’investigateur Simons.
