💻 computer science

Weak Zero-Knowledge and One-Way Functions

El artículo demuestra que la existencia de protocolos de conocimiento cero débiles para lenguajes de peor caso en NP, bajo ciertas condiciones de suma de errores, implica la existencia de funciones unidireccionales, mejorando así los resultados anteriores al relajar las restricciones sobre los parámetros de error.

Autores originales: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

Publicado 2026-02-19

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

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

¡Hola! Vamos a desglosar este paper académico, que parece muy complejo, en una historia sencilla con analogías de la vida real. Imagina que estamos hablando de seguridad, secretos y trucos de magia.

El Gran Misterio: ¿Qué nos dice el "Cero Conocimiento"?

Imagina que tienes un tesoro (un secreto matemático) y quieres convencer a un amigo de que lo tienes, sin mostrarle ni una sola pieza del tesoro. Eso es lo que se llama un Protocolo de Cero Conocimiento (Zero-Knowledge). Es como si le dijeras: "Mira, puedo abrir esta caja mágica sin que tú veas lo que hay dentro, pero si intento mentir, la caja explota".

En criptografía, estos protocolos son vitales. Pero, ¿qué pasa si el protocolo no es perfecto? ¿Qué pasa si a veces la caja explota por error, o a veces el amigo sospecha un poco? A esos protocolos "imperfectos" o "débiles" los llamamos ZK Débiles.

El objetivo de este paper es responder a una pregunta muy importante:

Si existen estos protocolos "imperfectos" para resolver problemas muy difíciles, ¿significa eso que podemos crear funciones de un solo sentido (One-Way Functions)?

¿Qué es una función de un solo sentido?
Piensa en una batidora de huevos.

Es muy fácil romper un huevo y batirlo (crear el producto).
Es imposible tomar la mezcla batida y reconstruir el huevo entero tal como estaba antes.
En criptografía, estas funciones son la base de todo: contraseñas, firmas digitales, blockchains. Si no existen, la seguridad moderna se derrumba.

La Historia del Papel: ¿Qué descubrieron los autores?

Los autores (Rohit, Yunqi y Prashant) se preguntaron: "¿Qué tan 'débil' puede ser un protocolo de cero conocimiento antes de que deje de ser útil para crear seguridad?"

Antes de este trabajo, los científicos pensaban que los errores del protocolo tenían que ser muy pequeños y específicos para que funcionara. Pero este paper dice: "¡No! Casi cualquier protocolo imperfecto sirve, siempre que no sea demasiado malo".

Aquí están sus tres grandes descubrimientos, explicados con analogías:

1. La Batidora Perfecta (NIZK - No Interactivo)

Imagina un protocolo donde solo hay un mensaje. Tú envías una carta (la prueba) y el receptor la lee.

El problema: A veces la carta llega rota (error de completitud), a veces un tramposo puede enviar una carta falsa que parece real (error de seguridad), y a veces el receptor puede aprender un secreto que no debería (error de cero conocimiento).
El hallazgo: Los autores demostraron que si la suma de estos tres errores es menor que 1 (es decir, el protocolo funciona "mejor que el azar" en conjunto), ¡entonces sí existen las funciones de un solo sentido!
La analogía: Imagina que tienes una máquina que mezcla huevos. Si la máquina falla un 20% de las veces en romper el huevo, un 10% en batirlo mal y un 5% en dejar ver el interior, siempre que la suma de fallos no sea el 100%, ¡sigue siendo una máquina útil para hacer batidos! Antes pensaban que la máquina tenía que fallar menos de un 1% en total. Ellos dicen: "No, mientras funcione más de lo que falla, sirve".

2. El Juego de Preguntas y Respuestas (ZK Público)

Ahora imagina un protocolo donde hay varias rondas de preguntas y respuestas (como un interrogatorio).

El hallazgo: Si tienes un protocolo de varias rondas donde el "vigilante" (el verificador) lanza dados públicos (monedas al aire) y tú respondes, y la suma de errores sigue siendo menor que 1 (ajustada por el número de rondas), también existen las funciones de un solo sentido.
La analogía: Es como un juego de "20 preguntas" para adivinar un secreto. Si el juego tiene un poco de ruido (errores), pero el jugador honesto gana más a menudo que el tramposo, podemos usar ese juego para crear una "batidora de huevos" segura.

3. El Truco de los Rondas Fijas (Constant-Round)

Si el juego tiene un número fijo y pequeño de rondas (por ejemplo, siempre son 3 preguntas), pueden mejorar aún más la condición.

