Quelle est la meilleure façon de résoudre des problèmes difficiles ? C’est la question au cœur d’un sous-domaine de l’informatique appelé théorie de la complexité computationnelle. C'est une question difficile à répondre, mais inversez-la et cela devient plus facile. La pire approche est presque toujours celle des essais et des erreurs, qui consistent à intégrer des solutions possibles jusqu'à ce qu'une solution fonctionne. Mais pour certains problèmes, il semble qu’il n’y ait tout simplement pas d’alternative : la pire approche est aussi la meilleure.

Les chercheurs se demandent depuis longtemps si c'est vraiment le cas, a déclaré Rahul Ilango, étudiant diplômé étudiant la théorie de la complexité au Massachusetts Institute of Technology. « Vous pourriez demander : « Y a-t-il des problèmes pour lesquels deviner et vérifier est tout simplement optimal ? » »

Les théoriciens de la complexité ont étudié de nombreux problèmes informatiques, et même les plus difficiles admettent souvent une sorte de procédure intelligente, ou d'algorithme, qui rend la recherche d'une solution un peu plus facile que de simples essais et erreurs. Parmi les rares exceptions figurent les problèmes dits de compression, où l’objectif est de trouver la description la plus courte d’un ensemble de données.

Mais en novembre dernier, deux groupes de chercheurs indépendamment découvert un autre algorithme pour les problèmes de compression – un algorithme légèrement plus rapide que la vérification de toutes les réponses possibles. La nouvelle approche fonctionne en adaptant un algorithme inventé par les cryptographes il y a 25 ans pour s'attaquer à un problème différent. Il n'y a qu'une seule restriction : vous devez adapter l'algorithme à la taille de votre ensemble de données.

"Ce sont des résultats vraiment magnifiques et importants", a déclaré Éric Allender, informaticien théorique à l'Université Rutgers.

Définir la dureté

Ces nouveaux résultats sont les derniers à étudier une question étudiée pour la première fois en Union soviétique, bien avant l'avènement de la théorie de la complexité. "Avant que j'entre à l'école primaire, les gens en Russie formulaient cela", a déclaré Allender.

Le problème informatique spécifique étudié par ces chercheurs soviétiques, appelé problème de la taille minimale du circuit, s’apparente à celui auquel les concepteurs de matériel informatique sont constamment confrontés. Si on vous donne des spécifications complètes sur la façon dont un circuit électronique doit se comporter, pouvez-vous trouver le circuit le plus simple qui fera le travail ? Personne ne savait comment résoudre ce problème sans « perebor » – un mot russe à peu près équivalent à « recherche exhaustive ».

Le problème de la taille minimale du circuit est un exemple de problème de compression. Vous pouvez décrire le comportement d'un circuit avec une longue chaîne de bits (0 et 1) et ensuite demander s'il existe un moyen de reproduire ce même comportement en utilisant moins de bits. Vérifier toutes les configurations de circuits possibles prendrait un temps qui augmente de façon exponentielle avec le nombre de bits de la chaîne.

Ce type de croissance exponentielle est la caractéristique déterminante d’un problème informatique difficile. Mais tous les problèmes difficiles ne sont pas également difficiles : certains ont des algorithmes plus rapides que la recherche exhaustive, même si leur durée d'exécution augmente toujours de façon exponentielle. En termes modernes, la grande question est de savoir si de tels algorithmes existent pour les problèmes de compression.

En 1959, un éminent chercheur nommé Sergey Yablonsky affirmait avoir prouvé qu'une recherche exhaustive était réellement le seul moyen de résoudre le problème de la taille minimale du circuit. Mais sa démonstration laisse quelques failles. Certains chercheurs ont remarqué les failles à l'époque, mais Yablonsky a eu suffisamment d'influence pour décourager la plupart des autres de travailler sur la question du perebor.

Dans les décennies qui ont suivi, peu de chercheurs ont étudié les problèmes de compression, et la question du perebor était surtout connue comme une note de bas de page dans la préhistoire de la théorie de la complexité. L'attention généralisée portée à la question n'est apparue que récemment, après que les chercheurs ont découvert un curieux lien entre les problèmes de compression et les fondements de la cryptographie.

Circulation à sens unique

La cryptographie moderne utilise des problèmes informatiques complexes pour protéger les messages secrets. Mais la dureté des calculs n’est utile que s’ils sont asymétriques – s’il est difficile de déchiffrer les messages codés mais pas difficile de les coder en premier lieu.

Dans tout système de cryptographie, l'origine de cette asymétrie est un objet mathématique appelé fonction unidirectionnelle, qui transforme les chaînes de bits d'entrée en chaînes de sortie de même longueur. Étant donné une entrée dans une fonction unidirectionnelle, il est facile de calculer la sortie, mais étant donné une sortie, il est difficile d'inverser la fonction, c'est-à-dire de la procéder à une ingénierie inverse et de récupérer l'entrée.

"Les cryptographes aimeraient vraiment disposer de fonctions unidirectionnelles calculables très, très efficacement et qui sont vraiment très difficiles à inverser", a déclaré Allender. De nombreuses fonctions mathématiques semblent avoir cette propriété, et la difficulté d’inverser ces fonctions vient de la difficulté apparente de résoudre différents problèmes informatiques.

