Panique chez les cryptologues post-quantiques

Mercredi 10 avril 2024. Yilei Chen, chercheur à l’université Tsinghua, en Chine, met en ligne un article qui, en quelques jours à peine, fait le tour du monde. “Algorithmes quantiques pour les problèmes de réseau”, annonce le titre. La première phrase de l’abstract précise : “Nous présentons un algorithme quantique en temps polynomial pour résoudre le problème de l’apprentissage avec erreurs (LWE).” Si, pour le commun des mortels, cette annonce ressemble à une énième phrase obscure écrite par un spécialiste sur un sujet pointu, pour la communauté mondiale de la cryptographie, c’est une tout autre histoire : une véritable alerte tsunami

J’ai carrément reçu un message disant que la cryptographie post-quantique était morte !

“Je vous le confirme, quand le papier a été mis en ligne, on a tous paniqué. On ne parlait presque plus que de ça, au travail.” “Vu les courriels qui ont circulé dans la mailing list du NIST, j’ai l’impression qu’ils n’étaient pas très sereins…” “La mise en ligne d’un papier comme ça, forcément, ça inquiète – et à raison, je pense.” “Ça a jeté toutes sortes de doutes : j’ai carrément reçu un message disant que la cryptographie post-quantique était morte !” La panique a duré quinze jours… le temps que l’article soit étudié, et qu’une erreur soit détectée dans la démonstration, invalidant le résultat. 

Fausse alerte

Car oui, l’article ne tient pas : c’était une fausse alerte. Les chercheuses et les chercheurs, pourtant, continuent d’en parler. Contrairement à l’usage ils bravent leur réticence à évoquer un article dont le contenu a finalement été réfuté. Il n’y a que l’auteur lui-même qui refuse poliment notre demande d’interview : “J’aurais accepté avec plaisir d’échanger avec vous si mon papier avait été correct. Mais comme vous le savez, une erreur a été trouvée, et la situation [de la cryptographie] n’a donc pas changé. Pour l’heure, je travaille à essayer de réparer l’erreur, donc je préfère ne pas parler de ce papier dans une interview.” 

Mais la secousse a été si violente que les cryptologues ne se font pas prier pour revenir sur l’événement. Et tous semblent reconnaître que quelque chose, durant ces deux semaines de panique, s’est cristallisé : même si l’épisode s’est terminé par un soulagement, il est révélateur des grands doutes qui planent au-dessus de ce champ de recherche très actif qu’est la cryptographie post-quantique. 

La cryptographie, c’est la science de la protection des données. Notamment à travers le chiffrement, c’est-à-dire le développement de méthodes permettant à l’auteur d’un message de le transformer, de sorte que seul son destinataire soit en mesure de le lire – si une tierce personne accède au message chiffré pendant son transfert entre émetteur et destinataire, elle ne doit pas être capable de le comprendre. De Jules César à Alan Turing, l’histoire a démontré l’importance cruciale de ces protocoles. 

Tout tient à un fil

En pratique, pour chiffrer un message, ou plus généralement sécuriser des données numériques, on utilise des opérations mathématiques faciles à faire dans un sens, mais difficiles à inverser. Autrement dit, des problèmes faciles à construire, mais difficiles à résoudre. L’exemple archétypal, c’est la factorisation : c’est simple de multiplier deux très grands nombres premiers, mais retrouver les deux facteurs à partir d’un produit est extrêmement fastidieux – et donc long, même pour un ordinateur. C’est sur cette difficulté que repose le célèbre protocole de chiffrement RSA, largement utilisé aujourd’hui pour sécuriser la navigation sur Internet ou les échanges bancaires. “On ramène la sécurité du chiffrement à la difficulté du problème sous-jacent”, résume Alice Pellet-Mary, chercheuse en cryptographie à l’université de Bordeaux.

Seulement voilà : il est difficile d’affirmer qu’un problème est vraiment difficile. C’est même impossible à démontrer. Tout un champ de la cryptographie, appelé la cryptanalyse, s’attache d’ailleurs à essayer de trouver des méthodes capables de résoudre rapidement les problèmes sur lesquels sont construits les protocoles de chiffrement. Autrement dit, tout tient à un fil : un problème est considéré comme difficile si cela fait longtemps que les cryptanalystes essaient de trouver une méthode efficace de résolution, sans y parvenir. En pratique, la cryptographie moderne repose donc sur la confiance des cryptologues en l’échec des cryptanalystes. “La confiance dans les problèmes est basée sur le temps de recherche et le nombre de personnes qui travaillent dessus”, résume Johanna Loyer, cryptanalyste au Centre de recherche national CWI, à Amsterdam. 