El hallazgo: Con un número fijo de rondas, pueden demostrar que existen funciones de un solo sentido que funcionan "casi siempre" (infinitamente a menudo).
La analogía: Es como un truco de magia de 3 pasos. Si el mago logra engañar al público en la mayoría de los intentos, podemos usar ese truco para crear un candado que nadie pueda abrir.

¿Por qué es esto tan importante?

Imagina que la criptografía es un castillo.

Las Funciones de Un Solo Sentido son los cimientos del castillo.
Los Protocolos de Cero Conocimiento son los guardias que protegen la puerta.

Antes, pensábamos que para que los guardias fueran útiles, tenían que ser perfectos (no podían fallar ni una vez). Si fallaban un poco, pensábamos que el castillo estaba en peligro y que no podíamos confiar en los cimientos.

Este paper dice: "¡Espera! Incluso si los guardias son un poco torpes, si siguen siendo mejores que un guardia al azar, ¡los cimientos del castillo son sólidos!"

Esto es revolucionario porque:

Ahorra esfuerzo: No necesitamos construir protocolos matemáticamente perfectos (que son muy difíciles de hacer). Con protocolos "suficientemente buenos" (pero imperfectos), ya podemos tener seguridad.
Conecta dos mundos: Une la teoría de la complejidad (qué problemas son difíciles de resolver) con la criptografía práctica (cómo proteger datos).

En resumen

Los autores nos dicen que la imperfección no es fatal. Incluso si nuestros sistemas de seguridad tienen pequeños errores (como un protocolo de cero conocimiento que a veces falla), mientras esos errores no sean tan grandes como para que el sistema deje de funcionar, podemos extraer de ellos la magia necesaria para crear la criptografía moderna.

Es como decir: "No necesitas un diamante perfecto para hacer un anillo de compromiso; un diamante con una pequeña imperfección, si es lo suficientemente brillante, sigue siendo precioso y duradero".

¡Y así, la seguridad de internet sigue siendo posible, incluso con herramientas imperfectas!

Resumen Técnico: Weak Zero-Knowledge and One-Way Functions

1. Problema y Contexto

La criptografía moderna se basa en la existencia de primitivas como las Funciones de Un Solo Sentido (OWF, por sus siglas en inglés). Una pregunta fundamental en la teoría de la complejidad criptográfica es determinar qué primitivas implican la existencia de OWF.

Trabajos previos (Ostrovsky, Wigderson, Hirahara, Nanashima) han demostrado que la existencia de protocolos de Cero Conocimiento (ZK) para lenguajes difíciles en el peor caso implica la existencia de OWF. Sin embargo, estos resultados asumen que los protocolos tienen errores (de completitud, sonidoza y cero conocimiento) que son despreciables (negligibles).

En la práctica, muchos protocolos ZK naturales (como los de coloreado de grafos o isomorfismo de grafos) tienen errores que son constantes o no despreciables. Estos se denominan Protocolos ZK Débiles. El problema central que aborda este artículo es: ¿Bajo qué condiciones de error no despreciables ( $\epsilon_c, \epsilon_s, \epsilon_z$ ) la existencia de protocolos ZK débiles para lenguajes en NP implica la existencia de OWF?

Anteriormente, Chakraborty et al. (CRYPTO 2025) habían establecido un límite bajo la condición $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ . Este trabajo busca relajar esa condición al máximo posible y extender el análisis a protocolos interactivos de múltiples rondas.

2. Metodología y Enfoque Técnico

Los autores desarrollan reducciones que transforman la capacidad de invertir funciones candidatas (derivadas de simuladores ZK) en un algoritmo que decide la pertenencia a un lenguaje difícil, contradiciendo así la dureza del lenguaje.

A. Protocolos No Interactivos (NIZK):

Enfoque anterior (Ostrovsky-Wigderson): Utilizaban un inverter para el simulador. La condición de error resultante era $\epsilon_s + 2\epsilon_z < 1$ (o variantes similares), ya que requerían verificar la prueba dos veces (una implícita en la simulación y otra explícita).
Innovación de este trabajo: Introducen una función candidata de un solo sentido $f_x(\rho)$ $f_{x} (ρ)$ que incluye explícitamente el resultado de la verificación $V(x; r, \pi)$ $V (x; r, π)$ en la salida.
- $f_x(\rho) = (r, a)$ donde $(r, \pi) \leftarrow \text{Sim}(x; \rho)$ y $a = V(x; r, \pi)$ .
- Al restringir al inverter a encontrar preimágenes que correspondan a una verificación exitosa ( $a=1$ ), eliminan la necesidad de una verificación explícita adicional en el distinguisher.
- Resultado: Logran relajar la condición a $\epsilon_c + \epsilon_s + \epsilon_z < 1$ , cubriendo todos los valores no triviales posibles.

B. Protocolos Públicos de Moneda (Public-Coin) Interactivos:

