Función unidireccional en criptografía: definición, tipos y usos

Idea formal y propiedades

Formalmente, una función unidireccional es una familia de funciones computables en tiempo polinómico para la cual cualquier algoritmo probabilístico de tiempo polinómico solo consigue hallar una preimagen con probabilidad despreciable (sobre entradas elegidas uniformemente). Entre las propiedades que suelen destacarse están:

• Cálculo directo eficiente: f(x) es fácil de calcular para todas las entradas permitidas.
• Dificultad media de invertir: ningún algoritmo eficiente encuentra de forma fiable x a partir de f(x) sobre entradas elegidas al azar.
• Seguridad asintótica: la dificultad se expresa como un tiempo de ejecución que crece con el tamaño de la entrada; en la práctica importan parámetros concretos.

Tipos y nociones relacionadas

Una refinación útil es la función unidireccional con trampilla, que resulta fácil de invertir para quien posee una información secreta de trampilla (por ejemplo, el mapeo RSA x ↦ x^e mod N cuando se conoce el exponente privado). Las funciones hash criptográficas suelen diseñarse para comportarse como funciones unidireccionales (resistencia a la preimagen), aunque no estén probadas como tales. Otros conceptos incluyen las funciones unidireccionales fuertes y débiles y los bits hard-core, que son bits de información concretos que siguen siendo difíciles de predecir incluso si se conoce f(x).

Usos e importancia

Las funciones unidireccionales son fundamentales: permiten el hash de contraseñas, los resúmenes de mensajes, los esquemas de compromiso, los generadores pseudorrandom y sustentan el cifrado de clave pública y las firmas digitales cuando se complementan con trampillas. Su existencia asumida permite construir muchos primitivos de nivel superior usados en comunicación segura, autenticación e integridad de datos.

Historia, supuestos y cuestiones abiertas

La existencia de funciones unidireccionales verdaderas es una cuestión abierta en la informática teórica: aunque muchas construcciones candidatas gozan de amplia confianza (factorización de enteros, logaritmo discreto y familias modernas de hash), ninguna está demostrada como irrompible. Se sabe que si existen funciones unidireccionales, entonces P ≠ NP, de modo que su existencia tiene conexiones profundas con la teoría de la complejidad. Por ello, los criptógrafos diseñan sistemas con elecciones de parámetros conservadoras y permanecen atentos a nuevos algoritmos y avances en la computación.