Il y a une structure magnifique dans LWE… En post-quantique, on n’a pas d’alternative aussi puissante !

Or, depuis une trentaine d’années, une perspective bouleverse la discipline : celle de l’arrivée de l’ordinateur quantique. Un ordinateur d’un tout nouveau genre, utilisant les puissantes propriétés de la mécanique quantique pour rendre possibles des calculs inaccessibles aux ordinateurs actuels, ou pour accélérer exponentiellement la vitesse de résolution algorithmique de certains problèmes. Une telle machine n’existe pas encore, et l’on est très loin de disposer d’un consensus sur la date à laquelle elle pourrait véritablement exister – certains experts émettent même des doutes sur le fait qu’elle n’arrivera jamais sur le marché. Reste qu’elle ferait des ravages parmi les protocoles de chiffrement actuels. Dès 1994, le mathématicien américain Peter Shor présentait un algorithme qui, sous réserve de disposer d’un ordinateur quantique pour le faire tourner, permettrait de résoudre le problème de la factorisation de manière extrêmement efficace, mettant ainsi en péril toutes les données sécurisées avec le protocole RSA. De quoi inquiéter tous les banquiers et tous les militaires de la planète…

Un petit jeu

Ainsi est née la cryptographie post-quantique : une sous-discipline qui s’attache à développer des protocoles capables de résister aux attaques d’un hypothétique ordinateur quantique. Avec, d’un côté, des cryptographes quantiques qui recherchent des problèmes “quantum-difficiles” (c’est-à-dire difficiles même pour un ordinateur quantique). Et, de l’autre, des crypt­analystes quantiques qui recherchent les éventuelles failles qu’un ordinateur quantique pourrait exploiter pour résoudre lesdits problèmes. Un petit jeu totalement théorique, mais hautement stratégique et très dynamique – des centaines de chercheurs s’y consacrent à plein temps.

Un petit jeu qui, depuis 2005 et un papier fondateur du chercheur israélo-américain Oded Regev, s’est focalisé sur un problème phare, le LWE, pour Learning With Errors. C’est sur ce problème de “l’apprentissage avec erreurs” que repose une large majorité des protocoles proposés. Celui-là même que Yilei Chen prétendait avoir cassé. “C’est un problème qui a pris une place très, très, très centrale en cryptographie, à la fois en pratique et en théorie, insiste Thomas Vidick, spécialiste de calcul quantique à l’institut Weizmann des sciences, en Israël. Il y a une structure magnifique dans LWE, les gens ont construit des montagnes dessus… Et en post-quantique, on n’a pas d’alternative aussi puissante !” 

La preuve : le NIST, le puissant organisme américain qui sélectionne les protocoles de cryptographie qui ont vocation à être déployés partout, a lancé en 2017 un concours pour faire émerger les futurs standards post-quantiques ; parmi les quatre protocoles sélectionnés en 2022, trois reposent sur LWE.

Le facteur humain joue beaucoup dans la cryptographie, c’est une affaire de confiance

Pourquoi cette quasi-hégémonie ? D’abord à cause de critères techniques, explique Alice Pellet-Mary – comme l’existence d’une “réduction cas moyen – pire cas”, ou encore des liens entre LWE et des problèmes de “recherche d’un sous-groupe caché dans des groupes discrets non commutatifs” réputés difficiles. Mais aussi pour des raisons sociologiques, voire psychologiques. “La cryptographie, c’est une discipline où il n’y a pas que des maths, sourit Gilles Zémor, chercheur à l’Institut de mathématiques de Bordeaux. Il y a un facteur humain qui joue beaucoup. À un moment, la question qui se pose, c’est : est-ce qu’on croit en la difficulté de tel problème, ou non ? C’est une affaire de confiance.” Or, ajoute Alice Pellet-Mary, “LWE, ça fait vingt ans qu’on l’étudie en cryptographie d’un point de vue vraiment algorithmique”. Un recul propre à donner confiance : si l’on n’a rien trouvé en vingt ans de recherche attentive, c’est sans doute que le problème revêt bien une forme de difficulté intrinsèque.

Cacher des failles