Para protocolos de $t$ mensajes, adaptan la técnica anterior.
Resultado General: Demuestran que si $\epsilon_c + \epsilon_s + (t-1)\epsilon_z < 1$ , existen OWF con entrada auxiliar (ai-OWF).
Mejora para Rondas Constantes: Para protocolos de $k$ $k$ rondas constantes, utilizan una construcción recursiva más sofisticada. Definen una familia de funciones $f_{i,x}$ $f_{i, x}$ donde cada función depende de la capacidad de invertir la siguiente función en la cadena.
- Utilizan algoritmos que estiman la probabilidad de aceptación condicional para maximizar la estrategia del "prover" falso.
- Resultado: Logran la condición $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ .
- Limitación: Esta mejora en los parámetros de error para rondas constantes solo garantiza la existencia de OWF "infinitamente a menudo" (io-OWF), debido a la necesidad de que múltiples algoritmos inversores tengan éxito simultáneamente en el mismo conjunto infinito de longitudes de entrada.

3. Contribuciones Clave

Optimización de Parámetros para NIZK:
- Se demuestra que si todos los lenguajes en NP tienen pruebas NIZK (o argumentos) con errores tales que $\epsilon_c + \epsilon_s + \epsilon_z < 1$ , entonces existen OWF.
- Esto mejora el resultado previo de Chakraborty et al. ( $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ ) y es óptimo en el sentido de que si la suma es $\ge 1$ , el protocolo es trivial.
- Además, implica que si $\epsilon_c$ es despreciable, se pueden amplificar estos protocolos débiles a protocolos estándar con errores despreciables.
Generalización a Protocolos Públicos Interactivos:
- Establecen que para protocolos de $t$ mensajes públicos, la condición $\epsilon_c + \epsilon_s + (t-1)\epsilon_z < 1$ es suficiente para derivar ai-OWF.
Mejora para Rondas Constantes:
- Para protocolos de $k$ rondas constantes, logran la condición más estricta $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ .
- Aunque el resultado es más débil (solo io-OWF), representa un avance significativo en la comprensión de la relación entre la complejidad de las rondas y la tolerancia al error.
Técnica de "Verificación Implícita":
- La contribución metodológica central es la inclusión del bit de verificación en la salida de la función de un solo sentido candidata. Esto evita penalizar el error de cero conocimiento dos veces, permitiendo condiciones de error más permisivas.

4. Resultados Principales

Teorema 1 (NIZK): Si $NP \not\subseteq ioP/poly$ y todo lenguaje en NP tiene un NIZK con $\epsilon_c + \epsilon_s + \epsilon_z < 1$ , entonces existen OWF.
Teorema 2 (ZK Público, $t$ mensajes): Si $NP \not\subseteq ioP/poly$ y todo lenguaje en NP tiene un ZK público de $t$ mensajes con $\epsilon_c + \epsilon_s + (t-1)\epsilon_z < 1$ , entonces existen OWF.
Teorema 3 (ZK Público, $k$ rondas constantes): Si $NP \not\subseteq P/poly$ y todo lenguaje en NP tiene un ZK público de $k$ rondas con $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ , entonces existen infinitamente a menudo OWF.

5. Significado e Impacto

Caracterización Completa: Este trabajo cierra la brecha teórica sobre los parámetros de error necesarios para que los protocolos ZK débiles impliquen dureza criptográfica. Muestra que la condición de suma de errores menor a 1 es la frontera natural para la existencia de OWF en el caso no interactivo.
Relación entre Complejidad y Seguridad: Ilustra cómo la estructura del protocolo (número de rondas) afecta la tolerancia al error. A medida que aumenta el número de rondas, la tolerancia al error de cero conocimiento ( $\epsilon_z$ ) se vuelve más restrictiva en la condición general, pero se puede optimizar con técnicas recursivas para casos de rondas constantes.
Fundamentos de Criptografía: Refuerza la conexión fundamental entre la existencia de protocolos de prueba de conocimiento cero (incluso imperfectos) y la existencia de primitivas criptográficas básicas. Esto sugiere que la criptografía moderna es robusta incluso frente a implementaciones de ZK que no son perfectas.
Direcciones Futuras: El trabajo deja abiertas preguntas sobre protocolos de moneda privada (private-coin) y cómo mejorar los resultados de "infinitamente a menudo" a OWF estándar para protocolos de rondas constantes.

En resumen, este artículo proporciona una comprensión más profunda y general de cómo la debilidad en los protocolos de cero conocimiento (en términos de errores no despreciables) aún es suficiente para garantizar la seguridad criptográfica fundamental, siempre que la suma de sus errores sea estrictamente menor a 1.