¿Existen funciones unidireccionales?
En informática , una función unidireccional es una función que es fácil de calcular en cada entrada, pero difícil de invertir dada la imagen de una entrada aleatoria. Aquí, "fácil" y "difícil" deben entenderse en el sentido de la teoría de la complejidad computacional , específicamente la teoría de los problemas de tiempo polinomial . No ser uno a uno no se considera suficiente para que una función se llame unidireccional (consulte la definición teórica a continuación).
La existencia de tales funciones unidireccionales es todavía 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 "bastante barato para los usuarios legítimos" y "prohibitivamente caro para cualquier agente malicioso ". [ cita necesaria ] Las funciones unidireccionales, en este sentido, 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 también es una conjetura abierta, hay varios candidatos que han resistido décadas de intenso escrutinio. Algunos de ellos son ingredientes esenciales de la mayoría de los sistemas de telecomunicaciones , comercio electrónico y banca electrónica en todo el mundo.
Una función f : {0, 1} * → {0, 1} * es unidireccional si f puede calcularse mediante un algoritmo de tiempo polinomial, pero cualquier algoritmo aleatorio de tiempo polinomial que intente calcular una pseudoinversa para f tiene éxito con probabilidad insignificante . (El superíndice * significa cualquier número de repeticiones, consulte la estrella de Kleene ). Es decir, para todos los algoritmos aleatorios , todos los enteros positivos c y todos los n = longitud ( x ) suficientemente grandes,
donde la probabilidad está sobre la elección de x de la distribución uniforme discreta en {0, 1} n y la aleatoriedad de . [3]
Tenga en cuenta que, según esta definición, la función debe ser "difícil de invertir" en el caso promedio, en lugar del peor de los casos . Esto es diferente de gran parte de la teoría de la complejidad (por ejemplo, dureza NP ), donde el término "duro" se refiere al peor de los casos. Es por eso que incluso si se sabe que algunos candidatos para funciones unidireccionales (descritas a continuación) son NP-completos , eso no implica que sean unidireccionales. Esta última propiedad sólo se basa en la falta de algoritmos conocidos para resolver el problema.
No es suficiente hacer que una función tenga "pérdidas" (no uno a uno) para tener una función unidireccional. En particular, la función que genera la cadena de n ceros en cualquier entrada de longitud n no es una función unidireccional porque es fácil encontrar una entrada que dé como resultado la misma salida. Más precisamente: para una función que simplemente genera una cadena de ceros, un algoritmo F que simplemente genera cualquier cadena de longitud n en 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 que es biyectiva . Las permutaciones unidireccionales son una primitiva criptográfica importante y no se sabe si su existencia está implicada por la existencia de funciones unidireccionales.
Una función unidireccional de trampilla o una permutación de trampilla es un tipo especial de función unidireccional. Esta función es difícil de invertir a menos que se conozca alguna información secreta, llamada trampilla .
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 de tiempo polinómico aleatorio puede encontrar una colisión (valores distintos x , y tales que f ( x ) = f ( y )) con una probabilidad no despreciable. [4]
Si f es una función unidireccional, entonces la inversión de f sería un problema cuya salida es difícil de calcular (por definición) pero fácil de verificar (simplemente calculando f en ella). Así, 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:
Los siguientes son varios candidatos para funciones unidireccionales (a abril de 2009). Claramente, no se sabe si estas funciones son realmente unidireccionales; pero hasta ahora una investigación exhaustiva no ha logrado producir un algoritmo de inversión eficiente para ninguno de ellos. [ cita necesaria ]
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 2 ) , donde b es el número total de bits de las entradas. Invertir esta función requiere encontrar los factores de un número entero N dado . Los mejores algoritmos de factorización conocidos se ejecutan en el tiempo, donde b es el número de bits necesarios para representar N.
Esta función se puede generalizar permitiendo que p y q se extiendan sobre un conjunto adecuado de semiprimos . Tenga en cuenta que f no es unidireccional para enteros p , q > 1 seleccionados aleatoriamente , ya que el producto tendrá 2 como factor con probabilidad 3/4 (porque la probabilidad de que un p arbitrario sea impar es 1/2, y lo mismo para q , por lo que si se eligen de forma independiente, la probabilidad de que ambos sean impares es, por lo tanto, 1/4; por lo tanto, la probabilidad de que p o q sean pares es 1 − 1/4 = 3/4 ).
Se cree que la función Rabin , [1] : 57 o módulo cuadrado , donde p y q son números primos, es una colección de funciones unidireccionales. Nosotros escribimos
para denotar módulo de cuadratura N : un miembro específico de la colección 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 del tiempo polinomial ). Por tanto, se puede demostrar que la colección de Rabin es unidireccional si y sólo si la factorización es difícil. Esto también es válido para el caso especial en el que p y q tienen la misma longitud de bits. El criptosistema Rabin se basa en el supuesto de que esta función Rabin es unidireccional.
La exponenciación modular se puede realizar en tiempo polinomial. Para invertir esta función es necesario calcular el logaritmo discreto . Actualmente existen varios grupos populares para los cuales no se conoce ningún algoritmo para calcular el logaritmo discreto subyacente en tiempo polinomial. Todos estos grupos son grupos abelianos finitos y el problema general del logaritmo discreto puede describirse así.
Sea G un grupo abeliano finito de cardinalidad n . Denota su operación de grupo por multiplicación. Considere 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:
El número 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 logaritmos discretos son los grupos cíclicos ( Z p ) × (por ejemplo , cifrado ElGamal , intercambio de claves Diffie-Hellman y algoritmo de firma digital ) y subgrupos cíclicos de curvas elípticas sobre campos finitos ( ver criptografía de curva elíptica ). ).
Una curva elíptica es un conjunto de pares de elementos de un campo que satisfacen y 2 = x 3 + 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 operación de suma del campo). La multiplicación kP de un punto P por un número entero k ( es decir , una acción grupal del grupo aditivo de los números enteros) se define como la suma repetida del punto a sí mismo. Si se conocen k y P , es fácil calcular R = kP , pero si sólo se conocen R y P , se supone que es difícil calcular k .
Hay una serie de funciones hash criptográficas que son rápidas de calcular, como SHA 256 . Algunas de las versiones más simples han caído en manos de análisis sofisticados, pero las versiones más potentes siguen ofreciendo soluciones rápidas y prácticas para el cálculo unidireccional. La mayor parte del apoyo teórico para las funciones son más técnicas para frustrar algunos de los ataques exitosos anteriormente.
Otros candidatos para funciones unidireccionales incluyen la dureza de la decodificación de códigos lineales aleatorios , la dureza de ciertos problemas de red y el problema de la suma de subconjuntos ( criptosistema de mochila Naccache-Stern ).
Existe una función explícita f que se ha demostrado que es unidireccional, si y sólo si existen funciones unidireccionales. [5] En otras palabras, si cualquier función es unidireccional, entonces también lo es f . Dado que esta función fue la primera función combinatoria unidireccional completa que se demostró, se la conoce como "función unidireccional universal". Por tanto, el problema de encontrar una función unidireccional se reduce a demostrar (quizás de forma no constructiva) que dicha función existe.
![{\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcabaaa7ff3f11fc73cf28f81878880173d1f3da)
![{\displaystyle O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fce9dac980e9d4ef0d5ed82aa0172be61d7b57b2)
{{cite journal}}: Citar diario requiere |journal=( ayuda )