Arguments pour l'existence de fonctions à sens unique

J'ai lu dans plusieurs articles que l'existence de fonctions à sens unique est largement admise. Quelqu'un peut-il expliquer pourquoi c'est le cas? Quels arguments avons-nous pour soutenir l'existence de fonctions à sens unique?

Voici un argument selon lequel les fonctions unidirectionnelles devraient être difficiles à inverser. Supposons qu'il existe une classe de problèmes 3-SAT avec des solutions plantées difficiles à résoudre. Considérez la carte suivante:

où est une chaîne de bits, est une chaîne de bits (vous pouvez les utiliser pour amorcer un générateur de nombres aléatoires, ou vous pouvez demander autant de bits aléatoires que nécessaire) et est un problème -SAT ayant comme une solution plantée, où le générateur de nombres aléatoires détermine exactement quel problème -SAT vous choisissez. Pour inverser cette fonction unidirectionnelle, vous devez résoudre un problème -SAT avec une solution plantée.$x$$r$$s$$k$$x$$k$$k$

Cet argument montre qu'inverser une fonction unidirectionnelle est aussi difficile que résoudre des problèmes -SAT avec des solutions plantées. Et puisque -SAT est un problème NP-complet, si vous pouvez comprendre comment construire des instances dures avec des solutions plantées pour tout problème NP, vous pouvez planter des solutions dans des formules -SAT.$k$$k$$k$

Il n'a pas été prouvé qu'il est possible de trouver une classe de problèmes NP-complets avec des solutions plantées qui sont tout aussi difficiles que des problèmes arbitraires NP-complets (et même si cela est vrai, ça va être incroyablement difficile à prouver) , mais les gens savent certainement comment trouver des solutions aux problèmes -SAT d'une manière que personne ne sait actuellement comment résoudre.$k$

AJOUT: Je me rends compte maintenant que cette connexion a déjà été donnée (plus en détail) à Abadi, Allender, Broder, Feigenbaum et Hemachandra ; ils soulignent que les fonctions unidirectionnelles peuvent donner des instances dures résolues de SAT, et vice versa.

Dans un langage plus informel, l'inexistence de fonctions à sens unique montre que des énigmes vraiment difficiles ne peuvent pas exister. S'il y a un type de puzzle où quelqu'un peut proposer à la fois un puzzle et sa solution de manière algorithmique, il existe également un algorithme polynomial pour trouver une solution au puzzle. Cela me semble très contre-intuitif. Bien sûr, un écart polynomial pourrait exister; il se peut que si la création du puzzle prenait étapes, sa résolution peut prendre étapes. Cependant, mon intuition dit qu'il devrait y avoir un écart superpolynomial. O ( n 3$n$$O(n^3)$

Je vais donner une réponse courte: l'existence de problèmes apparemment difficiles, tels que FACTORING ou DISCRETE LOG, a fait croire aux théoriciens que l'OWF existe. En particulier, ils ont essayé pendant des décennies (depuis les années 1970) de trouver des algorithmes efficaces (temps polynomial probabiliste) pour de tels problèmes, mais aucune tentative n'a réussi. Ce raisonnement est très similaire à la raison pour laquelle la plupart des chercheurs pensent que P ≠ NP.

L'argument de Sasho repose sur l'éternel problème P = NP pour lequel aucun consensus n'existe actuellement.

Cependant, si nous suivons la cryptanalyse par C. Shannon du bloc ponctuel, déclassifié en 1947, c'est-à-dire: il n'y a pas d'algorithme de chiffrement mathématiquement sécurisé autre que le bloc temporel. Son argument est basé sur l'idée que, si nous avons une séquence vraiment aléatoire de nombres et pour une séquence à chiffrer, s 1 , s 2 , s 3 , … , s n , nous chiffrons comme suit:$r_1,r_2,r_3,\ldots,r_n$$s_1,s_2,s_3,\ldots,s_n$

$f(r_i,s_i) = r_i \oplus s_i = c_i$

Si la séquence est vraiment aléatoire, nous essaierions de calculer et le résultat serait alors que toutes les séquences sont équiprobables.$f^{-1}(r_i,s_i)$

Nous pourrions imiter le résultat de Shannon pour les fonctions unidirectionnelles.

La fonction est la carte et la fonction inverse est la carte f : Z / n Z → Z / n Z x Z / n Z .$f:\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}$$f:\mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$

Le hic, c'est que nous ne savons pas s'il existe des nombres vraiment aléatoires car la question équivaut au commentaire d'Einstein sur «Dieu ne joue pas aux dés».

Cependant, à toutes fins utiles, un générateur de nombres aléatoires basé sur un processus physique est considéré comme suffisamment aléatoire par les experts.

Cela dit, au moment où nous essayons d'inverser , c'est-à-dire que les nombres aléatoires ne sont plus secrets, l'inversion est triviale.$(c_i,r_i)$

De plus, cette fonction unidirectionnelle n'a pas les propriétés intéressantes de la plupart des fonctions de hachage sécurisées cryptographiquement telles que la résistance aux collisions. De plus, nous avons la situation que . Cela signifie qu'une même valeur s k est hachée à deux valeurs différentes. Et f ( r i , s i ) = f ( r j , s j ) est commun.$f(r_i,s_k)\neq f(r_j,s_k)$$s_k$$f(r_i,s_i) = f(r_j,s_j)$

Serait-ce aussi simple que de suggérer par exemple la fonction Sine?

Parce que pour une entrée et une sortie données, l'entrée peut être augmentée ou diminuée de 360 ​​degrés (ou 2 pi si vous êtes en radians), c'est plusieurs à un, donc vous ne pouvez jamais être sûr de quelle entrée vous aviez?

Dites-moi si j'ai mal compris la question.