Statut des mondes d'Impagliazzo?

33

En 1995, Russell Impagliazzo a proposé cinq mondes de complexité:

1- Algorithmique: P=NP avec toutes les conséquences étonnantes.

2- Heuristica: problèmes complets sont difficiles dans le pire des cas ( P ≠ N PNPP≠NP ) mais sont efficacement résolubles dans le cas moyen.

3- Pessiland: Il existe des problèmes complets de type , mais les fonctions à sens unique n'existent pas. Cela implique que nous ne pouvons pas générer d'instances dures de N PNPNP problème -complete avec une solution connue.

4- Minicrypt: les fonctions unidirectionnelles existent mais les systèmes cryptographiques à clé publique sont impossibles

5- Cryptomanie: des systèmes cryptographiques à clé publique existent et une communication sécurisée est possible.

Quel monde est favorisé par les récents progrès de la complexité informatique? Quelle est la meilleure preuve du choix?

Russell Impagliazzo, Une vue personnelle de la complexité moyenne des cas , 1995

Les cinq mondes d'Impagliazzo, le blog sur la complexité informatique

cc.complexity-theory conditional-results average-case-complexity Mohammad Al-Turkistany
la source
2
Je ne suis pas assez expert pour répondre, mais j'ai pensé que vous aimeriez savoir qu'au premier atelier sur les obstacles à la complexité, Impagliazzo a appelé à un programme de recherche tout à fait conforme à votre question. Appelez des «oracles semblables à la Terre» dans lesquels se trouvent les mêmes théorèmes de complexité qui tiennent dans le «vrai» monde non relativisé dans lequel nous vivons. Ensuite, étudiez les propriétés de ces oracles qui sont un peu comme la vraie Terre. Donc, dans ce cadre, votre question devient: "Qu'est-ce qu'un oracle doit satisfaire pour ressembler à la Terre?"
Aaron Sterling

Réponses:

26

Il y a environ un an, j'ai co-organisé un atelier sur la complexité et la cryptographie: état des mondes d'Impagliazzo , et les diapositives et vidéos sur le site Web peuvent être intéressantes.

La réponse courte est que peu de choses ont changé dans le sens où la plupart des chercheurs croient encore que nous vivons dans "Cryptomania" et nous avons toujours plus ou moins les mêmes preuves à ce sujet, et pas beaucoup de progrès sur l'effondrement des mondes les uns pour les autres.

La nouvelle information peut-être la plus importante est l'algorithme de Shor qui montre qu'au moins si vous remplacez P par BQP, les cryptosystèmes à clé publique les plus couramment utilisés ne sont pas sécurisés. Mais, en raison des cryptosystèmes basés sur Lattice, l'hypothèse par défaut est que nous vivons dans la cryptomanie même dans ce cas, bien que le consensus ici soit peut-être un peu plus faible que le cas classique. Même dans le cas classique, il semble y avoir beaucoup plus de preuves de l'existence de fonctions à sens unique ("Minicrypt") que l'existence d'un cryptage à clé publique ("Cryptomania"). Pourtant, étant donné l'effort que les gens ont dépensé pour essayer de briser divers cryptosystèmes à clé publique, il existe également des preuves significatives de ce dernier.

Boaz Barak
la source
Ce lien peut mieux fonctionner: archive.dimacs.rutgers.edu/Workshops/Cryptography/program.html
Timothy Chow
18

Bonne question, mais les scientifiques n'ont même pas réussi à séparer "Algorithmica" des cas restants, encore moins à décider du monde exact dans lequel nous vivons.

Cela dit, il existe plusieurs articles de recherche sur le sujet. Voir par exemple: Sur la possibilité de baser la cryptographie sur l'hypothèse que P! = NP par Goldreich et Goldwasser, et leurs références.

Voir aussi Baser les fonctions unidirectionnelles sur la dureté NP par Adi Akavia et al.

De plus, il est bien connu que le décodage de certains cryptosystèmes est NP-difficile (voir, par exemple, le cryptosystème McEliece ou la cryptographie basée sur Lattice ). Je ne sais pas pourquoi cela ne résout pas le problème, car je ne connais pas ces systèmes de cryptage. Voir les commentaires de Peter Shor ci-dessous.

Je vous suggère également de jeter un coup d'œil à la discussion sur Stackoverflow . La revue de la littérature qui cite le travail d'Impagliazzo peut également être instructive.

EDIT: Les résultats suivants pourraient être intéressants:

Feigenbaum et Fortnow. Auto-réductibilité aléatoire des ensembles complets. SIAM Journal on Computing, 22: 994–1005, 1993.

Bogdanov et Trevisan. Réduction des pires cas aux cas moyens pour les problèmes de NP. Dans Actes du 44e Symposium annuel de l'IEEE sur les fondements de l'informatique, pages 308–317, 2003.

Akavia, Goldreich, Goldwasser et Moshkovitz. Baser les fonctions unidirectionnelles sur la dureté NP

Gutfreund et Ta-Shma. Nouvelles connexions entre dérandomisation, complexité du pire des cas et complexité du cas moyen. Technologie. Rep. TR06-108, Colloque électronique sur la complexité informatique, 2006.

Bogdanov et Trevisan. Complexité moyenne. A trouvé. Théorie des tendances. Comput. Sci. 2, 1 (octobre 2006), 1-106. DOI = http://dx.doi.org/10.1561/0400000004

MS Dousti
la source
5
Le cryptosystème McEliece n'est pas un cryptosystème; il s'agit de toute une famille de cryptosystèmes, selon la classe de codes correcteurs que vous utilisez. Si vous utilisez des codes de correction d'erreurs arbitraires, il est difficile de casser NP, mais il est également difficile de NP de décoder un message. Si vous utilisez une classe de codes de correction d'erreurs qui a un algorithme de décodage en temps polynomial, il est en effet temps polynomial de décoder le message, mais nous n'avons plus de preuve que casser le cryptosystème est difficile NP. La situation avec la cryptographie sur réseau est meilleure, mais elle n'est toujours pas difficile à NP.
Peter Shor
@Peter: Merci beaucoup! Vous avez résolu un puzzle qui m'intriguait depuis longtemps!
MS Dousti
En fait, il semble que pour certaines familles de codes correcteurs d'erreurs, le cryptosystème McEliece a été rompu, mais pas pour les codes Goppa, qui étaient dans la proposition originale de McEliece.
Peter Shor