¿Las “funciones unidireccionales” tienen aplicaciones fuera de la criptografía?

16

Una función es unidireccional si puede calcularse mediante un algoritmo de tiempo polinomial, pero para cada algoritmo de tiempo polinómico aleatorio , $f \colon \{0, 1\}^* \to \{0, 1\}^*$ $f$ $A$

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

para cada polinomio y suficientemente grande , suponiendo que se elige de manera uniforme desde . La probabilidad se toma sobre la elección de y la aleatoriedad de . $p(n)$ $n$ $x$ $\{ 0, 1 \}^n$ $x$ $A$

Entonces ... ¿tienen "One Way Functions" aplicaciones fuera de la criptografía? Si es así, ¿qué son?

cc.complexity-theory cr.crypto-security one-way-function Tarek Radwan
fuente

1

Corrigí las fórmulas al formulario LaTeX, pero parece haber un problema técnico en MathJax, ya que muestra las ecuaciones correctamente, pero muestra el error `Error '. Creo que se corregirá pronto ...

MS Dousti

1

Para mí, esto se parece más a un error en SE. Por alguna razón, no parece reconocer un doble \ como una secuencia de escape que debería generar un solo \, que luego sería procesado por MathJax.

Jukka Suomela

2

En la publicación es

, pero necesita un soporte de cierre adicional ")".

P r [f (A (f (x), 1^{n}) = x] < 1 / p (n)

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

Oleksandr Bondarenko

2

@Sadeq y Jukka: Esto podría estar relacionado con un error recientemente corregido en SE: meta.math.stackexchange.com/questions/1115/…

Tsuyoshi Ito

@ Tsuyoshi: ¡Gracias por el comentario informativo!

MS Dousti

23

Las funciones unidireccionales se muestran de manera crucial en el resultado de las pruebas naturales de Razborov-Rudich. No consideraría los límites inferiores del circuito como parte de la "criptografía", por lo que tal vez esto se ajuste a sus criterios.

mikero
fuente

11

Las funciones unidireccionales también aparecieron en algunas discusiones sobre la conjetura del isomorfismo de Berman-Hartmanis . Joseph y Young conjeturaron que si existían funciones unidireccionales, entonces la conjetura del isomorfismo falla (unidireccional contra adversarios deterministas, no contra adversarios probabilísticos, pero con suerte eso es lo suficientemente cercano para los propósitos de esta pregunta). John Rogers dio un mundo relativizado donde la conjetura de Joseph-Young falló (es decir, donde existen funciones unidireccionales pero la conjetura del isomorfismo es válida). Pero hasta donde yo sé, la conjetura de JY sigue siendo una de las principales pruebas técnicas que llevan a las personas a pensar que la Conjetura de isomorfismo es falsa (si piensan eso).

La esencia de la idea de Joseph y Young es que si es una función unidireccional, entonces es -completo pero "no debería" ser isomorfo a SAT. $f$ $f(SAT)$ $NP$

Joshua Grochow
fuente

8

Sí, una tabla hash o un mapa hash requieren una función unidireccional. También la detección de duplicados (vea esto y esto ) se puede hacer de manera muy eficiente utilizando funciones unidireccionales. Ambos casos requieren funciones unidireccionales "buenas" (con pocas posibilidades de colisión), mientras que generalmente no se requiere fuerza criptográfica .

diente filoso
fuente

Sí, las funciones hash son muy utilizadas para las tablas hash.

Gamlor

2

Su respuesta no es correcta. Lo que se requiere para la detección de duplicados es la resistencia a la colisión, que no es lo mismo que ser unidireccional. Vea la definición en la pregunta original para una definición cuidadosa de unidireccional. A veces, las personas usan libremente la frase "hash unidireccional" como sinónimo de la función hash criptográfica, pero eso es muy engañoso, ya que en muchas aplicaciones no es la propiedad "unidireccional" lo que es importante, sino más bien la resistencia a la colisión ( como en detección duplicada) o comportamiento como un oráculo aleatorio (como en hashing).

DW

6

Hay muchos resultados de "dureza criptográfica" (solo Google esta frase) para problemas de aprendizaje. Estos son resultados de dureza suponiendo que existan funciones unidireccionales.

Dana Moshkovitz
fuente

44

¿Me puede dar una definición precisa de "dureza criptográfica"?

Tarek Radwan

1

Los resultados de dureza estándar suponen que P no es igual a NP; Si este es el caso, entonces el problema lleva tiempo superpolinomial. Los resultados de "dureza criptográfica" suponen algo más fuerte: que existen funciones unidireccionales. Esta suposición implica (y es más fuerte que) la dureza promedio de algunos problemas.

Dana Moshkovitz

5

Las funciones unidireccionales tienen una aplicación en la complejidad de Kolmogorov:

$x$ $y$

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

Si existen funciones unidireccionales, entonces la simetría de la conjetura de información limitada en el tiempo polinomial es falsa.

L. Longpre y S. Mocas. Simetría de información y funciones unidireccionales. Cartas de procesamiento de información, 46 (2): 95 {100, 1993

L. Longpre y O. Watanabe. Sobre la simetría de la información y la invertibilidad del tiempo polinómico Información y cálculo, 121 (1): 14 {22, 1995

Mohammad Al-Turkistany
fuente

¿Las “funciones unidireccionales” tienen aplicaciones fuera de la criptografía?

Respuestas: