Resumen Técnico: Pruebas de Conocimiento Cero Relativistas Asimétricas Experimentales con Seguridad Incondicional

Planteamiento del Problema

Las pruebas de conocimiento cero (ZKP, por sus siglas en inglés) son críticas para establecer confianza y privacidad en las economías digitales, como las criptomonedas y los contratos inteligentes. Sin embargo, los protocolos ZKP clásicos dependen de supuestos computacionales (por ejemplo, la existencia de funciones unidireccionales), lo que los hace vulnerables a futuros ataques cuánticos. Si bien las ZKP cuánticas ofrecen una alternativa potencial, enfrentan obstáculos de implementación significativos, incluyendo el teorema de no clonación que complica el reintento (rewinding) cuántico, y la imposibilidad de un compromiso de bit cuántico con seguridad incondicional.

Las RZKP (Pruebas de Conocimiento Cero Relativistas) han surgido como una solución al reemplazar los supuestos computacionales con los principios de la relatividad especial (específicamente el principio de no señalización). Un avance reciente demostró una RZKP simétrica para el problema de la coloración de tres colores de un grafo. Sin embargo, este protocolo simétrico sufre de ineficiencias prohibitivas al garantizar la solidez cuántica (quantum soundness) (seguridad contra probadores que comparten entrelazamiento cuántico). Para lograr la solidez cuántica, el protocolo simétrico requiere una complejidad de rondas de $O(|E|^4)$ (donde $|E|$ es el número de aristas), lo que conduce a tiempos de ejecución inalcanzables y costos de aleatoriedad masivos para grafos de tamaño realista.

Metodología

Los autores proponen e implementan experimentalmente un protocolo ZKP GMW relativista asimétrico diseñado para superar las limitaciones de eficiencia de los enfoques simétricos previos, manteniendo la seguridad incondicional contra probadores con correlación cuántica.

Diseño del Protocolo

El protocolo involucra dos pares de probador-verificador espacialmente separados ($P_1-V_1$ y $P_2-V_2$) y opera sobre $m$ rondas interactivas para demostrar que un grafo $G(V, E)$ es de tres colores sin revelar la coloración.

1. Preparación: Los probadores $P_1$ y $P_2$ comparten una permutación de colores aleatoria $\pi$ y un conjunto de valores aleatorios $B = \{b_k\}$.
2. Fase de Consulta: El verificador $V_1$ envía consultas aleatorias $X = \{x_k\}$ a $P_1$.
3. Fase de Compromiso: $P_1$ computa compromisos $A = \{a_k\}$ donde $a_k = x_k \cdot y_k - b_k$ (donde $y_k$ es el color) y los envía a $V_1$.
4. Fase de Desafío: El verificador $V_2$ selecciona una arista aleatoria $C = \{i, j\}$ y la envía a $P_2$.
5. Fase de Revelación: $P_2$ revela los colores $Y(C)$ y los valores correspondientes $B(C)$ a $V_2$.
6. Fase de Verificación: Los verificadores comprueban las restricciones relativistas (asegurando que no haya señalización entre $P_1$ y $P_2 mediante la verificación de los retrasos temporales$|t_1 - t_4| < \tau$y$|t_2 - t_3| < \tau$, donde $\tau = d/c$) y la consistencia lógica (los colores son distintos y coinciden con los compromisos).

Análisis Teórico

Los autores abordan el desafío de la solidez cuántica. A diferencia de los protocolos clásicos donde el compromiso de bits es fuertemente vinculante, los compromisos de bits relativistas solo garantizan un "compromiso de suma" (sum-binding). Los autores demuestran que la probabilidad de que los probadores cuánticos maliciosos engañen con éxito en una arista inválida está acotada superiormente por el valor cuántico de un juego CHSH$_{Q(2)}$ no local. Al relacionar el error de solidez del protocolo con este juego, derivan un límite superior riguroso para el error de solidez cuántica $\delta$.

Implementación Experimental

El equipo implementó un experimento de prueba de principio utilizando:

