Retour

Test expérimental de codes cryptographiques à l'aide de méthodes quantiques adiabatiques

Publié par

Alexandra de Castro

,

14 mars 2024

 

 

Vous êtes-vous déjà demandé comment votre banque protège vos informations personnelles et financières contre les cybercriminels ? Elle utilise des techniques cryptographiques de bout en bout (dans le cas présent, de la banque au client), qui garantissent la protection de la vie privée et la confidentialité, empêchant ainsi le vol ou l'altération de vos données.

À l'ère numérique, où votre téléphone intelligent est votre appareil d'achat, votre carte de crédit, votre messagerie personnelle et professionnelle, la cryptographie est un outil de cybersécurité essentiel. Mais comment fonctionne la cryptographie ? Une méthode très répandue utilise une clé publique et une clé privée. Dans le cas des services bancaires en ligne, par exemple, votre code secret ou votre mot de passe est votre clé privée, et la banque utilise une clé publique pour protéger les données que vous lui envoyez ou qu'elle vous envoie.

La clé publique circule librement sur l'internet parce qu'elle est conçue pour être extrêmement difficile à casser ; et, comme nous le verrons par la suite, la force - et la beauté - d'une conception de clé publique largement utilisée réside dans une astuce mathématique simple : la multiplication de deux grands nombres premiers.

La multiplication de deux grands nombres premiers donne lieu à des nombres énormes, appelés semi-premiers, généralement composés de centaines ou de milliers de chiffres. Le déchiffrement d'une clé basée sur des nombres semi-premiers est un cauchemar, car pour casser de tels codes, il faut trouver les nombres premiers originaux utilisés pour créer la clé. La factorisation des semi-primes est extrêmement inefficace pour les ordinateurs classiques, et c'est pourquoi cette méthode inventée par Ron Rivest, Adi Shamir et Leonard Adleman(RSA) dans les années 70 est encore si largement utilisée. Aujourd'hui, il faut 300 trillions d'années pour casser une clé RSA de 2048 bits! La raison en est que, classiquement, le temps de résolution augmente de façon exponentielle avec le nombre de bits représentant la demi-prime.

Aujourd'hui, vous avez probablement entendu dire que les ordinateurs quantiques seront capables de casser les codes cryptographiques RSA à l'aide d'algorithmes quantiques, tels que celui de Shor, et de voler vos données à votre banque. Du point de vue algorithmique, l'algorithme de Shor devrait résoudre le problème de la factorisation en un temps de calcul polynomial. Cela signifie que l'algorithme de Shor, une fois mis en œuvre sur un ordinateur quantique réel et idéal, pourrait décrypter le même code RSA-2048 en seulement 10 secondes!  

Mais ne perdons pas de vue qu'il n'y a aucune raison de paniquer. La vérité est que les dispositifs quantiques ne sont pas encore assez puissants pour casser les codes du monde réel, et qu'ils ne le seront pas de sitôt. Toutefois, il est essentiel de tester des algorithmes quantiques capables de casser des clés RSA pour prouver qu'un chiffrement est sûr sur le plan quantique et pour déterminer à quel point les méthodes classiques sont obsolètes.

Nouvel algorithme quantique pour tester les codes cryptographiques

Des chercheurs du Korea Advanced Institute of Science and Technology (KAIST), en collaboration avec PASQAL, ont mis au point une nouvelle technique quantique adiabatique pour factoriser les nombres semi-premiers à l'aide de l'informatique quantique à atomes neutres. Dans l'informatique quantique adiabatique, le système évolue progressivement vers une réponse.

L'équipe a réussi à factoriser de petits nombres sur un dispositif quantique à atomes neutres du KAIST, démontrant ainsi le potentiel de leur méthode à remettre en question la cryptographie moderne. L'équipe a récemment publié ses résultats dans la revue Arxiv. Dans ce nouvel article, le professeur Jaewook Ahn du KAIST, Loïc Henriet du PASQAL et leurs collaborateurs examinent le comportement de leur approche pour les grands nombres semi-primes et le nombre d'atomes dont ils auraient besoin. Ils estiment que leur approche, dans des conditions idéales, s'étendrait de manière polynomiale en termes de pas de temps et d'espace mémoire.  

