Hispanopedia Wiki
Articulo de referencia

Función unidireccional

Problema sin resolver en informática ¿Existen las funciones unidireccionales? Más problemas sin resolver en informática En informática , una función unidireccional es aquella qu...

Hispanopedia WikiContenido en espanolLectura gratuita
Problema sin resolver en informática
¿Existen las funciones unidireccionales?
Más problemas sin resolver en informática

En informática , una función unidireccional es aquella que se puede calcular fácilmente con cualquier entrada, pero que es difícil de invertir dada la imagen de una entrada aleatoria. Aquí, "fácil" y "difícil" se entienden en el contexto de la teoría de la complejidad computacional , específicamente la teoría de problemas de tiempo polinomial . Esto no tiene nada que ver con si la función es biyectiva ; encontrar cualquier entrada con la imagen deseada se considera una inversión exitosa. (Véase la sección "  Definición teórica" ​​más adelante).

La existencia de tales funciones unidireccionales sigue siendo una conjetura abierta . Su existencia demostraría que las clases de complejidad P y NP no son iguales , resolviendo así la cuestión más importante sin resolver de la informática teórica. [ 1 ] : ej. 2.2, página 70 No se sabe que lo contrario sea cierto, es decir, la existencia de una prueba de que P  ≠  NP no implicaría directamente la existencia de funciones unidireccionales. [ 2 ]

En contextos aplicados, los términos «fácil» y «difícil» suelen interpretarse en relación con alguna entidad informática específica; normalmente, «lo suficientemente económico para los usuarios legítimos» y «excesivamente caro para cualquier agente malicioso ». En este sentido, las funciones unidireccionales son herramientas fundamentales para la criptografía , la identificación personal , la autenticación y otras aplicaciones de seguridad de datos . Si bien la existencia de funciones unidireccionales en este sentido es una conjetura abierta, existen varios candidatos que han resistido décadas de intenso escrutinio. Algunos de ellos son componentes esenciales de la mayoría de los sistemas de telecomunicaciones , comercio electrónico y banca electrónica en todo el mundo.

Definición teórica

Una función f  : {0,  1} * → {0,  1} * es unidireccional si f puede ser calculada por un algoritmo de tiempo polinomial, pero cualquier algoritmo aleatorio de tiempo polinomial no es unidireccional.F{\displaystyle F}que los intentos de calcular una pseudoinversa para f tienen éxito con una probabilidad insignificante . (El superíndice * significa cualquier número de repeticiones, véase la estrella de Kleene ). Es decir, para todos los algoritmos aleatoriosF{\displaystyle F}, todos los enteros positivos c y todos los n = longitud( x ) suficientemente grandes ,

Pr[F(F(F(incógnita)))=F(incógnita)]<norte−do,{\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}

donde la probabilidad es sobre la elección de x de la distribución uniforme discreta en {0,  1} n , y la aleatoriedad de F{\displaystyle F}. [ 3 ]

Cabe destacar que, según esta definición, la función debe ser "difícil de invertir" en el caso promedio, no en el peor de los casos . Esto difiere de gran parte de la teoría de la complejidad (por ejemplo, la NP-dureza ), donde el término "difícil" se refiere al peor de los casos. Por ello, aunque se sepa que algunas funciones candidatas a ser unidireccionales (descritas más adelante) son NP-completas , esto no implica que sean unidireccionales. Esta última propiedad se basa únicamente en la falta de algoritmos conocidos para resolver el problema.

No basta con que una función sea "con pérdida" (no biyectiva) para que sea unidireccional. En particular, la función que produce una cadena de n ceros para cualquier entrada de longitud n no es unidireccional porque es fácil encontrar una entrada que produzca la misma salida. Más precisamente: para una función que simplemente produce una cadena de ceros, un algoritmo F que produce cualquier cadena de longitud n para la entrada f ( x ) encontrará una preimagen adecuada de la salida, incluso si no es la entrada que se usó originalmente para encontrar la cadena de salida.

Una permutación unidireccional es una función unidireccional que también es una permutación; es decir, una función unidireccional biyectiva . Las permutaciones unidireccionales son una primitiva criptográfica importante , y se desconoce si su existencia está implícita en la existencia de funciones unidireccionales.

Una función unidireccional con puerta trasera o permutación con puerta trasera es un tipo especial de función unidireccional. Es difícil invertir dicha función a menos que se conozca alguna información secreta, denominada puerta trasera .

Una función hash f libre de colisiones es una función unidireccional que también es resistente a colisiones ; es decir, ningún algoritmo aleatorio de tiempo polinomial puede encontrar una colisión —valores distintos x , y tales que f ( x ) = f ( y )— con una probabilidad no despreciable. [ 4 ]

