💻 computer science

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$ , Generically)

Este artículo introduce una transformación genérica que convierte PRF débiles en PRF fuertes con un sobrecoste de profundidad mínimo, permitiendo la construcción de PRF computables en $\mathsf{NC}^1$ a partir de supuestos estándar incluyendo LWE, LPN y CDH, resolviendo así problemas abiertos de larga data en la criptografía de baja profundidad.

Autores originales: Youlong Ding, Aayush Jain, Ilan Komargodski

Publicado 2026-08-27

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Youlong Ding, Aayush Jain, Ilan Komargodski

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el mundo digital, la seguridad a menudo depende de un tipo especial de herramienta matemática llamada función pseudialeatoria. Imagine una máquina que toma un código secreto y un fragmento de datos, y luego escupe una cadena de números que parece completamente aleatoria para cualquiera que la observe. Si la máquina funciona correctamente, nadie puede notar la diferencia entre su salida y una secuencia verdaderamente aleatoria, incluso si han visto a la máquina trabajar muchas veces antes. Estas herramientas son las cerraduras y llaves invisibles que protegen todo, desde la banca en línea hasta los mensajes privados. Durante décadas, los investigadores han intentado construir estas máquinas para que funcionen lo más rápido posible, específicamente haciendo que operen en muy pocos pasos. En el lenguaje de la informática, esto significa construirlas con un circuito muy poco profundo, permitiendo que el cálculo ocurra casi instantáneamente en los procesadores modernos. Cuanto más rápidas y simples sean estas herramientas, más eficientemente podrán utilizarse en sistemas complejos como la votación segura o el intercambio de datos privados.

Durante mucho tiempo, hubo una brecha persistente en nuestra capacidad para construir estas máquinas rápidas y poco profundas. Sabíamos cómo crearlas utilizando supuestos matemáticos muy fuertes y complejos, pero aquellos requerían circuitos profundos y lentos. Por el contrario, podíamos construir circuitos poco profundos, pero solo si dependíamos de supuestos más débiles y menos probados o de estructuras matemáticas muy específicas y rígidas. Era como tener una llave que abría una puerta pero era demasiado pesada para cargar, o una llave que era ligera pero solo encajaba en una cerradura única y extraña. El objetivo era encontrar la manera de hacer una llave ligera que pudiera abrir cualquier puerta, utilizando solo las cerraduras más estándar y fiables disponibles. Este desafío ha permanecido durante casi treinta años, limitando qué tan eficientemente podíamos asegurar el mundo digital.

Un equipo de investigadores ha cerrado ahora esta brecha con un nuevo método general que transforma una herramienta más débil y fácil de construir en una fuerte y segura sin ralentizarla. Su trabajo, publicado en un artículo titulado "Pseudorandom Functions in NC1 from LWE/LPN/CDH", demuestra que es posible construir estas máquinas rápidas y poco profundas utilizando tres de los supuestos más fundamentales y ampliamente confiables de la criptografía. Los investigadores lograron esto refinando una idea antigua llamada construcción GGM, que construye una función compleja recorriendo un árbol de cálculos más pequeños. La forma tradicional de hacer esto era como caminar por un pasillo largo donde cada paso requería la misma cantidad de esfuerzo, haciendo que el viaje total fuera largo y lento. El nuevo método cambia la forma del pasillo. A medida que el proceso se adentra más en el árbol, la cantidad de trabajo requerido en cada paso disminuye geométricamente. Los primeros pasos son pesados, pero los pasos subsiguientes se vuelven cada vez más ligeros, tan rápidamente que el esfuerzo total permanece pequeño. Esta técnica de "atenuación" permite a los investigadores mantener todo el proceso dentro de los límites de un circuito rápido y poco profundo.