"Nous devions estimer les ressources informatiques pour savoir comment la méthode allait évoluer, car pour nous, un comportement exponentiel avec les ressources informatiques n'est pas acceptable", a déclaré le professeur Jaewook Ahn du KAIST. "Nous avons constaté que le nombre de ressources serait important, mais qu'en principe, la résolution du problème de factorisation à l'aide de notre méthode serait au moins polynomiale.

Manipuler les atomes pour factoriser les nombres

La méthode proposée consiste à traduire le problème de factorisation en un problème de graphe. Un graphe comporte des nœuds, qui représentent des entités, et des arêtes reliant les nœuds, qui représentent la relation entre les entités. Pour factoriser un semi-prime, n = p x q, les candidats aux nombres premiers originaux (p et q) sont traduits en leurs versions binaires et, avec eux, construisent des graphes représentant les nombres binaires avec des nœuds, et les opérations mathématiques entre eux avec les arêtes. Pour trouver la solution, l'algorithme recherche le plus grand ensemble de nœuds qui ne sont pas connectés par des arêtes, appelé l'ensemble indépendant maximal (MIS), en amenant progressivement le système à l'état fondamental de l'énergie.

Parmi les candidats au traitement quantique adiabatique, les architectures à atomes neutres offrent une adaptabilité exceptionnelle pour traiter une grande variété de problèmes basés sur les graphes. Dans ces dispositifs, les atomes sont manipulés à l'aide de réseaux de lasers très focalisés pour créer des réseaux arbitraires 2D ou 3D et un second laser pour manipuler les états électroniques des atomes afin de créer des qubits. Un choix intéressant pour deux états de qubits est constitué par un état fondamental et un état de Rydberg, qui est un état d'énergie électronique très élevé. Un atome dans un état de Rydberg se développe physiquement en influençant les atomes adjacents, les empêchant d'atteindre l'état de Rydberg lorsqu'ils sont plus proches qu'une certaine distance, appelée distance de blocage de Rydberg. L'expérience menée au KAIST s'appuie sur ces deux principales propriétés des technologies quantiques des atomes neutres pour représenter des graphes, où les atomes représentent les nœuds du graphe et où deux atomes qui sont plus proches que leur distance de blocage sont considérés comme reliés par une arête.

Création de réseaux 3D avec des atomes neutres pour résoudre des problèmes basés sur des graphes

Pour résoudre le problème de factorisation, l'équipe a utilisé une approche hybride dans laquelle une partie classique conçoit le graphique représentant le problème et l'ordinateur à atomes neutres est utilisé pour trouver la solution. Grâce à cette méthode, l'équipe a réussi à factoriser les nombres 6 = 2 x 3, 15 = 5x 3 et 35 = 5 x 7 de manière expérimentale.

Alors que pour factoriser le nombre 6 = 2 x 3, les réseaux d'atomes 2D étaient suffisants, les graphiques permettant de factoriser des nombres plus élevés ne sont pas toujours réalisables en 2D. C'est pourquoi l'équipe a dû créer des réseaux d'atomes en 3D avec l'ordinateur quantique du KAIST. Il est essentiel de pouvoir créer des réseaux d'atomes en 3D dans le matériel quantique, non seulement pour casser les codes cryptographiques, mais aussi pour de nombreux autres cas d'utilisation dans le monde réel, tels que la conception de médicaments basée sur la structure moléculaire ou l'analyse du trafic aérien. L'équipe a réussi à créer des réseaux de qubits en 3D pour représenter le problème du graphe et résoudre le problème de factorisation associé pour le nombre 15 = 5 x 3.

