La version originale de cette histoire est apparu dans Combien de magazine.

Les problèmes difficiles ne sont généralement pas un spectacle bienvenu. Mais les cryptographes les aiment. C’est parce que certains problèmes de mathématiques difficiles sous-tendent la sécurité du chiffrement moderne. Toute astuce intelligente pour les résoudre condamnera la plupart des formes de cryptographie.

Il y a plusieurs années, les chercheurs ont trouvé Une approche radicalement nouvelle du cryptage Cela manque ce point faible potentiel. L’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éciales, la nouvelle approche peut accomplir une gamme de tâches beaucoup plus large. Et cela pourrait fonctionner même si tous les problèmes au cœur de la cryptographie «classique» ordinaire se révèlent facilement résolubles.

Mais cette découverte frappante reposait sur des hypothèses irréalistes. Le résultat a été «plus une preuve de concept», a déclaré Ferme maischercheur en cryptographie au Simons Institute pour la théorie de l’informatique à Berkeley, en Californie. «Ce n’est pas une déclaration sur le monde réel.»

Maintenant, un nouveau papier Par deux cryptographes ont ouvert une voie vers la cryptographie quantique sans ces hypothèses bizarres. « Cet article dit que si certaines autres conjectures sont vraies, alors la cryptographie quantique doit exister », a déclaré Ma.

Château dans le ciel

Vous pouvez considérer la cryptographie moderne comme une tour avec trois parties essentielles. La première partie est le fondement profondément sous la tour, qui est faite de problèmes mathématiques durs. La tour elle-même est la deuxième partie – vous pouvez trouver des protocoles cryptographiques spécifiques qui vous permettent d’envoyer des messages privés, de signer des documents numériques, des bulletins de vote en cast secrète, etc.

Entre les deux, sécuriser ces applications quotidiennes au socle mathématique, se trouve une base en blocs de construction appelés fonctions unidirectionnelles. Ils sont responsables de l’asymétrie inhérente à tout schéma de chiffrement. « C’est à sens unique parce que vous pouvez crypter des messages, mais vous ne pouvez pas les décrypter », a déclaré Mark Zhandryun cryptographe chez NTT Research.

Dans les années 80, les chercheurs ont prouvé que la cryptographie construite au sommet des fonctions unidirectionnelles assurerait la sécurité de nombreuses tâches différentes. Mais des décennies plus tard, ils ne sont toujours pas certains que le fondement est assez fort pour le soutenir. Le problème est que le substratum rocheux est fait de problèmes difficiles particuliers – de manière technique connue sous le nom de problèmes de NP – dont la définition de la fonctionnalité est qu’il est facile de vérifier si une solution candidate est correcte. (Par exemple, diviser un nombre en ses facteurs premiers est un problème de NP: difficile à faire pour un grand nombre, mais facile à vérifier.)

Beaucoup de ces problèmes semblent intrinsèquement difficiles, mais les informaticiens Je n’ai pas pu le prouver. Si quelqu’un découvre un algorithme ingénieux pour résoudre rapidement les problèmes de NP les plus durs, le fondement s’effondrera et toute la tour s’effondrera.

Malheureusement, vous ne pouvez pas simplement déplacer votre tour ailleurs. La fondation de la tour – fonctionne à une voie – ne peut être assis que sur un fondement de problèmes de NP.

Pour construire une tour sur des problèmes plus difficiles, les cryptographes auraient besoin d’une nouvelle fondation qui n’est pas faite de fonctions unidirectionnelles. Cela semblait impossible jusqu’à il y a quelques années, lorsque les chercheurs ont réalisé que la physique quantique pouvait aider.