Para probar que este nuevo método funciona, el equipo lo aplicó a tres problemas matemáticos específicos que son conocidos por ser difíciles de resolver. El primero es el problema de Aprendizaje con Errores (Learning With Errors), que implica encontrar un patrón oculto en un conjunto de datos con ruido. Los intentos previos para construir máquinas rápidas a partir de este problema requerían una versión más compleja y específica de la matemática que utilizaba números muy grandes. El nuevo trabajo muestra que la versión estándar, con números mucho más pequeños, es suficiente. El segundo problema, Aprendizaje de Paridad con Ruido (Learning Parity with Noise), trata sobre encontrar un patrón oculto en un flujo de bits que ha sido alterado aleatoriamente. Los investigadores demostraron que su método funciona con la versión estándar de este problema, eliminando la necesidad de las versiones especializadas y estructuradas que se requerían anteriormente. El tercer problema, el supuesto de Diffie-Hellman Computacional (Computational Diffie-Hellman), una piedra angular de la seguridad moderna de Internet utilizada para intercambiar claves secretas. Durante décadas, la única forma conocida de construir máquinas rápidas a partir de este supuesto dependía de una versión más fuerte y restrictiva del problema. La nueva construcción prueba que la versión estándar es suficiente.

La importancia de este trabajo radica en su generalidad y en su dependencia de supuestos estándar. Al demostrar que una herramienta débil y poco profunda puede actualizarse a una fuerte y segura sin añadir profundidad, los investigadores han desbloqueado la capacidad de construir funciones rápidas y seguras a partir de los problemas matemáticos más básicos y mejor estudiados. Esto resuelve varias cuestiones de larga data y proporciona un plano nuevo y flexible para futuros sistemas criptográficos. Los investigadores no solo sugirieron que esto podría ser posible; proporcionaron una construcción concreta, paso a paso, y una prueba rigurosa de que funciona. Demostraron que la profundidad de la máquina resultante es esencialmente la misma que la profundidad de la herramienta inicial, preservando la ventaja de velocidad mientras se gana la seguridad necesaria.

Este logro significa que, por primera vez, podemos construir estas herramientas de seguridad esenciales utilizando los fundamentos matemáticos más comunes y confiables, sin sacrificar la velocidad. Elimina la necesidad de variantes especializadas y complejas de estos problemas que anteriormente se pensaba que eran necesarias para la eficiencia. El resultado es una base más robusta y versátil para la seguridad digital del futuro, permitiendo métodos de cifrado más rápidos y eficientes que pueden desplegarse en una amplia gama de tecnologías. El trabajo constituye una prueba definitiva de que la barrera entre las herramientas débiles y rápidas y las herramientas fuertes y rápidas se ha roto, abriendo la puerta a una nueva era de diseño criptográfico eficiente.

Resumen Técnico: Funciones Pseudorandom en NC1 a partir de LWE/LPN/CDH

1. Planteamiento del Problema

La construcción de Funciones Pseudorandom (PRFs) con baja complejidad paralela (específicamente dentro de la clase NC1, computable mediante circuitos de profundidad logarítmica y tamaño polinomial) ha sido un problema abierto de larga data en criptografía. Si bien las PRFs pueden construirse genéricamente a partir de Generadores de Números Pseudorandom (PRGs) mediante la transformación de Goldreich-Goldwasser-Micali (GGM), este método es inherentemente secuencial. Incluso si el PRG subyacente es computable en profundidad logarítmica, la PRF resultante requiere una profundidad $\omega(\log n)$ , situándose fuera de NC1.

Antes de este trabajo, las PRFs computables en NC1 eran escasas y dependían de estructuras algebraicas altamente específicas o supuestos fuertes:

Naor-Reingold (1997, 2004): Construyeron PRFs en $TC_0 \subseteq NC1$ a partir de Decisional Diffie-Hellman (DDH) y factorización.
Banerjee-Peikert-Rosen (2012): Construyeron PRFs en $TC_0$ a partir de Ring-LWE, pero requirieron una relación módulo-ruido superpolinomial.
Ding-Jain-Komargodski (2025): Construyeron PRFs a partir de variantes estructuradas de Learning Parity with Noise (LPN), tales como SeededLPN o Ring-LPN.

El desafío central es lograr PRFs computables en NC1 a partir de supuestos estándar (LWE con relación módulo-ruido polinomial, LPN estándar y Computational Diffie-Hellman) sin depender de variantes estructuradas o parámetros superpolinomiales.

2. Metodología

