A proof complexity perspective on effectively zero-knowledge proofs

Resumen Técnico: Una Perspectiva desde la Complejidad de la Demostración sobre las Pruebas de Conocimiento Cero Efectivas

Planteamiento del Problema
El artículo aborda el concepto de las pruebas de conocimiento cero (ZK) "efectivamente cero-conocimiento", una variante introducida por Ilango [4] que se basa en ideas de la lógica matemática. La formulación original de Ilango evitaba las nociones lógicas estándar (como teorías, demostrabilidad y consistencia) en favor de simulaciones algorítmicas. El artículo identifica una limitación específica en la definición de Ilango: la propiedad de que una prueba es "indistinguible de la verdad" está integrada directamente en la definición del probador en lugar de ser derivada como una consecuencia. Además, la construcción de las pruebas de ZK efectivas depende de conjeturas tanto de la criptografía como de la complejidad de la demostración, específicamente respecto a la existencia de tautologías proposicionales difíciles para sistemas de demostración específicos. El artículo busca reformular este concepto utilizando el lenguaje de la lógica y la complejidad de la demostración para proporcionar pruebas de existencia más simples y para clarificar la relación entre la definición del probador y la propiedad de "indistinguibilidad".

Metodología
El autor emplea el marco de la complejidad de la demostración y la aritmética acotada, utilizando específicamente teorías capaces de razonar sobre computaciones y demostraciones (tales como $S^1_2$ y $S_2$). La metodología consiste en:

1. Reformulación Lógica: Reemplazar las simulaciones algorítmicas por teorías formales $T$ y sus extensiones $T^*$. El probador se define en relación con una teoría $T$, y la propiedad ZK se caracteriza por la no existencia de demostraciones cortas dentro de $T$ para la no existencia de un simulador.
2. Teoría de Modelos de la Aritmética: Las demostraciones utilizan modelos no estándar de la aritmética y el "principio de sobreextensión" (overspill principle). Específicamente, el artículo se apoya en un teorema de K.-Pudlák [13] que vincula la no existencia de demostraciones proposicionales cortas en un sistema de demostración $P(T)$ con la existencia de extensiones de modelos de aritmética donde ciertas fórmulas son satisfacibles.
3. Generadores de Complejidad de la Demostración: En la sección final, el artículo explora la transformación de las pruebas de ZK efectivas en pruebas de conocimiento cero "genuinas". Esto se logra reemplazando la secuencia de tautologías difíciles $\Psi$ por generadores de complejidad de la demostración. La construcción asume la existencia de "demi-bits" (un tipo de generador difícil definido por Rudich [16]) y permite que el probador y el verificador compartan una cadena aleatoria común.

Contribuciones Clave y Resultados

• Reformulación del Probador: El artículo define un probador $Prover[A, B, \Psi]$ en relación con una teoría $T$. La propiedad ZK se define no por la existencia inmediata de un simulador, sino por la condición de que, para cualquier tamaño polinómico $d$, la teoría $T$ no puede demostrar (con demostraciones de tamaño superpolinómico) que no existe un simulador de tamaño $n^d$.
• Derivación de "Indistinguibilidad de la Verdad": Un resultado principal (Teorema 2.4) demuestra que la propiedad de ser "indistinguible de la verdad" es una consecuencia de la definición de ZK relativa a una teoría, en lugar de un prerrequisito. Si un enunciado $S(n)$ es demostrable en $T$ a partir de la existencia de un simulador, y el probador es ZK relativo a $T$, entonces $S(n)$ debe ser verdadero para todos excepto para un número finito de $n$. Esto contrasta con la definición de Ilango, donde esto era parte de los requisitos axiomáticos del probador.
• Prueba de Existencia (Teorema 2.2): El artículo demuestra que si $A, B$ forman un esquema de Indistinguibilidad de Testigo No Interactivo (NIWI) y la secuencia de tautologías $\Psi$ es difícil para el sistema de demostración $P(T^*)$, entonces el probador construido es ZK relativo a $T$. La demostración utiliza modelos no estándar para mostrar que la existencia de un simulador es consistente con la teoría, evitando así demostraciones cortas de su no existencia.
• Transformación a ZK Genuino (Sección 3): El artículo muestra que el concepto de ZK efectivo puede convertirse en pruebas de conocimiento cero estándar (donde un simulador realmente existe) bajo supuestos específicos. Al utilizar generadores de complejidad de la demostración derivados de "demi-bits" y permitir que las partes compartan una cadena aleatoria común, se puede garantizar uniformemente la dificultad de las fórmulas subyacentes. Esto evita la necesidad de que el probador y el verificador confíen en una secuencia específica de tautologías sin verificación.

Significancia y Reivindicaciones
El artículo afirma ofrecer una "demostración simple" de la existencia y las propiedades clave de las pruebas de conocimiento cero efectivas mediante el aprovechamiento de la estructura lógica de la complejidad de la demostración. Su significancia radica en:

1. Claridad Conceptual: Clarifica los fundamentos lógicos de las pruebas de ZK efectivas, mostrando que la propiedad de "indistinguibilidad de la verdad" es una consecuencia derivable de la definición del probador relativo a una teoría.
2. Puente entre Lógica y Criptografía: Conecta explícitamente la noción criptográfica de indistinguibilidad de testigo con la noción lógica de extensiones de modelos y la no existencia de demostraciones cortas.
3. Camino hacia el ZK Estándar: Esboza una vía teórica para transformar estas pruebas condicionales, basadas en la lógica, en pruebas de conocimiento cero estándar, supeditadas a la existencia de generadores de complejidad de la demostración difíciles (específicamente demi-bits) y al uso de una cadena aleatoria común.

El autor mantiene la modestia respecto a la construcción de las secuencias difíciles en sí mismas, señalando que, si bien existen conjeturas (por ejemplo, respecto a la existencia de generadores difíciles para todos los sistemas de demostración), una prueba de que una construcción específica funciona sigue siendo un problema abierto en la complejidad de la demostración. El artículo sirve como un refinamiento teórico y un puente entre la formulación lógica de ZK y las definiciones criptográficas estándar.