Les Scientifiques Quantiques Ont Construit une Nouvelle Mathématique de la Cryptographie
Les problèmes complexes ne sont généralement pas les bienvenus. Mais les cryptographes les adorent. En effet, certaines équations mathématiques difficiles sous-tendent la sécurité du chiffrement moderne. Toute astuce ingénieuse pour les résoudre pourrait anéantir la plupart des formes de cryptographie. Il y a quelques années, des chercheurs ont découvert une approche radicalement nouvelle du chiffrement, éliminant cette faille potentielle. Cette méthode exploite les particularités de la physique quantique. Contrairement aux anciens schémas de chiffrement quantique, limités à quelques tâches spécifiques, cette nouvelle approche couvre un éventail bien plus large d’applications. Elle pourrait même fonctionner si tous les problèmes au cœur de la cryptographie « classique » s’avéraient facilement solubles.
Cependant, cette découverte reposait sur des hypothèses irréalistes. « C’était plutôt une preuve de concept », explique Fermi Ma, chercheur en cryptographie à l’Institut Simons pour la Théorie du Calcul à Berkeley, en Californie. « Cela ne reflète pas la réalité. » Aujourd’hui, un nouvel article rédigé par deux cryptographes ouvre la voie à une cryptographie quantique sans ces hypothèses farfelues. « Cet article démontre que si certaines autres conjectures sont vraies, alors la cryptographie quantique doit exister », affirme Ma.
Imaginez la cryptographie moderne comme une tour composée de trois éléments essentiels. Le premier est la fondation profonde, constituée de problèmes mathématiques ardus. La tour elle-même représente le deuxième élément, abritant des protocoles cryptographiques spécifiques permettant d’envoyer des messages privés, de signer des documents numériques, ou encore de voter secrètement. Entre les deux se trouve une base faite de blocs appelés fonctions à sens unique, assurant l’asymétrie inhérente à tout schéma de chiffrement. « C’est à sens unique parce que vous pouvez chiffrer des messages, mais pas les déchiffrer », explique Mark Zhandry, cryptographe chez NTT Research.
Dans les années 1980, des chercheurs ont prouvé que la cryptographie reposant sur des fonctions à sens unique garantirait la sécurité pour de nombreuses tâches. Mais des décennies plus tard, ils ne sont toujours pas certains que cette fondation soit assez solide. Le problème vient du fait que cette base repose sur des problèmes NP, dont la particularité est qu’il est facile de vérifier si une solution proposée est correcte. Bien que ces problèmes semblent intrinsèquement difficiles, les informaticiens n’ont pas pu le prouver. Si quelqu’un découvrait un algorithme ingénieux pour résoudre rapidement les problèmes NP les plus complexes, toute la tour s’effondrerait.
Malheureusement, il est impossible de déplacer cette tour ailleurs. La fondation – les fonctions à sens unique – ne peut reposer que sur des problèmes NP. Pour construire une tour sur des problèmes plus ardus, les cryptographes auraient besoin d’une nouvelle fondation. Cela semblait impossible jusqu’à il y a quelques années, lorsque des chercheurs ont réalisé que la physique quantique pouvait aider. Tout a commencé avec un article publié en 2021 par un étudiant nommé William Kretschmer, qui a attiré l’attention sur un problème étrange concernant les propriétés des systèmes quantiques. Les chercheurs ont rapidement montré que ce problème pouvait remplacer les fonctions à sens unique comme fondation d’une nouvelle tour de protocoles cryptographiques.
L’année suivante, Kretschmer et d’autres ont prouvé que cette approche alternative pouvait fonctionner même sans problèmes NP difficiles. Soudain, il semblait possible de construire une forteresse cryptographique bien plus robuste. Mais où la bâtir ? Le problème quantique utilisé par Kretschmer impliquait des dispositifs hypothétiques appelés oracles, capables de répondre instantanément à des questions spécifiques. Les oracles sont utiles en théorie, mais n’existent pas en réalité. Les preuves de Kretschmer ressemblaient à un plan pour construire un château dans les airs. Comment le ramener sur terre ?
À l’automne 2022, cette question a attiré l’attention de Dakshita Khurana, cryptographe à l’Université de l’Illinois à Urbana-Champaign et chez NTT Research. Khurana et son étudiant Kabir Tomer se sont lancés dans la construction d’une nouvelle tour cryptographique. Leur première étape a été de créer une nouvelle fondation utilisant des blocs quantiques au lieu de fonctions classiques à sens unique. Ils ont ensuite dû prouver que cette fondation pouvait soutenir une tour d’autres protocoles cryptographiques. Une fois cela établi, il leur restait à trouver un socle solide – des problèmes du monde réel encore plus difficiles que les problèmes NP utilisés en cryptographie classique.