El artículo introduce un enfoque de dos vertientes: una transformación genérica que preserva la profundidad de Funciones Pseudorandom Débiles (WPRFs) a Funciones Pseudorandom Fuertes (PRFs), y nuevas construcciones de WPRFs (o sintetizadores) con eficiencia de profundidad a partir de supuestos estándar.

2.1 Tapering-GGM: Una Transformación Genérica

Los autores proponen una novedosa adaptación de la construcción de árbol GGM, denominada Tapering-GGM, que eleva una WPRF a una PRF fuerte preservando la profundidad del circuito de evaluación.

El Mecanismo de Atenuación (Tapering): En un árbol GGM estándar, el tamaño del estado permanece constante y la profundidad se acumula linealmente con el número de niveles del árbol ( $\ell \cdot d_{WPRF}$ ). En Tapering-GGM, el tamaño del estado se reduce geomététicamente en cada nivel. Si el parámetro de seguridad en el nivel $i$ es $\lambda^{(i)}$ , los autores definen $\lambda^{(i)} = \lambda^{2^{-i+1}}$ . En consecuencia, la profundidad de la llamada a la WPRF en el nivel $i$ , denotada $d(\lambda^{(i)})$ , disminuye geométricamente.
Análisis de Profundidad: Si la WPRF base tiene profundidad $d(\lambda) = \Theta(\log \lambda)$ , la profundidad total de la construcción Tapering-GGM es:
$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$
Esta decaimiento geométrico asegura que la profundidad total sea $O(d(\lambda))$ , manteniendo la construcción dentro de NC1 si la WPRF de entrada está en NC1.
Desafíos de Seguridad y Soluciones:
- Desafío: A medida que el árbol se profundiza, el parámetro de seguridad $\lambda^{(i)}$ se vuelve pequeño (sub-polinomial), lo que podría romper la seguridad computacional de la WPRF subyacente.
- Solución 1 (Hashing): La entrada es primero procesada mediante una función de hash de independencia por pares. Esto asegura que, con alta probabilidad, las consultas del adversario sean "fragmentadas" (mapeadas a rutas distintas) dentro de los primeros $O(\log_\Delta q)$ niveles, donde el parámetro de seguridad aún es polinomial.
- Solución 2 (Uniformidad de Clave): Para los niveles por debajo del punto de fragmentación, la construcción depende de la seguridad informacional. Los autores requieren que la WPRF sea clave-uniforme (1-independiente por claves). Si el estado en el nivel de fragmentación es pseudorandom, la composición subsecuente de transformaciones clave-uniformes mapea este estado a una salida perfectamente uniforme, independientemente de la dureza computacional de las WPRFs de niveles inferiores.

2.2 Construcciones de WPRF con Eficiencia de Profundidad

Los autores instancian el marco de Tapering-GGM con nuevas construcciones de WPRF a partir de supuestos estándar:

A partir de LWE (Learning With Errors):
- Los autores construyen la primera WPRF en NC1 a partir de LWE estándar con una relación módulo-ruido polinomial ( $\alpha = n^{-\epsilon}$ ).
- Herramienta Técnica Clave: Un Muestreador Gaussiano Redondeado computable en profundidad $O(\text{poly}(\log \log \lambda))$ . Aproximan la transformada de Box-Muller utilizando aproximaciones polinomiales de baja profundidad para $\ln$ , $\cos$ e iteración de Newton para raíces cuadradas.
- Construcción: Emplean un paradigma de encadenamiento (inspirado en Kim [Kim20]). La construcción computa productos internos de LWE enmascarados capa por capa. Los bits de orden superior de la salida de una capa determinan la muestra de la distribución de error para la siguiente capa. La acotación del muestreador de error asegura la estabilidad, permitiendo que la prueba de seguridad proceda mediante híbridos.
A partir de LPN (Learning Parity with Noise):
- Los autores aprovechan un resultado reciente de Ding, Jain y Komargodski [DJK25] que proporciona WPRFs en NC1 a partir de LPN estándar (ruido de inverso polinomial arbitrario).
- Al combinar esto con Tapering-GGM, obtienen la primera PRF en NC1 a partir de LPN estándar, eliminando la necesidad de variantes estructuradas (ej. Ring-LPN).
A partir de CDH (Computational Diffie-Hellman):
- Los autores observan que Tapering-GGM requiere en realidad una primitiva más débil que una WPRF: un Sintetizador (donde el conjunto de entradas está oculto para el adversario).
- Instancian la transformación utilizando la construcción de sintetizador de Naor-Reingold [NR95, NR99], la cual es computable en NC1 bajo el supuesto CDH. Esto produce la primera PRF en NC1 a partir de CDH, mejorando las construcciones previas basadas en DDH.