"L'agencement des atomes en trois dimensions n'est pas simple, ce n'est pas encore une technique, c'est encore un art. Cependant, si vous calculez l'échelle 2D en fonction du nombre de ressources, vous obtiendrez des chiffres beaucoup plus importants que pour la 3D. Pour que les atomes se connectent efficacement dans le graphique, il faut passer au 3D", a expliqué le professeur Jaewook Ahn.

Dans le cadre de l'émergence des technologies d'atomes neutres, l'équipe du KAIST est l'un des pionniers de la création de réseaux tridimensionnels d'atomes neutres. Avec ce nouveau résultat, les scientifiques du KAIST se positionnent comme l'un des rares à réaliser des réseaux 3D de qubits pour effectuer des calculs de manière efficace.

"En 3D, nous avons pu lever certaines contraintes et disposer plus librement des atomes pour produire les bords du graphe", a déclaré Louis Vignoli, développeur quantique au PASQAL, qui a participé aux travaux. "Cependant, expérimentalement, la 3D est plus difficile à réaliser que la 2D, mais l'équipe coréenne y est parvenue.

Figure 1 - Disposition des atomes en 3D pour factoriser expérimentalement 15 = 3x5. A gauche : Le graphe cible, intégré dans l'espace 3D dans une disposition consistant en 3 couches planes empilées le long de l'axe vertical. À droite : imagerie de fluorescence des 3 plans. Les points brillants sont des atomes. Les nœuds et les arêtes des graphes sont superposés, les lignes en pointillé représentant les arêtes entre les différents plans.

Qu'est-ce qui nous attend pour freiner la cryptographie avec la quantique ?

Bien qu'il faille encore des années pour que l'informatique quantique puisse casser les codes cryptographiques du monde réel, ce résultat expérimental représente un grand pas en avant dans la quête d'algorithmes quantiques promettant d'aider à tester l'obsolescence des méthodes classiques.

"Progresser dans cette direction avec la recherche fondamentale sur le quantique n'est qu'une évolution dans la quête du renforcement de l'ensemble de notre système de sécurité. Le NIST (American Institute of Standards) est déjà en train de publier ses premières normes pour la cryptographie post-quantique précisément pour cette raison, parce qu'il sait que cela se produira [le quantique capable de casser ces codes traditionnels] à un moment donné. Le fait que nous poussions dans cette direction est en fait une force de traction qui incite les gens à aller vers plus de sécurité", a fait remarquer Louis Vignoli.

"Auparavant, les gens considéraient que l'informatique quantique adiabatique était utilisée à des fins spécifiques, mais ce n'est plus le cas aujourd'hui. Nous montrons que nous pouvons programmer un problème général, tel que la factorisation, en utilisant des graphes de conception appropriée. Nous repoussons la limite de l'informatique adiabatique à base d'atomes utilisant des graphes pour devenir une informatique universelle. Nous aurons besoin d'un déploiement de matériel plus important pour pouvoir continuer à travailler dans ce domaine et essayer de factoriser des nombres plus importants. La partie classique de notre algorithme hybride est presque optimale, mais la partie quantique expérimentale peut encore être améliorée. Mais cette fois-ci, nous avons réussi, et ce n'est que le début", a conclu le professeur Jaewook Ahn.

 

Références

Park, K. Jeong, S., Kim, M., Kim, K., Byun,A., Vignoli, L., Henry, L-P., Henriet, L., Ahn, J. (décembre 2023). A Rydberg-atom approach to the integer factorization problem. Disponible sur arXiv : https://arxiv.org/abs/2312.08703

 

Vous souhaitez en savoir plus sur ces techniques sur un ordinateur quantique à atomes neutres ? Commencez votre voyage quantique en utilisant nos plateformes et algorithmes avec Quantum Discovery.

Vous avez des questions sur notre technologie et nos applications ? N'hésitez pas à nous contacter!