La réponse à une question épineuse pourrait débloquer la sécurité Internet

math

Crédit : CC0 Domaine public

Est-il plus facile de vérifier qu’une solution à un problème est correcte que de résoudre le problème ?

La question, connue sous le nom de problème « NP contre P », est le problème fondamental le plus profond en informatique et en cryptographie, au cœur de la question de savoir si des données Internet peuvent un jour être vraiment privées.

Dans le cas improbable où P = NP, tous les schémas de cryptage et méthodes de confidentialité de nos données sur Internet ne seraient pas sécurisés. Mais même si P n’est pas égal à NP, et même si quelqu’un parvient à le prouver, nous ne savons toujours pas comment obtenir un schéma de cryptage vraiment sécurisé.

Rafael Pass, professeur d’informatique à Cornell Tech et au Cornell Ann S. Bowers College of Computing and Information Science, et le co-auteur Yanyi Liu, doctorant dans le domaine de l’informatique, ont proposé une solution, en quelque sorte.

Leurs travaux sont détaillés dans « On the Possibility of Basing Cryptography on EXP ≠ BPP », qui a remporté le prix du meilleur article à CRYPTO ’21 et sera présenté lors de la conférence le 17 août.

La question posée dans le titre de l’article porte sur l’idée d’aléatoire, une épineuse question d’informatique et de mathématiques. Le problème EXP contre BPP – bien qu’il ne soit pas aussi célèbre que « NP contre P » – est un autre problème ouvert de longue date et cause encore plus d’embarras sur le terrain, selon Pass.

« La question est essentiellement : le hasard peut-il accélérer les calculs de façon exponentielle ? » Pass dit. « Cela est clairement considéré comme impossible. Nous ne penserions pas que le simple fait de lancer des pièces au hasard nous permettra d’accélérer nos calculs de manière exponentielle. Ce serait un peu fou, mais les gens n’ont toujours pas été en mesure de le prouver. »

Si les calculs peuvent être accélérés de manière exponentielle en utilisant le hasard, alors tous les schémas de chiffrement peuvent être rompus. Les attaques dites « par force brute », dans lesquelles toutes les clés possibles sont énumérées, pourraient désormais être efficacement mises en œuvre.

Pass et Liu abordent la question de savoir si le simple fait de supposer que EXP n’est pas égal à BPP – que les calculs ne peuvent pas être accélérés de manière exponentielle en utilisant le hasard – suffit pour obtenir des schémas de cryptage incassables. À cette fin, Pass et Liu revisitent une connexion entre les schémas de cryptage et la complexité de Kolmogorov limitée dans le temps qu’ils ont établie l’année dernière.

La complexité de Kolmogorov limitée dans le temps d’une chaîne (x) est la longueur du programme le plus court qui peut produire x dans un laps de temps défini. Mais le nouveau travail considère une notion différente de la complexité de Kolmogorov : le calcul de la « complexité de Levin-Kolmogorov » d’une chaîne (x). Le problème : étant donné x, trouvez le programme « le plus efficace » qui affiche x, où « efficacité » est la somme de la longueur du programme et du logarithme du temps d’exécution du programme.

Leur article montre que les cryptages incassables sont possibles si et seulement s’il n’existe pas d’algorithme efficace capable de calculer la complexité de Levin-Kolmogorov pour la plupart des chaînes, sans commettre trop d’erreurs.

« Donc, pour obtenir un cryptage incassable », a déclaré Pass, « nous devons simplement montrer qu’aucun algorithme efficace ne peut résoudre ce problème particulier. »

Bien qu’ils ne soient pas en mesure de prouver qu’un tel algorithme n’existe pas, ils montrent qu’en supposant que EXP n’est pas égal à BPP, il n’existe pas d’algorithme « sans erreur » efficace (un algorithme qui produit la bonne réponse ou dit « Je ne savoir ») pour déterminer la complexité de Levin-Kolmogorov d’une grande fraction de chaînes aléatoires.

« Il n’a pas à le résoudre pour toutes les ficelles – il peut parfois abandonner », a déclaré Pass. « Mais quand il donne une réponse, il faut toujours que ce soit la bonne. »

En d’autres termes, les algorithmes qui peuvent se tromper fonctionnent très bien sur les tests où vous êtes récompensé en fonction du nombre de questions que vous obtenez correctement, tandis que les algorithmes sans erreur fonctionnent également bien sur les tests où vous êtes pénalisé pour les questions que vous vous trompez.

Leurs résultats concluent que le problème de complexité de Levin-Kolmogorov est central pour comprendre à la fois le problème EXP contre BPP et le problème de l’existence de schémas de cryptage incassables.

« Ce problème détient la clé de certaines des questions les plus importantes en informatique », a déclaré Pass. « Ce problème spécifique est fondamental et nous devons vraiment comprendre l’écart entre les algorithmes sans erreur et les algorithmes qui peuvent se tromper. »

Les auteurs montrent que si l’écart peut être comblé – un gigantesque « si » en informatique – alors vous avez non seulement prouvé qu’une cryptographie incassable existe si EXP n’est pas égal à BPP, mais en fait vous avez également prouvé que NP n’est pas égal à P.


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


Plus d’information:
Yanyi Liu et Rafael Pass, Sur la possibilité de baser la cryptographie sur EXP 6 ≠ BPP. eprint.iacr.org/2021/535.pdf

Fourni par l’Université Cornell

Citation: La réponse à une question épineuse pourrait débloquer la sécurité Internet (2021, 12 août) récupérée le 12 août 2021 sur https://techxplore.com/news/2021-08-thorny-internet.html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation équitable à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans l’autorisation écrite. Le contenu est fourni seulement pour information.