3. Contribuciones Clave

Transformación Genérica de Preservación de Profundidad: Una transformación de caja negra que convierte cualquier WPRF (o sintetizador) computable en profundidad $d(\lambda) = \Omega(\log \lambda)$ en una PRF fuerte computable en profundidad $O(d(\lambda))$ . Esto resuelve la barrera genérica que impedía las PRFs en NC1 a partir de supuestos estándar.
PRFs en NC1 desde LWE Estándar: La primera construcción de PRFs en NC1 a partir de LWE con una relación módulo-ruido polinomial ( $\alpha = n^{-\epsilon}$ ), resolviendo un problema abierto planteado explícitamente en las notas de clase de Vaikuntanathan. Esto depende de la dureza de GapSVP con factores de aproximación polinomiales.
PRFs en NC1 desde LPN Estándar: La primera construcción de PRFs en NC1 a partir del supuesto LPN estándar, eliminando la necesidad de variantes estructuradas como Ring-LPN.
PRFs en NC1 desde CDH: La primera construcción de PRFs en NC1 a partir del supuesto Computational Diffie-Hellman, mejorando el resultado de 30 años de Naor-Reingold que dependía de Decisional Diffie-Hellman (DDH) más fuerte.
Muestreador Gaussiano de Baja Profundidad: Un novedoso circuito determinista para muestrear errores gaussianos redondeados en profundidad $O(\text{poly}(\log \log \lambda))$ , que es un componente crítico para la WPRF basada en LWE.

4. Resultados

El artículo establece los siguientes resultados concretos:

Teorema: Si existen WPRFs en NC1, entonces existen PRFs en NC1.
Corolario (LWE): Asumiendo que el supuesto LWE se cumple para una relación ruido-módulo $\alpha = n^{-\epsilon}$ , existen PRFs en NC1.
Corolario (LPN): Asumiendo que el supuesto LPN se cumple para una probabilidad de ruido $\mu = n^{-\epsilon}$ , existen PRFs en NC1.
Corolario (CDH): Asumiendo que el supuesto CDH se cumple, existen PRFs en NC1.
Corolario (GapSVP): Asumiendo que GapSVP es difícil de aproximar dentro de un factor $\tilde{O}(n^{1+\epsilon})$ , existen PRFs en NC1.

5. Significancia

El artículo afirma resolver varios problemas abiertos de larga data en la complejidad de los primitivos criptográficos. Al desacoplar la profundidad de la evaluación de la PRF de la naturaleza secuencial de la transformación GGM, los autores demuestran que se pueden construir PRFs fuertes a partir de una amplia gama de supuestos estándar sin sacrificar la eficiencia paralela.

Específicamente, el trabajo:

Elimina la dependencia de Ring-LWE y parámetros superpolinomiales para las PRFs en NC1, pasando a LWE estándar con parámetros polinomiales.
Elimina la dependencia de variantes de LPN estructurado, pasando a LPN estándar.
Debilita el supuesto de dureza para las PRFs basadas en CDH de DDH a CDH.
Provee un marco genérico (Tapering-GGM) que puede elevar cualquier candidato de WPRF de log-profundidad existente (ej. [ABG+14], [AR16]) en una PRF de log-profundidad, siempre que el supuesto subyacente se cumpla.

Los autores posicionan este trabajo como un paso fundamental para entender la complejidad paralela de la criptografía, con implicaciones para protocolos de computación segura, teoría del aprendizaje (vía las conexiones PRF-versus-learning) y metacomplejidad.