Non-Trivial Zero-Knowledge Implies One-Way Functions

1. El Problema y el Contexto

La criptografía moderna se basa en gran medida en la existencia de Funciones de Un Solo Sentido (OWF). Una pregunta fundamental en la teoría de la complejidad criptográfica, iniciada por Ostrovsky y Wigderson, es: ¿Cuáles son las suposiciones mínimas necesarias para construir sistemas de prueba de conocimiento cero (ZK)?

Trabajos anteriores establecieron que si $NP$ es difícil en promedio, la existencia de ZK para $NP$ implica la existencia de OWF. Recientemente, Hirahara y Nanashima (2024) demostraron que incluso la dureza en el peor caso de $NP$ (específicamente $NP \not\subseteq ioP/poly$) es suficiente para derivar OWF a partir de ZK, pero solo si los errores del protocolo son despreciables (negligibles).

La Brecha:
El artículo aborda un vacío fundamental: ¿Qué sucede si permitimos protocolos ZK con errores no despreciables (grandes)?

• Un protocolo ZK se considera "trivial" si la suma de sus errores de completitud ($\epsilon_c$), sonidoza ($\epsilon_s$) y conocimiento cero ($\epsilon_{zk}$) es $\ge 1$. Tales protocolos pueden construirse sin ninguna suposición criptográfica.
• Un protocolo es "no trivial" si $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1 - 1/p(n)$ para algún polinomio $p$.
• Pregunta central: ¿La existencia de protocolos ZK no triviales (con errores grandes pero no triviales) implica la existencia de OWF? Las técnicas anteriores fallaban en este régimen de "alto error".

2. Metodología y Técnicas Clave

Los autores desarrollan nuevas técnicas para superar las barreras de los trabajos previos (como [OW93] y [CHK25]), que dependían de que la suma de errores fuera estrictamente menor que 1 de una manera muy específica (ej. $\epsilon_s + 2\epsilon_{zk} < 1$).

A. Repetición y Muestreo (Para NIZK)

Para el caso de Conocimiento Cero No Interactivo (NIZK), los autores proponen un algoritmo de decisión que utiliza la Extrapolación Universal (UE) (posible si no existen OWF).

• El problema anterior: En protocolos con alto error, el simulador podría generar pruebas "malas" (que no son aceptadas) con una frecuencia que anula la ventaja del algoritmo de decisión.
• La solución: En lugar de intentar encontrar una sola prueba aceptable, el algoritmo repite el proceso de muestreo de pruebas simuladas muchas veces ($p(|x|)$ veces) para un mismo CRS (Common Reference String).
• Lógica: Si el CRS es "bueno" (el simulador tiene una probabilidad significativa de generar una prueba aceptable), la repetición garantiza que se encontrará al menos una prueba aceptable con alta probabilidad. Si el CRS es "malo", la repetición no ayuda, pero la probabilidad de que el generador de CRS produzca un CRS "malo" está acotada por el error de conocimiento cero.
• Esto permite construir un algoritmo que decide el lenguaje con una probabilidad significativamente mayor para instancias en $L$ que para instancias fuera de $L$, siempre que $\epsilon_s + \epsilon_{zk} < 1$.

B. Proveedor Malicioso Eficiente (Para ZK Interactivo)

Para el caso Interactivo (argumentos de ZK de rondas constantes), la técnica es más compleja:

1. Definición de un Proveedor Malicioso ($\tilde{P}$): Se define un proveedor que, dado un transcripto parcial, utiliza UE para muestrear muchos posibles mensajes siguientes del simulador.
2. Selección Óptima: $\tilde{P}$ elige el mensaje que maximiza la probabilidad de que el verificador acepte al final.
3. Eficiencia: Como calcular la probabilidad exacta es costoso, $\tilde{P}$ estima esta probabilidad simulando interacciones futuras internamente (usando el hecho de que el verificador es de moneda pública y carece de estado interno).
4. Análisis de Errores: Se demuestra que $\tilde{P}$ se desempeña casi tan bien como el proveedor honesto, perdiendo solo una pequeña fracción de probabilidad de éxito debido a la estimación aproximada y al error de conocimiento cero global (no por mensaje).
5. Moneda Privada: Para protocolos de moneda privada, los autores muestran que, a menos que existan OWF con entrada auxiliar, cualquier protocolo de moneda privada de rondas constantes puede convertirse en uno de moneda pública.

3. Contribuciones Principales y Resultados

El artículo establece teoremas que caracterizan la complejidad del ZK no trivial:

1. Teorema Principal (NIZK): Si $NP \not\subseteq ioP/poly$ y existen argumentos NIZK no triviales para $NP$, entonces existen Funciones de Un Solo Sentido (OWF).

   • Esto mejora trabajos anteriores que requerían condiciones más estrictas sobre la suma de errores (ej. $\epsilon_{zk} + \sqrt{\epsilon_s} < 1$). Ahora, cualquier protocolo donde la suma de errores sea estrictamente menor que 1 es suficiente.

2. Teorema Principal (ZK Interactivo): Si $NP \not\subseteq ioP/poly$ y existen argumentos ZK de rondas constantes y moneda pública no triviales para $NP$, entonces existen OWF con entrada auxiliar.

   • Si se asume que no existen OWF con entrada auxiliar, entonces cualquier protocolo de moneda privada de rondas constantes puede convertirse en uno de moneda pública, lo que implica la existencia de OWF estándar.

3. Aplicación: Amplificación de Errores:

   • Un resultado crucial es que estos teoremas permiten la amplificación de protocolos débiles a fuertes sin suposiciones criptográficas adicionales (más allá de la dureza de $NP$).
   • Si existen NIZK no triviales, se pueden derivar OWF. Luego, usando OWF y técnicas de amplificación existentes, se pueden construir NIZK estándar (con errores despreciables) para todos los lenguajes en $NP$.
   • De manera similar, para ZK interactivo, la existencia de protocolos no triviales implica la existencia de argumentos ZK de 4 rondas con errores despreciables.

4. Significado e Impacto

• Caracterización Completa: El trabajo cierra una brecha importante en la comprensión de la complejidad del ZK. Demuestra que no existe un "región intermedia" segura donde existan protocolos ZK no triviales sin implicar la existencia de primitivas criptográficas fundamentales (OWF).
• Reducción de Suposiciones: Elimina la necesidad de suposiciones criptográficas fuertes (como cifrado de clave pública) para amplificar protocolos ZK débiles. Ahora, la única suposición necesaria es la dureza computacional de $NP$ en el peor caso.
• Nuevas Direcciones: Proporciona una ruta para construir OWF basándose únicamente en la existencia de protocolos de prueba de conocimiento cero "débiles" (pero no triviales), lo que podría ser útil en escenarios donde los protocolos estándar son difíciles de implementar pero los protocolos de alto error son factibles.

En resumen, el artículo demuestra que cualquier sistema de prueba de conocimiento cero no trivial (donde la suma de errores es menor que 1) para problemas difíciles en el peor caso es, en esencia, tan fuerte como las Funciones de Un Solo Sentido, permitiendo la construcción de criptografía estándar a partir de protocolos de alta tolerancia al error.