Un predicado de núcleo duro de una función unidireccional f es un predicado (es decir, un solo bit) b tal que b(x) es fácil de calcular dado x pero difícil de calcular dado solo f(x) .

Implicaciones teóricas de las funciones unidireccionales

Si f es una función unidireccional, su inversión sería un problema cuyo resultado es difícil de calcular (por definición), pero fácil de verificar (simplemente calculando f sobre ella). Por lo tanto, la existencia de una función unidireccional implica que FP  ≠ FNP , lo que a su vez implica que P ≠ NP. Sin embargo, P ≠ NP no implica la existencia de funciones unidireccionales.     

La existencia de una función unidireccional implica la existencia de muchos otros conceptos útiles, entre ellos:

Candidatos para funciones unidireccionales

A continuación se presentan varias funciones candidatas a ser unidireccionales (a abril de 2009). Evidentemente, se desconoce si estas funciones son realmente unidireccionales; sin embargo, una extensa investigación hasta el momento no ha logrado desarrollar un algoritmo de inversión eficiente para ninguna de ellas.

Multiplicación y factorización

La función f toma como entradas dos números primos p y q en notación binaria y devuelve su producto. Esta función se puede calcular "fácilmente" en tiempo O(b²) , donde b es el número total de bits de las entradas. Invertir esta función requiere encontrar los factores de un entero N dado . Los mejores algoritmos de factorización conocidos se ejecutan enO(exp⁡649b(registro⁡b)23){\displaystyle O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}tiempo, donde b es el número de bits necesarios para representar N.

Esta función se puede generalizar permitiendo que p y q varíen sobre un conjunto adecuado de semiprimos . Nótese que f no es unidireccional para enteros seleccionados aleatoriamente p , q > 1 , ya que el producto tendrá 2 como factor con una probabilidad de 3/4 (porque la probabilidad de que un p arbitrario sea impar es 1/2, y lo mismo ocurre con q , por lo que si se eligen independientemente, la probabilidad de que ambos sean impares es, por lo tanto, 1/4; de ahí que la probabilidad de que p o q sea par sea 1 − 1/4 = 3/4 ).

La función de Rabin (elevación al cuadrado modular)

La función de Rabin , [ 1 ] : 57 o elevar al cuadrado módulonorte=pagq{\displaystyle N=pq}, donde p y q son números primos, se cree que es una colección de funciones unidireccionales. Escribimos

Rabinnorte⁡(incógnita)≜incógnita2modnorte{\displaystyle \operatorname {Rabin} _ {N}(x)\triangleq x^{2}{\bmod {N}}}

para denotar el cuadrado módulo N : un miembro específico de la colección de Rabin . Se puede demostrar que extraer raíces cuadradas, es decir, invertir la función de Rabin, es computacionalmente equivalente a factorizar N (en el sentido de reducción en tiempo polinomial ). Por lo tanto, se puede probar que la colección de Rabin es unidireccional si y solo si la factorización es difícil. Esto también se cumple para el caso especial en el que p y q tienen la misma longitud de bits. El algoritmo de firma de Rabin se basa en la suposición de que esta función de Rabin es unidireccional.

exponencial y logaritmo discretos

La exponenciación modular se puede realizar en tiempo polinomial. Invertir esta función requiere calcular el logaritmo discreto . Actualmente existen varios grupos populares para los cuales no se conoce ningún algoritmo que permita calcular el logaritmo discreto subyacente en tiempo polinomial. Todos estos grupos son grupos abelianos finitos y el problema general del logaritmo discreto se puede describir de la siguiente manera.

Sea G un grupo abeliano finito de cardinalidad n . Denotemos su operación de grupo por multiplicación. Consideremos un elemento primitivo α ∈ G y otro elemento β ∈ G. El problema del logaritmo discreto consiste en encontrar el entero positivo k , donde 1 ≤ k ≤ n , tal que:

αk=α⋅α⋅…⋅α⏟ktimetromis=β{\displaystyle \alpha ^{k}=\underbrace {\alpha \cdot \alpha \cdot \ldots \cdot \alpha } _{k\;\mathrm {times} }=\beta }

El entero k que resuelve la ecuación α k = β se denomina logaritmo discreto de β en base α . Se escribe k = log α β .

Las opciones populares para el grupo G en criptografía de logaritmo discreto son los grupos cíclicos ( Z p ) × (por ejemplo , cifrado ElGamal , intercambio de claves Diffie-Hellman y el algoritmo de firma digital ) y subgrupos cíclicos de curvas elípticas sobre campos finitos ( véase criptografía de curva elíptica ).

