La théorie du hasard pourrait être la clé de la sécurité Internet –

La question est au cœur de la cryptographie depuis des milliers d’années et est au cœur des efforts visant à sécuriser les informations privées sur Internet. Dans un nouvel article, les chercheurs de Cornell Tech ont identifié un problème qui détient la clé pour savoir si tout le cryptage peut être rompu – ainsi qu’un lien surprenant avec un concept mathématique qui vise à définir et à mesurer le caractère aléatoire.

«Notre résultat montre non seulement que la cryptographie a un problème naturel de« mère », mais il montre également un lien profond entre deux domaines bien distincts des mathématiques et de l’informatique – la cryptographie et la théorie de l’information algorithmique», a déclaré Rafael Pass, professeur d’informatique à Cornell Tech.

Pass est co-auteur de «On One-Way Functions and Kolmogorov Complexity», qui sera présenté au Symposium IEEE sur les fondations de l’informatique, qui se tiendra du 16 au 19 novembre à Durham, en Caroline du Nord.

“Le résultat”, a-t-il dit, “est qu’un problème de calcul naturel introduit dans les années 1960 en Union soviétique caractérise la faisabilité de la cryptographie de base – le cryptage à clé privée, les signatures numériques et l’authentification, par exemple.”

Pendant des millénaires, la cryptographie a été considérée comme un cycle: quelqu’un a inventé un code, le code était efficace jusqu’à ce que quelqu’un finisse par le casser, et le code est devenu inefficace. Dans les années 1970, des chercheurs à la recherche d’une meilleure théorie de la cryptographie ont introduit le concept de la fonction unidirectionnelle – une tâche facile ou un problème dans un sens qui est impossible dans l’autre.

Par exemple, il est facile d’allumer une allumette, mais impossible de ramener une allumette en feu à son état éteint sans réorganiser ses atomes – une tâche extrêmement difficile.

«L’idée était que si nous avons une telle fonction à sens unique, c’est peut-être un très bon point de départ pour comprendre la cryptographie», a déclaré Pass. “Crypter le message est très simple. Et si vous avez la clé, vous pouvez également la décrypter. Mais quelqu’un qui ne connaît pas la clé devrait faire la même chose que restaurer une correspondance allumée.”

Mais les chercheurs n’ont pas pu prouver l’existence d’une fonction unidirectionnelle. Le candidat le plus connu – qui est également à la base des schémas de cryptage les plus couramment utilisés sur Internet – repose sur la factorisation d’entiers. Il est facile de multiplier deux nombres premiers aléatoires – par exemple, 23 et 47 – mais beaucoup plus difficile de trouver ces deux facteurs si on leur donne seulement leur produit, 1081.

On pense qu’aucun algorithme d’affacturage efficace n’existe pour les grands nombres, a déclaré Pass, bien que les chercheurs n’aient peut-être pas encore trouvé les bons algorithmes.

“La question centrale que nous abordons est: existe-t-il? Y a-t-il un problème naturel qui caractérise l’existence de fonctions à sens unique?” il a dit. “Si c’est le cas, c’est la mère de tous les problèmes, et si vous avez un moyen de résoudre ce problème, vous pouvez interrompre toutes les fonctions supposées à sens unique. Et si vous ne savez pas comment résoudre ce problème, vous pouvez réellement obtenir cryptographie sécurisée. “

Pendant ce temps, les mathématiciens des années 1960 ont identifié ce que l’on appelle la complexité de Kolmogorov, qui se réfère à la quantification du caractère aléatoire ou du modèle d’une chaîne de nombres. La complexité de Kolmogorov d’une chaîne de nombres est définie comme la longueur du programme informatique le plus court qui peut générer la chaîne; pour certaines chaînes, telles que 121212121212121212121212121212, il existe un programme court qui la génère – alternez 1 et 2. Mais pour des chaînes de nombres plus compliquées et apparemment aléatoires, telles que 37539017332840393452954329, il peut ne pas exister de programme plus court que la longueur de la chaîne elle-même.

Le problème intéresse depuis longtemps les mathématiciens et les informaticiens, dont Juris Hartmanis, professeur émérite d’informatique et d’ingénierie. Parce que le programme informatique tentant de générer le nombre pouvait prendre des millions, voire des milliards d’années, des chercheurs de l’Union soviétique dans les années 1960, ainsi que Hartmanis et d’autres dans les années 1980, ont développé la complexité de Kolmogorov limitée dans le temps – la durée du programme le plus court qui peut produire une chaîne de nombres dans un certain laps de temps.

Dans l’article, Pass et l’étudiant au doctorat Yanyi Liu ont montré que si le calcul de la complexité de Kolmogorov limitée dans le temps est difficile, alors des fonctions à sens unique existent.

Bien que leur découverte soit théorique, elle a des implications potentielles sur la cryptographie, y compris la sécurité Internet.

«Si vous pouvez trouver un algorithme pour résoudre le problème de complexité limité dans le temps de Kolmogorov, alors vous pouvez briser tous les cryptos, tous les schémas de cryptage, toutes les signatures numériques», a déclaré Pass. “Cependant, s’il n’existe pas d’algorithme efficace pour résoudre ce problème, vous pouvez obtenir une fonction unidirectionnelle, et par conséquent, vous pouvez obtenir un cryptage sécurisé et des signatures numériques, etc.”

La recherche a été financée en partie par la National Science Foundation et le Air Force Office of Scientific Research, et était basée sur des recherches financées par l’activité Intelligence Advanced Research Projects au sein du bureau du directeur du renseignement national.