Malheureusement, les cryptographes ne savent pas avec certitude si l'une de ces fonctions est vraiment difficile à inverser. En effet, il est possible que de véritables fonctions à sens unique n'existent pas. Cette incertitude persiste parce que les théoriciens de la complexité ont lutté pendant 50 ans pour prouver que des problèmes apparemment difficiles le sont réellement. Si ce n’est pas le cas, et si les chercheurs découvrent des algorithmes ultra-rapides pour résoudre ces problèmes, cela serait désastreux pour la cryptographie – un peu comme si l’on dirigeait soudainement des voitures à grande vitesse dans les deux sens sur une rue à sens unique.

Même si une compréhension globale de la complexité des calculs reste difficile à atteindre, les cryptographes ont récemment fait des progrès passionnants vers une théorie unifiée des fonctions unidirectionnelles. Un grand pas a été franchi en 2020, lorsque le cryptographe de l’Université de Tel Aviv Col Rafael et son étudiant diplômé Yan Yi Liu prouvé que les fonctions à sens unique sont intimement connecté à un problème de compression spécifique appelé problème de complexité de Kolmogorov limité dans le temps.

Si ce problème est vraiment difficile à résoudre pour la plupart des entrées, alors le résultat de Pass et Liu donne une recette sur la façon de construire une fonction unidirectionnelle dont la difficulté est prouvée - une fonction dont la sécurité est garantie même si d'autres problèmes de calcul s'avèrent beaucoup plus faciles. que prévu par les chercheurs. Mais s’il existe un algorithme rapide pour résoudre le problème de complexité limité dans le temps de Kolmogorov, alors la cryptographie est vouée à l’échec et toute fonction peut être facilement inversée. Une fonction à sens unique basée sur la difficulté de ce problème est la fonction la plus sûre possible – une fonction à sens unique pour les gouverner tous.

S'appuyer sur des structures de données

La découverte de Pass et Liu constitue le dernier chapitre d'une longue série de recherches utilisant la théorie de la complexité pour mieux comprendre les fondements de la cryptographie. Mais cela suggère également un moyen d’inverser cette relation : l’équivalence entre le problème de complexité de Kolmogorov limité dans le temps et l’inversion de fonction implique que les connaissances sur l’un ou l’autre problème peuvent en révéler davantage sur l’autre. Les cryptographes étudient les algorithmes d’inversion de fonctions depuis des décennies pour mieux comprendre les points faibles de leurs méthodes de chiffrement. Les chercheurs ont commencé à se demander si ces algorithmes pourraient aider à répondre à des questions séculaires en théorie de la complexité.

Comme de nombreux problèmes informatiques, l’inversion de fonctions peut être résolue par une recherche exhaustive. Étant donné une chaîne de sortie, branchez simplement toutes les entrées possibles dans la fonction jusqu'à ce que vous trouviez celle qui donne la bonne réponse.

En 1980, le cryptographe Martin Hellman a commencé à étudier s’il était possible de faire mieux – la même question que les mathématiciens soviétiques avaient posée à propos des problèmes de compression des décennies plus tôt. Homme de l'enfer découvert que oui, c'est possible – à condition que vous soyez prêt à effectuer un travail supplémentaire à l'avance, en utilisant des objets mathématiques appelés structures de données.

Une structure de données est essentiellement un tableau qui stocke des informations sur la fonction à inverser, et sa construction nécessite de calculer les sorties de la fonction pour certaines entrées stratégiquement choisies. Tous ces calculs « pourraient prendre beaucoup de temps », a déclaré Ryan Williams, théoricien de la complexité au MIT. "Mais l'idée est que cela se fasse une fois, une fois pour toutes." Si vous essayez d'inverser la même fonction à partir de nombreuses sorties différentes (par exemple, pour décoder de nombreux messages différents chiffrés de la même manière), il peut être utile de faire ce travail à l'avance.

Bien sûr, le stockage de ces informations supplémentaires nécessite de l'espace, alors poussez cette stratégie à l'extrême et vous pourriez vous retrouver avec un programme rapide qui ne peut tenir sur aucun ordinateur. Hellman a conçu une structure de données intelligente qui a permis à son algorithme d'inverser la plupart des fonctions légèrement plus rapidement qu'une recherche exhaustive sans prendre trop de place. Puis en 2000, les cryptographes Amos Fiat et Moni Naor prolongé Les arguments de Hellman pour toutes les fonctions.

Après la percée de Pass et Liu en 2020, ces anciens résultats sont soudainement devenus d’actualité. L'algorithme de Fiat-Naor pourrait inverser des fonctions arbitraires plus rapidement qu'une recherche exhaustive. Cela pourrait-il également fonctionner pour des problèmes de compression ?

En civil

Les premiers chercheurs à se poser la question furent le théoricien de la complexité Rahul Santhanam de l'Université d'Oxford et son étudiant diplômé Hanlin Ren. Ils l'ont fait dans un papier 2021 prouvant que les problèmes de compression et d’inversion de fonction étaient encore plus liés que les chercheurs ne l’avaient imaginé.