Una curva elíptica es un conjunto de pares de elementos de un cuerpo que satisfacen y² = x³ + ax + b . Los elementos de la curva forman un grupo bajo una operación llamada "suma de puntos" (que no es lo mismo que la suma del cuerpo). La multiplicación kP de un punto P por un entero k ( es decir , una acción de grupo del grupo aditivo de los enteros) se define como la suma repetida del punto consigo mismo. Si se conocen k y P , es fácil calcular R = kP , pero si solo se conocen R y P , se supone que es difícil calcular k .

Funciones hash criptográficamente seguras

Existen varias funciones hash criptográficas de cálculo rápido, como SHA-256 . Algunas de las versiones más sencillas han sido vulneradas mediante análisis sofisticados, pero las versiones más robustas siguen ofreciendo soluciones rápidas y prácticas para el cálculo unidireccional. La mayor parte del respaldo teórico para estas funciones se centra en técnicas para contrarrestar algunos de los ataques que han tenido éxito anteriormente.

Otros candidatos

Otros candidatos para funciones unidireccionales incluyen la dificultad de la decodificación de códigos lineales aleatorios , la dificultad de ciertos problemas de retículos y el problema de la suma de subconjuntos ( criptosistema de la mochila de Naccache-Stern ).

Función universal unidireccional

Existe una función explícita f que se ha demostrado que es unidireccional, si y solo si existen funciones unidireccionales. [ 5 ] En otras palabras, si alguna función es unidireccional, entonces f también lo es . Dado que esta función fue la primera función unidireccional combinatoriamente completa que se demostró, se la conoce como la "función unidireccional universal". El problema de encontrar una función unidireccional se reduce, por lo tanto, a demostrar —quizás de forma no constructiva— que existe una función de este tipo .

También existe una función unidireccional si la complejidad de Kolmogorov acotada en tiempo polinomial es, en promedio, ligeramente difícil. Dado que la existencia de funciones unidireccionales implica que la complejidad de Kolmogorov acotada en tiempo polinomial es, en promedio, ligeramente difícil, la función es una función unidireccional universal. [ 6 ]

Véase también

Referencias

  1. 1 2 Oded Goldreich (2001). Fundamentos de criptografía: Volumen 1, Herramientas básicas ( borrador disponible en el sitio web del autor). Cambridge University Press. ISBN 0-521-79172-3Véase también wisdom.weizmann.ac.il .
  2. ↑ Goldwasser, S. y Bellare, M. «Apuntes de clase sobre criptografía». Archivado el 21 de abril de 2012 en Wayback Machine . Curso de verano sobre criptografía, MIT, 1996-2001.
  3. ↑ Muchos autores consideran esta definición como una función unidireccional fuerte. Una función unidireccional débil puede definirse de manera similar, excepto que la probabilidad de que cada adversarioF{\displaystyle F}La falta de inversión de f es notable. Sin embargo, se pueden construir funciones unidireccionales robustas a partir de funciones débiles. En términos generales, las versiones robustas y débiles de una función unidireccional son teóricamente equivalentes. Véase Fundamentos de la criptografía de Goldreich, vol.  1, cap.  2.1–2.3.
  4. ↑ Russell, A. (1995). "Condiciones necesarias y suficientes para el hash sin colisiones". Journal of Cryptology . 8 (2): 87– 99. doi : 10.1007/BF00190757 . S2CID 26046704 . 
  5. ↑ Levin, Leonid A. (enero de 2003). "El cuento de las funciones unidireccionales". Problemas de transmisión de información . 39 (39): 92– 103. arXiv : cs.CR/0012023 . doi : 10.1023/A:1023634616182 .
  6. ↑ Liu, Yanyi; Pass, Rafael (24-09-2020). "Sobre funciones unidireccionales y complejidad de Kolmogorov". arXiv : 2009.11514 [ cs.CC ].

Lecturas adicionales

  • Jonathan Katz y Yehuda Lindell (2007). Introducción a la criptografía moderna . CRC Press. ISBN 1-58488-551-3.
  • Michael Sipser (1997). Introducción a la teoría de la computación . PWS Publishing. ISBN 978-0-534-94728-6.Sección 10.6.3: Funciones unidireccionales, págs.  374 – 376.
  • Christos Papadimitriou (1993). Complejidad computacional (1.ª  ed.). Addison Wesley. ISBN 978-0-201-53082-7.Sección 12.1: Funciones unidireccionales, págs.  279 – 298.