Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM

Resumen Técnico: Imposibilidad de un Acuerdo de Claves de Muchas Rondas Perfectamente Completo en el QROM

Planteamiento del Problema
Este artículo aborda los límites fundamentales del Acuerdo de Claves Cuánticas (QKA) dentro del Modelo de Oráculo Aleatorio Cuántico (QROM). Específicamente, investiga si dos partes, Alice y Bob, pueden establecer una clave secreta compartida con completitud perfecta (probabilidad 1) utilizando únicamente comunicación clásica, mientras realizan computaciones cuánticas locales y realizan consultas cuánticas a un oráculo aleatorio. El entorno es el modelo de Computación Cuántica con Comunicación Clásica (QCCC). La cuestión central es si tales protocolos pueden ser seguros contra un espía pasivo que observa la transcripción clásica y tiene acceso al mismo oráculo, asumiendo que el protocolo se construye a partir de funciones unidireccionales (OWF) cuánticamente seguras de manera de caja negra.

Trabajos previos habían establecido separaciones para protocolos clásicos y casos cuánticos específicos, pero persistían brechas para protocolos QCCC generales de múltiples rondas. Notablemente, Austrin et al. (CRYPTO 22) proporcionaron un ataque de consultas polinomiales bajo una "Conjetura de Compatibilidad Polinomial" no probada, mientras que Li et al. (CRYPTO 26) resolvieron el caso para protocolos de dos rondas de forma incondicional. Este artículo busca cerrar la brecha para protocolos de rondas arbitrarias sin depender de conjeturas no probadas.

Metodología
Los autores emplean una combinación de teoría de la complejidad de consultas cuánticas, análisis polinomial sobre funciones booleanas y complejidad de árbol de decisión para construir un ataque incondicional. La metodología central procede de la siguiente manera:

1. Factorización Polinomial de las Probabilidades de la Transcripción:
   Al fijar la transcripción clásica completa $t$ y la tabla de verdad del oráculo $z$, se demuestra que la probabilidad de que Alice y Bob produzcan claves específicas $a$ y $b$ se factoriza en $A_{t,a}(z) \cdot B_{t,b}(z)$. Aquí, $A$ y $B$ son funciones no negativas que representan las probabilidades de ejecución local de Alice y Bob, respectivamente.

   • Utilizando el método polinomial cuántico (específicamente el Lema 2.2 de [BBC+01]), los autores acotan los grados de estas funciones: $\deg(A_{t,a}) \le 2q_A$ y $\deg(B_{t,b}) \le 2q_B$, donde $q_A$ y $q_B$ son el número de consultas cuánticas realizadas por las partes honestas.

2. Soportes de Claves Disjuntos mediante Completitud Perfecta:
   La condición de completitud perfecta ($Pr[K_A = K_B] = 1$) implica que para cualquier transcripción válida $t$ y oráculo $z$, el producto $A_{t,k}(z)B_{t,k}(z)$ debe ser cero para todo par de claves distintas $k \neq \ell$.

   • Definiendo $C_{t,k}(z) = A_{t,k}(z)B_{t,k}(z)$, los autores demuestran que los soportes de estos polinomios son disjuntos entre sí en el cubo booleano $\{0,1\}^N$.
   • Esta disjuntidad, combinada con el hecho de que un polinomio multilineal no nulo de grado $d$ debe ser no nulo en al menos $2^{N-d}$ puntos (Lema 2.1), limita el número de claves candidatas $|K_t|$ a un máximo de $2^d$, donde $d = 2(q_A + q_B)$.

3. Árbol de Decisión para Polinomios Disjuntos:
   La contribución técnica crítica es un procedimiento determinista (Lema 3.5) para identificar qué uno de dos polinomios de soporte disjunto, $p$ y $q$, es no nulo en un oráculo específico $z$, dado el compromiso de que uno de ellos es no nulo.

   • El procedimiento utiliza un árbol de decisión recursivo. En cada paso, identifica un conjunto de $O(d^3)$ bits del oráculo tales que consultarlos determina la respuesta o reduce estrictamente el grado de uno de los polinomios.
   • Esta reducción se basa en una desigualdad de Markov discreta (Lema 2.3) aplicada a un polinomio $r$ derivado de la diferencia de los cuadrados de las entradas.
   • Se demuestra que la profundidad de este árbol de decisión es $O(d^4)$.

4. Estrategia de Búsqueda Binaria:
   El espía realiza una búsqueda binaria equilibrada sobre el conjunto de claves candidatas $K_t$ (tamaño $\le 2^d$). En cada nivel, el conjunto de candidatos se divide en dos mitades, y se forman las sumas de los polinomios correspondientes ($P$ y $Q$). Dado que sus soportes son disjuntos, exactamente uno de $P(z)$ o $Q(z)$ es no nulo. El árbol de decisión del paso 3 se utiliza para determinar qué mitad contiene la clave correcta.

   • Con un máximo de $d$ niveles de búsqueda binaria y $O(d^4)$ consultas por nivel, la complejidad total de consultas es $O(d^5)$.

Contribuciones Clave y Resultados

• Imposibilidad Incondicional: El artículo demuestra que es imposible construir protocolos de acuerdo de claves QCCC de rondas finitas y con completitud perfecta a partir de funciones unidireccionales (OWF) cuánticamente seguras de manera de caja negra en el QROM. Este resultado es incondicional, eliminando la "Conjetura de Compatibilidad Polinomial" requerida por el trabajo anterior [ACC+22].
• Límite de Complejidad de Consultas: Los autores construyen un espía que recupera la clave compartida con probabilidad 1 utilizando $O((q_A + q_B)^5)$ consultas al oráculo clásicas.
  • Este límite es independiente del número de rondas de comunicación, la longitud de la transcripción, la longitud de la clave y el tamaño del dominio del oráculo.
  • Crucialmente, aunque las partes honestas pueden usar consultas en superposición, el espía solo requiere consultas clásicas.
• Generalización: El resultado generaliza los hallazgos previos sobre protocolos de dos rondas [LLLL26] a rondas arbitrarias y permite que las partes mantengan estados cuánticos arbitrarios entre las etapas de comunicación, un escenario no cubierto por resultados incondicionales previos.

Significado y Reivindicaciones
El artículo afirma proporcionar una respuesta negativa definitiva a la seguridad del QKA de muchas rondas y con completitud perfecta en el QROM.

• Impacto Teórico: Establece una separación estricta de caja negra entre las funciones unidireccionales cuánticamente seguras y el acuerdo de claves con completitud perfecta en el entorno QCCC.
• Avance Metodológico: La prueba introduce una aplicación novedosa de la reducción del grado polinomial y la complejidad del árbol de decisión al problema de la recuperación de claves, manejando específicamente el caso en que las partes honestas usan superposición cuántica pero el atacante está restringido a consultas clásicas.
• Limitaciones: Los autores declaran explícitamente que la prueba depende de la completitud perfecta. Extender este resultado a protocolos con completitud imperfecta (donde las partes podrían no ponerse de acuerdo con alguna pequeña probabilidad) requeriría ideas significativamente diferentes y no es cubierto por este trabajo.
• Atribución: El artículo señala que el núcleo de la prueba fue descubierto por GPT-5.6 Sol Ultra en una sola conversación, siendo los autores humanos responsables de la verificación, el refinamiento y la exposición final.

En resumen, el artículo demuestra que en el QROM, la combinación de comunicación clásica y completitud perfecta es insuficiente para proteger el acuerdo de claves de un espía clásico eficiente, independientemente del número de rondas o la complejidad de las computaciones cuánticas locales.