En informática , una función unidireccional es una función que es fácil de calcular para 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 problemas de tiempo polinomial . No ser uno a uno no se considera suficiente para que una función se denomine unidireccional (ver la definición teórica, a continuación).
La existencia de tales funciones unidireccionales es todavía una conjetura abierta . Su existencia probarí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 si la inversa es cierta, 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; típicamente "suficientemente barata para los usuarios legítimos" y "prohibitivamente cara para cualquier agente malicioso ". [ cita requerida ] 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 se puede calcular mediante un algoritmo de tiempo polinomial, pero cualquier algoritmo aleatorio de tiempo polinomial que intente calcular una pseudoinversa para f tiene éxito con una probabilidad despreciable . (El superíndice * significa cualquier número de repeticiones, véase la estrella de Kleene ). Es decir, para todos los algoritmos aleatorios , todos los enteros positivos c y todos los suficientemente grandes n = length( x ),
donde la probabilidad es sobre la elección de x de la distribución uniforme discreta en {0, 1} n , y la aleatoriedad de . [3]
Nótese que, según esta definición, la función debe ser "difícil de invertir" en el sentido del caso promedio, en lugar del peor de los casos . Esto es diferente de gran parte de la teoría de la complejidad (por ejemplo, NP-hardness ), donde el término "hard" 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 , no implica su unidireccionalidad. La última propiedad solo se basa en la falta de algoritmos conocidos para resolver el problema.
No basta con hacer que una función sea "con pérdidas" (no uno a uno) para que tenga 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 genere 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 utilizó 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á implícita en la existencia de funciones unidireccionales.
Una función unidireccional de trampilla o permutación de trampilla es un tipo especial de función unidireccional. Es difícil invertir una función de este tipo a menos que se conozca cierta información secreta, llamada trampilla .
Una función hash libre de colisiones f es una función unidireccional que también es resistente a colisiones ; es decir, ningún algoritmo de tiempo polinomial 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 cuyo resultado es difícil de calcular (por definición) pero fácil de comprobar (simplemente calculando f sobre él). 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:
A continuación se enumeran varios candidatos a funciones unidireccionales (a fecha de abril de 2009). Evidentemente, no se sabe si estas funciones son realmente unidireccionales, pero hasta el momento se han realizado investigaciones exhaustivas que no han logrado producir un algoritmo inversor eficiente para ninguna de ellas. [ cita requerida ]
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. Para invertir esta función es necesario encontrar los factores de un entero dado N . Los mejores algoritmos de factorización conocidos se ejecutan en tiempo, donde b es el número de bits necesarios para representar N .
Esta función se puede generalizar permitiendo que p y q oscilen sobre un conjunto adecuado de semiprimos . Nótese que f no es unidireccional para números enteros seleccionados aleatoriamente p , q > 1 , 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 independientemente, 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 primos, es una colección de funciones unidireccionales. Escribimos
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 demostrar que la colección de Rabin es unidireccional si y solo 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 de Rabin se basa en el supuesto de que esta función de 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, hay varios grupos populares para los que 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 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. Considérese un elemento primitivo α ∈ G y otro elemento β ∈ G . El problema del logaritmo discreto consiste en hallar el entero positivo k , donde 1 ≤ k ≤ n , tal que:
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 logarítmica discreta 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 ( ver criptografía de curva elíptica ).
Una curva elíptica es un conjunto de pares de elementos de un cuerpo que satisface 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 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 a sí 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 .
Hay varias funciones hash criptográficas que se calculan rápidamente, como SHA 256. Algunas de las versiones más simples han caído en el olvido, pero las versiones más sólidas siguen ofreciendo soluciones rápidas y prácticas para el cálculo unidireccional. La mayor parte del respaldo teórico de las funciones son más bien técnicas para frustrar algunos de los ataques que tuvieron éxito anteriormente.
Otros candidatos para funciones unidireccionales incluyen la dificultad de la decodificación de códigos lineales aleatorios , la dificultad de ciertos problemas de red y el problema de la suma de subconjuntos ( criptosistema de mochila de Naccache-Stern ).
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 cualquier función es unidireccional, entonces también lo es f . Dado que esta función fue la primera función unidireccional combinatoria 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 manera no constructiva) que existe una de esas funciones.
También existe una función unidireccional si la complejidad de Kolmogorov acotada en el tiempo polinomial es levemente difícil en promedio. Dado que la existencia de funciones unidireccionales implica que la complejidad de Kolmogorov acotada en el tiempo polinomial es levemente difícil en promedio, la función es una función unidireccional universal. [6]
![{\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)
