Les scientifiques quantiques ont créé une nouvelle mathématique de cryptographie
En théorie, la physique quantique peut contourner les problèmes mathématiques complexes à l'origine du chiffrement moderne. Une nouvelle preuve montre comment.
Les problèmes complexes ne sont généralement pas les bienvenus. Pourtant, les cryptographes les adorent. En effet, certains problèmes mathématiques complexes sont à la base de la sécurité du chiffrement moderne. Toute astuce pour les résoudre condamnerait la plupart des formes de cryptographie.
Il y a plusieurs années, des chercheurs ont découvert une approche de chiffrement radicalement nouvelle , dépourvue de ce point faible potentiel. Cette approche exploite les caractéristiques particulières de la physique quantique. Mais contrairement aux schémas de chiffrement quantique antérieurs, qui ne fonctionnent que pour quelques tâches spécifiques, cette nouvelle approche permet d'accomplir un éventail de tâches beaucoup plus large. Et elle pourrait fonctionner même si tous les problèmes au cœur de la cryptographie " classique " ordinaire s'avéraient facile à résoudre.
Mais cette découverte remarquable reposait sur des hypothèses irréalistes. Le résultat était " plutôt une démonstration conceptuelle ", a déclaré Fermi Ma, chercheur en cryptographie à l'Institut Simons pour la théorie de l'informatique à Berkeley, en Californie. " Ce n'est pas une affirmation concernant le monde réel. "
Maintenant, un nouvelle étude réalisée par deux cryptographes a ouvert la voie à la cryptographie quantique, débarrassée de ces hypothèses farfelues. " Cet article affirme que si certaines autres conjectures sont vraies, alors la cryptographie quantique doit être possible ", a déclaré Ma.
Le Château dans le ciel
On peut comparer la cryptographie moderne à une tour composée de trois parties essentielles. La première partie est le socle rocheux situé en profondeur sous la tour, constitué de problèmes mathématiques complexes. La tour elle-même constitue la deuxième partie : on y trouve des protocoles cryptographiques spécifiques permettant d'envoyer des messages privés, de signer des documents numériques, de voter à bulletin secret, et bien plus encore.
Entre les deux, la sécurisation de ces applications quotidiennes sur un socle mathématique repose sur des blocs de construction appelés fonctions unidirectionnelles . Elles sont responsables de l'asymétrie inhérente à tout schéma de chiffrement. " C'est unidirectionnel, car on peut chiffrer les 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 basée sur des fonctions unidirectionnelles garantissait la sécurité de nombreuses tâches. Mais des décennies plus tard, ils ne sont toujours pas certains que le socle soit suffisamment solide pour le supporter. Le problème est que ce socle est constitué de problèmes difficiles spécifiques – techniquement appelés problèmes NP – dont la caractéristique principale est qu'il est facile de vérifier si une solution candidate est correcte. (Par exemple, décomposer un nombre en ses facteurs premiers est un problème NP : difficile à réaliser pour les grands nombres, mais facile à vérifier.)
Beaucoup de ces problèmes semblent intrinsèquement difficiles, mais les informaticiens n'ont pas réussi à le prouver. Si quelqu'un découvre un algorithme ingénieux pour résoudre rapidement les problèmes NP les plus complexes, le socle s'effondrera et la tour entière s'effondrera.
Malheureusement, il est impossible de déplacer simplement cette tour ailleurs. Ses fondations – des fonctions unidirectionnelles – ne peuvent reposer que sur un socle de problèmes NP.
Pour construire une tour sur des problèmes plus complexes, les cryptographes auraient besoin d'une nouvelle base, non constituée de fonctions à sens unique. Cela semblait impossible jusqu'à il y a quelques années, lorsque les chercheurs ont réalisé que la physique quantique pouvait leur être utile.
Tout a commencé avec un article de 2021 d'un étudiant diplômé nommé William Kretschmer qui a attiré l'attention sur un étrange problème concernant les propriétés des systèmes quantiques. Les chercheurs ont rapidement démontré que le problème de Kretschmer pouvait remplacer les fonctions à sens unique comme fondement d'une nouvelle tour de cryptographie protocoles. L'année suivante, Kretschmer et d'autres ont prouvé que cette approche alternative pouvait fonctionner même sans problèmes NP complexes. Soudain, il semblait possible de construire une forteresse cryptographique bien plus robuste.
Mais où la construire ? Le problème quantique sur lequel Kretschmer s'est appuyé impliquait des dispositifs informatiques hypothétiques appelés oracles, capables de répondre instantanément à des questions spécifiques. Les oracles peuvent être des outils théoriques utiles, mais ils n'existent pas réellement. Les preuves de Kretschmer étaient comme un plan pour construire ce château dans le ciel. Y avait-il un moyen de le faire descendre sur terre ?
Deuxième Fondation
À l’automne 2022, cette question a retenu l’attention de Dakshita Khurana, cryptographe à l'Université de l'Illinois à Urbana-Champaign et au sein de NTT Research et son étudiant diplômé Kabir Tomer. Elle s'est lancée dans la construction d'une nouvelle tour de cryptographie. La première étape a consisté à construire une nouvelle fondation en utilisant des blocs de construction quantiques plutôt que des fonctions unidirectionnelles classiques. Elle devait ensuite prouver que cette nouvelle fondation pouvait supporter une tour d'autres protocoles cryptographiques. Une fois cette preuve faite, elle devait trouver un emplacement solide pour l'ensemble : un socle de problèmes concrets, apparemment encore plus complexes que les problèmes NP utilisés en cryptographie classique.
Pour la première étape, Khurana et Tomer se sont concentrés sur une version quantique d'une fonction à sens unique, appelée générateur d'état à sens unique, qui satisfasse aux trois propriétés qui rendent les fonctions unidirectionnelles utiles. Premièrement, la fonction doit s'exécuter rapidement afin de pouvoir générer facilement un verrou cryptographique et la clé correspondante pour l'ouvrir pour chaque message envoyé. Deuxièmement, chaque verrou doit être sécurisé, nécessitant un effort considérable pour être forcé sans la bonne clé. Enfin, chaque verrou doit être facile à ouvrir avec la bonne clé.
La différence fondamentale résidait dans la nature des verrous. Les fonctions unidirectionnelles classiques génèrent des verrous mathématiques composés de bits – les 0 et les 1 qui stockent l'information dans un ordinateur classique. Les générateurs d'états unidirectionnels quantiques généreraient quant à eux des verrous composés d'unités d'information quantique appelées qubits. Ces verrous quantiques pourraient potentiellement rester sécurisés même si tous les verrous classiques sont faciles à briser. Khurana et Tomer espéraient partir de cette nouvelle fondation quantique et y ériger une tour de protocoles cryptographiques. " Cela s'est avéré très difficile ", a déclaré Khurana. " Nous sommes restés bloqués pendant de très nombreux mois. "
En juillet 2023, Khurana était enceinte de près de neuf mois et préparait un congé parental. Tomer était à court d'idées. " Je suis bien plus pessimiste que Dakshita ", dit-il. " C'est toujours elle qui croit que tout va s'arranger. "
Ils firent alors une avancée décisive. L'étape cruciale consistait à définir un autre élément mathématique de base, véritable sous-sol : une structure reliant les fondations des générateurs d'états unidirectionnels à une tour de protocoles cryptographiques. Lorsque Khurana et Tomer déterminèrent les propriétés que cet élément devait posséder, ils découvrirent qu'il ressemblait à une fonction unidirectionnelle présentant un mélange déroutant de caractéristiques quantiques et classiques. Comme dans une fonction unidirectionnelle ordinaire, les verrous et les clés étaient constitués de bits classiques, mais la procédure de génération de ces verrous et clés ne pouvait s'exécuter que sur un ordinateur quantique. Plus étrange encore, le nouveau bloc de base satisfaisait aux deux premières propriétés définissant les fonctions unidirectionnelles, mais pas à la troisième : il était facile de générer des verrous et des clés, et chaque verrou était difficile à casser. En revanche, une clé ne pouvait pas ouvrir facilement sa serrure.
Khurana et Tomer ont baptisé ces nouveaux blocs de construction déroutants " énigmes à sens unique ". Intuitivement, il est difficile d'imaginer leur utilité : à quoi sert une clé inutilisable ? Mais les deux cryptographes ont démontré que les énigmes à sens unique, combinées à d'autres astuces quantiques, permettraient de mettre en œuvre de nombreux protocoles cryptographiques. Si vous pouvez générer des serrures et des clés qui s'assemblent en principe, peu importe que la procédure de déverrouillage soit extrêmement inefficace.
" Le simple fait de savoir qu'il existe un algorithme pouvant être arbitrairement lent suffit »", a déclaré Kretschmer, aujourd'hui chercheur à l'Institut Simons. " C'est très surprenant. "
Une fois cette pièce manquante en place, ils ont rapidement terminé la preuve le 4 août. La fille de Khurana est née quelques jours plus tard.
Dossier permanent
En novembre, Khurana était de retour au travail et prête à s'attaquer à la deuxième phase de son plan. Elle et Tomer avaient démontré que de nombreux types de cryptographie pouvaient être construits sur des énigmes unidirectionnelles, et que ces énigmes unidirectionnelles pouvaient à leur tour être construites sur une nouvelle base quantique constituée de générateurs d'états unidirectionnels. L'étape suivante de leur plan initial consistait à relier cette base quantique à un nouveau socle : un ensemble de problèmes mathématiques relativement inattaquables, encore plus complexes que ceux de la théorie des probabilités.
Mais alors que Khurana et Tomer s'attaquaient à cette tâche, ils ont décidé d'adopter une approche plus directe : oublier les générateurs d'états à sens unique et ancrer à la place les énigmes à sens unique directement au fondement mathématique.
D'un certain point de vue, ce choix semblait étrange. Les énigmes à sens unique étaient des bizarreries mathématiques que Khurana et Tomer avaient utilisées dans une étape intermédiaire de leur démonstration.
Les énigmes unidirectionnelles présentaient néanmoins certains avantages. D'une part, bien que quantiques, les clés et verrous qu'elles génèrent sont classiques. Khurana pensait que cela faciliterait leur rattachement à un socle de mathématiques classiques. De plus, les énigmes unidirectionnelles génèrent des clés trop complexes pour ouvrir les verrous. Cela pourrait faciliter leur rattachement à des problèmes si complexes que même la vérification des solutions semble désespérément difficile.
Mais quels problèmes spécifiques pourraient fonctionner ? Khurana avait un candidat en tête : calculer une combinaison spécifique d'entrées dans une table de nombres appelée matrice. Ce problème, appelé " problème de la matrice permanente ", est notoirement difficile à résoudre pour les grandes matrices, et il n'existe aucun moyen simple de vérifier l'exactitude d'un calcul. Le problème de la matrice permanente présente également d'autres propriétés mathématiques particulières que les cryptographes trouvent intéressantes.
" Ce serait un beau problème sur lequel baser la cryptographie ", a déclaré Khurana.
Le problème de la matrice permanente est également lié à un autre problème que les ordinateurs quantiques peuvent facilement résoudre, mais que les ordinateurs classiques ne semblent pas pouvoir résoudre . Les chercheurs s'efforcent de démontrer cet avantage du calcul quantique de manière théorique précise. Khurana et Tomer ont montré qu'une telle preuve leur permettrait également de construire des énigmes unidirectionnelles sécurisées – et donc toute la tour de la cryptographie quantique – en s'appuyant sur le problème de la matrice permanente.
" Ils ont pu y parvenir à partir d'hypothèses bien étudiées ", a déclaré Kretschmer. " J'étais vraiment ravi de constater cela. "
Grâce à leur nouveau résultat, Khurana et Tomer ont réussi à réduire deux problèmes ouverts à un seul. Si les chercheurs parviennent à prouver que les ordinateurs quantiques surpassent véritablement les ordinateurs classiques dans une tâche spécifique, la cryptographie quantique bénéficiera automatiquement d'une assise théorique bien plus solide que pratiquement toute autre forme de cryptographie classique.
Malheureusement, la nouvelle approche de Khurana et Tomer pour envoyer des messages secrets ne sera pas bientôt utilisable. Malgré les progrès récents , l'informatique quantique n'est pas encore suffisamment mature pour mettre leurs idées en pratique. Parallèlement, d'autres chercheurs ont mis au point des méthodes de cryptographie quantique qui pourraient être utilisées plus rapidement, bien que des travaux supplémentaires soient nécessaires pour établir qu'ils sont véritablement sécurisés.
La cryptographie quantique a déjà révélé de nombreuses surprises, et les chercheurs n'ont commencé que récemment à explorer ses possibilités. " Nous essayons simplement de comprendre ce nouveau paysage qui existait déjà ", a déclaré Zhandry.