Comparing classical and quantum conditional disclosure of secrets

1. Introducción y Problema

El Contexto de Divulgación Condicional de Secretos (CDS, por sus siglas en inglés) es una primitiva fundamental en la criptografía de teoría de la información. En este escenario, tres partes interactúan:

• Alice y Bob reciben entradas $x$ e $y$ respectivamente.
• Alice posee un secreto $s$.
• El árbitro (Referee) conoce las entradas $x$ e $y$.

El objetivo es que Alice y Bob envíen mensajes simultáneos al árbitro de tal manera que:

1. Si $f(x, y) = 1$, el árbitro pueda recuperar el secreto $s$.
2. Si $f(x, y) = 0$, el árbitro no aprenda nada sobre $s$.

El problema central de este trabajo es investigar las diferencias entre el CDS clásico (donde se comparte aleatoriedad) y el CDS cuántico (CDQS) (donde se comparte entrelazamiento y se envían mensajes cuánticos). Los autores buscan determinar si los recursos cuánticos ofrecen ventajas significativas en la eficiencia (comunicación y entrelazamiento) y cómo se relacionan las cotas inferiores (lower bounds) de ambos regímenes.

2. Metodología

Los autores emplean una combinación de técnicas de complejidad de comunicación y computación cuántica no local (NLQC). Su enfoque metodológico incluye:

• Analogía Clásica-Cuántica: Revisan las cotas inferiores conocidas para el CDS clásico (basadas en complejidad de comunicación unidireccional, pruebas interactivas de dos mensajes, etc.) y buscan sus análogos cuánticos.
• Reducciones de Protocolos: Construyen protocolos de comunicación cuántica a partir de protocolos CDQS para demostrar cotas inferiores. Por ejemplo, convierten un protocolo CDQS en un protocolo de comunicación unidireccional clásica para acotar la complejidad.
• Técnicas de NLQC: Utilizan resultados recientes sobre computación cuántica no local, específicamente cómo realizar canales cuánticos conjuntos con baja profundidad de puertas $T$ (T-depth) utilizando entrelazamiento, para construir protocolos CDQS eficientes.
• Análisis de Funciones Específicas: Estudian funciones concretas (como "Not-Equals" y "Forrelation") para establecer separaciones explícitas entre los regímenes clásico y cuántico.

3. Contribuciones Clave y Resultados

El artículo presenta cuatro resultados principales:

A. Nuevas Cotas Inferiores para CDQS

Los autores establecen límites inferiores para la complejidad del CDQS en términos de clases de complejidad de comunicación clásica y cuántica:

1. Complejidad de Comunicación Unidireccional Clásica: Demuestran que la complejidad de CDQS (comunicación + entrelazamiento) está acotada inferiormente por:
   $$\text{CDQS}(f) = \tilde{\Omega}(\log R_{0,A\to B}(f) + \log R_{0,B\to A}(f))$$
   Donde $R_{0}$ es la complejidad de comunicación unidireccional clásica con corrección perfecta. Esto implica que las cotas inferiores clásicas basadas en comunicación unidireccional son "débiles" en el sentido de que también se aplican a estrategias cuánticas.
2. Pruebas Interactivas de Dos Provers: Establecen una cota inferior en términos de pruebas interactivas públicas de dos rondas y dos provers:
   $$\text{CDQS}(f) = \Omega(\text{QAM}[2, 2]_{cc}(f))$$
   Esto es el análogo cuántico más cercano a la cota inferior clásica basada en $\text{AM}_{cc}$ (Arthur-Merlin), sugiriendo que mejorar las cotas para CDQS cuántico es un paso hacia entender la complejidad $\text{QAM}[2, 2]_{cc}$.

B. Separación para el Caso de Corrección Perfecta

Demuestran una separación incondicional entre el CDS clásico y el CDQS para una versión de promesa de la función Not-Equals (NEQ):

• Caso Clásico: Para la función NEQ con la promesa de que las entradas son iguales o difieren exactamente en la mitad de los bits, la complejidad clásica de CDS con corrección perfecta es $\Omega(n)$.
• Caso Cuántico: Utilizando un protocolo basado en el problema distribuido de Deutsch-Jozsa y entrelazamiento, logran una cota superior de $O(\log n)$.
• Resultado: Existe una separación exponencial ($\Omega(n)$ vs $O(\log n)$) cuando se exige corrección perfecta.

C. Separación para el Caso Robusto (Con Error)

En el régimen robusto (donde se permiten errores de corrección y seguridad), es difícil probar separaciones incondicionales debido a la falta de cotas inferiores clásicas fuertes para funciones explícitas. Sin embargo, los autores ofrecen evidencia preliminar:

• Función Forrelation: Proporcionan una cota superior de $O(\text{poly}(\log n))$ para el CDQS de la función forrelation.
• Comparación: El mejor algoritmo clásico conocido para esta función es lineal ($O(n)$).
• Significado: Esto sugiere que incluso con errores permitidos, los recursos cuánticos pueden ofrecer ventajas significativas, aunque una separación incondicional total depende de avances futuros en la complejidad de comunicación clásica.

D. Separación en Mensajes Simultáneos Privados (PSM)

Mejoran una separación anterior entre el PSM clásico y el PSM cuántico (PSQM) para una función parcial (basada en el problema de Emparejamiento Oculto Booleano - BHM), logrando una separación exponencial en el régimen robusto.

4. Discusión y Significado

El trabajo tiene implicaciones profundas para varias áreas:

1. Criptografía de Teoría de la Información: Confirma que los recursos cuánticos (entrelazamiento) pueden reducir drásticamente la comunicación necesaria para tareas criptográficas fundamentales como la divulgación condicional de secretos, especialmente en escenarios de corrección perfecta.
2. Computación Cuántica No Local (NLQC): El artículo refuerza la conexión entre la criptografía y la NLQC. Muestra que las técnicas desarrolladas para realizar computación no local con baja profundidad de puertas $T$ pueden aplicarse directamente para construir protocolos de CDS eficientes.
3. Complejidad de Comunicación: Las cotas inferiores derivadas sugieren que entender el CDQS cuántico es una vía prometedora para atacar problemas abiertos en la complejidad de comunicación clásica, específicamente en la búsqueda de cotas inferiores para funciones explícitas en el modelo $\text{AM}_{cc}$.
4. Límites de la Analogía: Aunque muchas propiedades se transfieren del caso clásico al cuántico, los autores notan que ciertas propiedades clásicas, como la "esparcimiento de aleatoriedad" (randomness sparsification), no tienen un análogo cuántico claro, lo que abre nuevas preguntas sobre la relación entre entrelazamiento y comunicación.

En resumen, el artículo demuestra que el CDS cuántico no es simplemente una versión "ruidosa" del clásico, sino un régimen con capacidades superiores demostrables, y proporciona herramientas teóricas nuevas para explorar los límites de la criptografía y la computación cuántica.