Mais dans le même temps, les cryptanalystes post-quantiques ont de sérieux doutes. Car ce problème possède certaines propriétés qui pourraient cacher des failles. “On peut interpréter LWE d’une manière géométrique, avec une structure périodique sous-jacente. Or l’intérêt principal des algorithmes quantiques, c’est qu’ils ont une certaine capacité à découvrir des périodes”, détaille Thomas Vidick. D’autant que les recherches sur LWE ont été majoritairement menées dans un cadre ne prenant pas en compte la possibilité des ordinateurs quantiques. “On a plutôt une bonne confiance dans LWE dans le cadre classique. À l’inverse, je dirais que la croyance générale chez les cryptanalystes est qu’il ne serait pas si surprenant qu’on réussisse à casser LWE avec un algorithme quantique”, résume le chercheur.

Jusqu’à l’étape 9

Alors forcément, quand Yilei Chen, un chercheur reconnu, met en ligne son article, la communauté s’agite. “Tous les six mois, quelqu’un prétend avoir cassé LWE, raconte Johanna Loyer. Mais en général, on détecte très vite des erreurs dans les démonstrations. Ce sont plutôt des papiers qu’on regarde pendant nos pauses, un peu comme des blagues. Or, là, après quelques jours, les meilleurs spécialistes du domaine n’arrivaient pas à contrecarrer le résultat de Chen !” Un groupe de discussion en ligne a été mis sur pied pour tenter de démêler cet article extrêmement dense. Pas moins de quatre cents chercheurs et chercheuses se sont retrouvés à échanger sur le sujet ! “Énormément de gens ont parlé de ce papier, mais très peu ont réussi à rentrer véritablement dedans et à le lire : c’est très technique et difficile”, souligne Thomas Vidick. “J’étais à une grosse conférence de recherche quand le preprint est sorti, confirme Gilles Zémor. J’en ai discuté avec un collègue qui connaît vraiment bien le sujet, et lui-même s’avouait perplexe. Il me racontait : ‘J’en suis à tel endroit dans la lecture de l’article, mais je ne comprends toujours pas où il va, ce qu’il cherche à faire’…”

Si LWE tombe, une énorme partie de la crypto post-quantique actuelle tombe !

Au fil des jours, le résultat est cependant devenu de plus en plus crédible, et la communauté a commencé à être prise de sueurs froides. “Si LWE tombe, une énorme partie de la crypto post-quantique actuelle tombe !”, rappelle Johanna Loyer. “J’ai même eu un appel d’un collègue un peu paniqué, m’expliquant qu’il avait prévu à la rentrée un cours de cryptographie post-quantique et qu’il se posait sérieusement la question de l’annuler”, s’amuse Gilles Zémor. “Après avoir lu les quatre premières étapes, j’ai pris conscience que c’était une tentative très sérieuse, se souvient Hongxun Wu, chercheur en informatique théorique à l’université de Californie, à Berkeley. Toutes les erreurs identifiées étaient solubles. Jusqu’à l’étape 9.” Le passage fatidique, dans lequel Hongxun Wu et Thomas Vidick identifient tous les deux, de manière indépendante, une erreur non réparable. Ou du moins, dont la résolution nécessiterait un tout nouveau raisonnement, fondamentalement différent de celui proposé dans toute la fin de l’article.

Le ver du doute

Quand on lui demande s’il est optimiste quant à la possibilité de trouver une solution, Yilei Chen répond : “Je suis optimiste de manière générale. Mais les algorithmes quantiques peuvent être piégeux. Aujourd’hui, il m’est donc difficile de dire si oui ou non l’algorithme peut être réparé.” Mais le ver du doute est entré dans le fruit de la crypto. “Avec ce qu’a développé Yilei Chen, je ne serais pas surpris que quelqu’un propose quelque chose de correct dans les années à venir”, estime pour sa part Hongxun Wu. Thomas Vidick, lui, est plus dubitatif : “Moi, je serais plutôt du côté de ceux qui pensent que LWE va tenir la route. Mais en réalité, on ne sait pas. Il faut essayer. »

Pour l’heure, donc, LWE tient bon. Peut-être sera-t-il le grand rempart contre les futures attaques quantiques. Mais il existe un dicton bien connu dans le domaine, qui capture la tension spécifique à ce champ de recherche et qui, après cet épisode, est plus que jamais d’actualité : “Les cryptographes ne dorment pas bien.” À quand la prochaine terreur nocturne ?