Argumentos para la existencia de funciones unidireccionales

He leído en varios artículos que la existencia de funciones unidireccionales se cree ampliamente. ¿Alguien puede arrojar luz sobre por qué este es el caso? ¿Qué argumentos tenemos para apoyar la existencia de funciones unidireccionales?

Aquí hay un argumento de que las funciones unidireccionales deberían ser difíciles de invertir. Supongamos que hay una clase de problemas 3-SAT con soluciones plantadas que son difíciles de resolver. Considere el siguiente mapa:

donde es cualquier cadena de bits, r es una cadena de bits (puede usarlos para generar un generador de números aleatorios, o puede solicitar tantos bits aleatorios como necesite) y s es un problema de k -SAT que tiene x como una solución plantada, donde el generador de números aleatorios determina exactamente qué problema k -SAT eliges. Para invertir esta función unidireccional, debe resolver un problema k -SAT con una solución plantada.$x$$r$$s$$k$$x$$k$$k$

Este argumento muestra que invertir una función unidireccional es tan difícil como resolver problemas -SAT con soluciones plantadas. Y dado que k -SAT es un problema NP-completo, si puede descubrir cómo construir instancias difíciles con soluciones plantadas para cualquier problema NP, puede plantar soluciones en $k$$k$$k$ fórmulas -SAT.

No se ha demostrado que sea posible llegar a una clase de problemas NP-completos con soluciones plantadas que son tan difíciles como los problemas arbitrarios NP-complete (e incluso si esto es cierto, será increíblemente difícil de probar) , pero la gente definitivamente sabe cómo plantar soluciones en $k$ problemas -SAT de una manera que nadie sabe cómo resolver.

AGREGADO: ahora me doy cuenta de que esta conexión ya se había dado (con más detalle) en Abadi, Allender, Broder, Feigenbaum y Hemachandra ; Señalan que las funciones unidireccionales pueden dar instancias resueltas de SAT, y viceversa.

Poniéndolo en un lenguaje más informal, la inexistencia de funciones unidireccionales muestra que los rompecabezas realmente difíciles no pueden existir. Si hay un tipo de rompecabezas en el que alguien puede encontrar tanto un rompecabezas como su solución algorítmicamente, entonces también hay un algoritmo de tiempo polinómico para encontrar una solución al rompecabezas. Esto me parece muy intuitivo. Por supuesto, podría existir una brecha polinómica; Podría ser el caso de que si crear el rompecabezas tomara pasos, luego resolverlo podría tomar O ( n 3 ) pasos. Sin embargo, mi intuición dice que debería haber una brecha superpolinómica. $n$$O(n^3)$

Daré una respuesta breve: la existencia de problemas aparentemente difíciles, como FACTORING o DISCRETE LOG, hizo que los teóricos creyeran que OWF existe. En particular, intentaron durante décadas (desde 1970) encontrar algoritmos eficientes (tiempo polinomial probabilístico) para tales problemas, pero ningún intento tuvo éxito. Este razonamiento es muy similar al por qué la mayoría de los investigadores creen que P ≠ NP.

El argumento de Sasho se basa en el eterno problema P = NP para el que actualmente no existe consenso.

Sin embargo, si seguimos el criptoanálisis de C. Shannon de la plataforma única, desclasificada en 1947, es decir: no existe un algoritmo de cifrado matemáticamente seguro que no sea la plataforma única. Su argumento se basa en la idea de que, si tenemos una secuencia verdaderamente aleatoria de números para que se encripte alguna secuencia, s 1 , s 2 , s 3 , ... , s n , encriptamos de la siguiente manera:$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 secuencia es verdaderamente aleatoria, intentaríamos calcular $f^{-1}(r_i,s_i)$ y el resultado sería que todas las secuencias son equiprobables.

Podríamos imitar el resultado de Shannon para funciones unidireccionales.

La función es el mapa y la función inversa es el mapa f : Z / n Z → Z / n Z × Z / n $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}$ .

El problema es que no sabemos si existen números verdaderamente aleatorios, ya que la pregunta es equivalente al comentario de Einstein sobre "Dios no juega a los dados".

Sin embargo, a todos los efectos, los expertos consideran que un generador de números aleatorios basado en un proceso físico es lo suficientemente aleatorio.

$(c_i,r_i)$ , es decir, los números aleatorios ya no son secretos, la reversión es trivial.

$f(r_i,s_k)\neq f(r_j,s_k)$$s_k$$f(r_i,s_i) = f(r_j,s_j)$

¿Sería tan fácil como sugerir, por ejemplo, la función seno?

Debido a que para una entrada y salida dada, la entrada puede aumentarse o disminuirse en 360 grados (o 2 pi si le gustan los radianes) es de muchos a uno, por lo que nunca puede estar seguro de qué entrada tuvo.

No obstante, dígame si he entendido mal la pregunta.