• Hardware: FPGAs para procesamiento de baja latencia y servidores de sincronización de tiempo GPS de alta precisión (con relojes atómicos).
• Configuración: Dos pares de probador-verificador separados por 300 metros (lo que corresponde a una separación temporal $\tau = 1000$ ns).
• Grafo: Un grafo de tres colores con $|V| = 588$ vértices y $|E| = 1097$ aristas.
• Ejecución: El experimento completó todas las rondas interactivas requeridas en aproximadamente 0.22 segundos.

Contribuciones Clave

1. Protocolo Asimétrico Eficiente: Los autores diseñaron un ZKP GMW relativista asimétrico que reduce la complejidad de rondas de $O(|E|^4)$ (en protocolos simétricos previos con solidez cuántica) a $O(|E|)$. Esto se logra utilizando compromisos de bits relativistas de dos probadores dentro del marco de GMW, permitiendo que la prueba y las comprobaciones de consistencia ocurran simultáneamente en una sola ronda.
2. Prueba de Solidez Cuántica: Proporcionaron una prueba rigurosa de solidez cuántica al relacionar la probabilidad de engaño de los probadores entrelazados con el juego no local CHSH$_{Q(2)}$, estableciendo un límite superior para el error de solidez sin depender de supuestos computacionales.
3. Realización Experimental: Ejecutaron con éxito el protocolo sobre una separación de 300 metros, demostrando que el tiempo de ejecución y el costo de aleatoriedad requeridos son factibles para un despliegue en el mundo real.

Resultados

• Complejidad de Rondas: El protocolo requiere $m = 2k|E|$ rondas para lograr un error de solidez de $e^{-k}$. Para los parámetros experimentales ($|E|=1097, k=100$), esto resultó en aproximadamente $2.2 \times 10^5$ rondas.
• Tiempo de Ejecución: Todo el experimento se completó en 0.22 segundos. En contraste, el protocolo simétrico anterior [23] habría requerido aproximadamente $6.72 \times 10^4$ años para lograr el mismo nivel de seguridad con el mismo grafo.
• Costo de Aleatoriedad: El costo total de aleatoriedad para el experimento fue de 430.81 MB. El protocolo simétrico [23] habría requerido aproximadamente $5.92 \times 10^9$ GB (5.92 exabytes) para la misma tarea.
• Seguridad: Las diferencias de tiempo $|t_1 - t_4|$ y $|t_2 - t_3|$ se midieron consistentemente por debajo del umbral de 1000 ns, satisfaciendo las restricciones de no señalización relativista incluso al considerar los errores de sincronización de GPS.

Significancia y Reivindicaciones

El artículo afirma que este trabajo ilustra el potencial poderoso de integrar la relatividad especial con la teoría cuántica para crear sistemas de confianza sin intermediarios que sean seguros contra ataques cuánticos sin depender de supuestos de dureza computacional.

Las afirmaciones clave sobre la significancia incluyen:

• Viabilidad Práctica: La reducción en la complejidad de rondas de $O(|E|^4)$ a $O(|E|)$ transforma las RZKP de constructos teóricos en tecnologías desplegables en la práctica para escenarios reales que involucren grafos de tamaño razonable.
• Seguridad Incondicional: El protocolo ofrece solidez cuántica y propiedades de conocimiento cero basadas únicamente en el principio de no señalización, lo que lo hace robusto frente a los futuros avances de la computación cuántica.
• Potencial de Escalabilidad: Aunque la naturaleza asimétrica impone una mayor carga computacional a un par probador-verificador ($V_1-P_1$), los autores argumentan que el intercambio es necesario para lograr tiempos de ejecución factibles. Sugieren que el protocolo podría implementarse en dispositivos cotidianos como teléfonos inteligentes.
• Aplicaciones Futuras: Los autores destacan aplicaciones potenciales en dominios sensibles a la privacidad como blockchains, contratos inteligentes, votación electrónica anónima y subastas en línea. También señalan el potencial de extender este marco a Pruebas de Conocimiento de Conocimiento (ZKPoK) para la verificación de identidad.

Los autores mantienen la modestia respecto a los desafíos de escalabilidad, reconociendo que el despliegue práctico en redes de fibra óptica aún enfrenta obstáculos como la verificación de la posición precisa de los probadores y la gestión de las cargas computacionales, que identifican como problemas abiertos para investigaciones futuras.