Les «fonctions à sens unique» ont-elles des applications en dehors de la cryptographie?

Une fonction $f \colon \{0, 1\}^* \to \{0, 1\}^*$ est unidirectionnelle si $f$ peut être calculé par un algorithme de temps polynomial, mais pour chaque algorithme de temps polynomial randomisé $A$ ,

$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$

pour tout polynôme et suffisamment grand , en supposant que est choisi de manière uniforme à partir de . La probabilité est prise sur le choix des et le caractère aléatoire de .$p(n)$$n$$x$$\{ 0, 1 \}^n$$x$$A$

Alors ... "Les fonctions à sens unique" ont-elles des applications en dehors de la cryptographie? Si oui, quels sont-ils?

Les fonctions à sens unique apparaissent de manière cruciale dans le résultat des preuves naturelles de Razborov-Rudich. Je ne considérerais pas les bornes inférieures du circuit comme faisant partie de la "cryptographie", alors peut-être que cela correspond à vos critères.

Les fonctions à sens unique ont également figuré dans certaines discussions autour de la conjecture d'isomorphisme de Berman-Hartmanis . Joseph et Young ont supposé que si des fonctions à sens unique existaient, alors la conjecture d'isomorphisme échoue (à sens unique contre des adversaires déterministes, pas probabilistes, mais j'espère que c'est assez proche pour les besoins de cette question). John Rogers a donné un monde relativisé où la conjecture de Joseph-Young a échoué (c'est-à-dire où les fonctions à sens unique existent mais où la conjecture d'isomorphisme tient). Mais pour autant que je sache, la conjecture JY est toujours l'un des principaux éléments de preuve technique qui amène les gens à penser que la conjecture d'isomorphisme est fausse (s'ils le pensent).

L'essence de l'idée de Joseph et Young est que si est une fonction à sens unique, alors est complet mais "ne devrait pas" être isomorphe à SAT.f ( S A T ) N $f$$f(SAT)$$NP$

Oui, une table de hachage ou une carte de hachage nécessite une fonction unidirectionnelle. La détection des doublons (voir ceci et cela ) peut également être effectuée très efficacement en utilisant des fonctions unidirectionnelles. Les deux cas nécessitent de «bonnes» (avec de faibles chances de collision) des fonctions unidirectionnelles alors que la force cryptographique n'est généralement pas requise .

Il existe de nombreux résultats de "dureté cryptographique" (juste cette phrase Google) pour les problèmes d'apprentissage. Ce sont des résultats de dureté en supposant qu'il existe des fonctions à sens unique.

Les fonctions unidirectionnelles ont une application dans la complexité de Kolmogorov:

La symétrie du théorème de l'information indique que les informations contenues dans une chaîne $x$$y$

$K^q(x, y) = K^q(x) + K^q(y|x) + O(\log n)$$q$

S'il existe des fonctions unidirectionnelles, la symétrie bornée dans le temps polynomial de la conjecture d'information est fausse.

L. Longpre et S. Mocas. Symétrie des informations et fonctions unidirectionnelles. Lettres de traitement de l'information, 46 (2): 95 {100, 1993

L. Longpre et O. Watanabe. Sur la symétrie de l'information et l'inversibilité polynomiale du temps. Information et calcul, 121 (1): 14 {22, 1995