Pass et Liu ont prouvé que si le problème de complexité de Kolmogorov limité dans le temps est difficile, alors l'inversion de fonction doit également l'être, et vice versa. Mais les problèmes peuvent être difficiles et néanmoins admettre des solutions un peu meilleures qu’une recherche exhaustive. Santhanam et Ren ont montré qu'il existe un lien étroit entre la nécessité d'une recherche exhaustive pour un problème et celle pour l'autre.

Leurs résultats ont eu des implications différentes pour deux grandes classes d’algorithmes que les chercheurs étudient souvent, appelés algorithmes « uniformes » et « non uniformes ». Les algorithmes uniformes suivent la même procédure pour chaque entrée : un programme uniforme pour trier des listes de nombres, par exemple, fonctionnera de la même manière, qu'il y ait 20 entrées sur la liste ou 20,000 XNUMX. Les algorithmes non uniformes utilisent à la place des procédures différentes pour des entrées de longueur différente.

Les structures de données utilisées par l'algorithme Fiat-Naor sont toujours adaptées à une fonction spécifique. Pour inverser une fonction qui brouille une chaîne de 10 bits, vous avez besoin d'une structure de données différente de celle dont vous auriez besoin pour inverser une fonction qui brouille une chaîne de 20 bits, même si le brouillage est effectué de la même manière. Cela fait de Fiat-Naor un algorithme non uniforme.

Les résultats de Santhanam et Ren suggèrent qu'il pourrait être possible de transformer l'algorithme de Fiat-Naor en un algorithme permettant de résoudre des problèmes de compression. Mais adapter l’algorithme d’un problème à l’autre n’a pas été simple et ils n’ont pas approfondi la question.

Pass est tombé sur la même idée un an plus tard, après avoir entendu Fiat parler de l'algorithme classique lors d'un atelier célébrant les contributions de Naor à la cryptographie. "Cette idée d'utiliser l'inversion de fonctions me trottait dans la tête depuis lors", a-t-il déclaré. Il a ensuite commencé à travailler sérieusement sur le problème avec un chercheur de l'Université de Tel Aviv. Noam Mazor.

Pendant ce temps, Ilango a eu l'idée de s'attaquer au problème après des discussions avec d'autres chercheurs, dont Santhanam, lors d'une visite au Simons Institute for the Theory of Computing à Berkeley, en Californie. "Cela est né d'une de ces conversations très fortuites où vous jetez simplement des choses", a déclaré Santhanam. Ilango s'est ensuite associé à Williams et Shuichi Hirahara, théoricien de la complexité à l'Institut national d'informatique de Tokyo.

Le plus difficile était de trouver comment intégrer la structure de données au cœur de l'algorithme de Fiat-Naor dans un algorithme non uniforme pour résoudre les problèmes de compression. Il existe une procédure standard pour effectuer ce type d'intégration, mais cela ralentirait l'algorithme, anéantissant ainsi son avantage sur la recherche exhaustive. Les deux équipes ont trouvé des moyens plus intelligents d'incorporer la structure de données Fiat-Naor et ont obtenu des algorithmes pour les problèmes de compression qui fonctionnaient sur toutes les entrées et restaient plus rapides qu'une recherche exhaustive.

Les détails des deux algorithmes diffèrent légèrement. Celui d'Ilango et de ses co-auteurs est plus rapide qu'une recherche exhaustive, même si vous limitez la recherche aux possibilités les plus simples, et il s'applique à tous les problèmes de compression : complexité de Kolmogorov limitée dans le temps, problème de taille minimale du circuit et bien d'autres. Mais l’idée de base était la même pour les deux algorithmes. Les techniques issues de la cryptographie ont fait leurs preuves dans ce nouveau domaine.

Convergence des inversions

La nouvelle preuve des algorithmes non uniformes soulève une question naturelle : qu’en est-il des algorithmes uniformes ? Existe-t-il un moyen de résoudre les problèmes de compression plus rapidement qu'une recherche exhaustive en les utilisant ?

La récente série de résultats implique qu’un tel algorithme serait équivalent à un algorithme uniforme pour inverser des fonctions arbitraires – ce que les cryptographes recherchent sans succès depuis des décennies. Pour cette raison, de nombreux chercheurs trouvent cette possibilité peu probable.

"Je serais très surpris", a déclaré Santhanam. "Cela nécessiterait une idée complètement nouvelle."

Mais Allender a déclaré que les chercheurs ne devraient pas écarter cette possibilité. « Pour moi, une bonne hypothèse de travail était que s'il existe une manière non uniforme de faire quelque chose, il y a très probablement une manière uniforme », a-t-il déclaré.

Quoi qu’il en soit, ces travaux ont incité les théoriciens de la complexité à s’intéresser de nouveau aux vieilles questions de la cryptographie. Yuval Ishaï, cryptographe au Technion à Haïfa, en Israël, a déclaré que c'était ce qui rendait cette activité la plus excitante.

« Je suis vraiment heureux de voir cette convergence d'intérêts entre les différentes communautés », a-t-il déclaré. "Je pense que c'est formidable pour la science."