EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity

Resumen Técnico: Pares EFI sin Puzzles Unidireccionales

1. Planteamiento del Problema y Motivación

La criptografía cuántica carece actualmente de un único primitivo mínimo análogo a las funciones unidireccionales (OWF) en la criptografía clásica. Han surgido dos candidatos principales para este supuesto mínimo:

1. Pares EFI (Preparables eficientemente, Estadísticamente lejanos, Computacionalmente indistinguibles): Un par de estados cuánticos mixtos que son fáciles de generar, estadísticamente distintos, pero computacionalmente indistinguibles. Los pares EFI son equivalentes a los compromisos de bits cuánticos y permiten la computación multipartita segura.
2. Puzzles Unidireccionales (OWPuzzs): Un par $(Samp, Ver)$ donde un muestreador genera un puzzle clásico $s$ y una clave $k$, y un verificador ilimitado comprueba la clave. Los OWPuzzs implican pares EFI, pero el inverso es una pregunta abierta.

El problema abierto central es si la dureza requerida para los pares EFI (indistinguibilidad de estados cuánticos) implica necesariamente la dureza clásica de caso promedio requerida para los OWPuzzs (invertir un problema de búsqueda). Específicamente, ¿existe un oráculo relativo al cual existan pares EFI, pero no OWPuzzs (incluso con verificadores ineficientes)?

2. Metodología y Construcción del Oráculo

El autor construye un único oráculo clásico determinista $\mathcal{O}'$ que separa estos primitivos. El oráculo consta de dos capas:

1. Fuente de Estados ($R$): Sobre la entrada $(b, 1^\lambda)$, devuelve una copia fresca de un estado mixto $\rho_{b,\lambda}$. Estos estados se construyen a partir de un subespacio de media dimensión $H \subseteq \mathbb{R}^n$ elegido mediante una distribución de Haar (donde $n=2^\lambda$). Específicamente, $\rho_0$ es el estado máximamente mezclado sobre $H$, y $\rho_1$ es el estado máximamente mezclado sobre $H^\perp$.
2. Oráculo de Conteo ($Count$): Un oráculo clásico que, dada la descripción de un muestreador cuántico asistido por oráculo $C$ con salida clásica, devuelve los bits exactos de la probabilidad de salida $\Pr[C^{\mathcal{O}}(1^\lambda) = x]$. Para evitar la circularidad, las consultas se estratifican por rango: una consulta de rango $r$ solo puede preguntar sobre muestreadores cuyas propias llamadas al oráculo tengan un rango estrictamente menor que $r$.

Modelo de Acceso (Coherente-al Final / Coherent-Last): La seguridad del par EFI se demuestra contra distinguidores con acceso coherente al final. Este modelo otorga:

• Asesoría clásica de longitud polinómica (o $O(\lambda)$ qubits de asesoría cuántica).
• Polinómicamente muchas consultas clásicas adaptativas al oráculo.
• Exactamente una consulta coherente (en superposición) al final de la interacción.
• Polinómicamente muchas copias de referencia de los estados desafío (generados por la fuente pública).

3. Contribuciones Clave y Resultados

A. No existencia de Puzzles Unidireccionales (Teorema A(i))
Relativo a $\mathcal{O}'$, los OWPuzzs no existen, incluso con un verificador computacionalmente ilimitado.

• Mecanismo: El oráculo $Count$ permite a un adversario estimar las probabilidades de salida de cualquier muestreador con precisión exponencial utilizando un número polinómico de consultas clásicas.
• Ataque: El adversario puede reconstruir la distribución condicional de las claves bit a bit. Al muestrear de estas probabilidades condicionales estimadas, el adversario genera una clave aceptada por el verificador con probabilidad $1 - \text{negl}(\lambda)$.
• Alcance: Este ataque es puramente clásico y se aplica incluso si el adversario tiene acceso coherente total al oráculo (ya que el ataque no depende de consultas cuánticas). En consecuencia, todos los primitivos implicados por los OWPuzzs (estados pseudialeatorios de múltiples copias, generadores de estados de salida pura, dinero cuántico) tampoco existen relativo a $\mathcal{O}'$.

B. Existencia de Pares EFI (Teorema A(ii))
Relativo a $\mathcal{O}'$, el par de medio subespacio $(\rho_0, \rho_1)$ forma un par EFI seguro contra el modelo de acceso definido.

• Consultas Clásicas (Reducción de Complejidad de Comunicación): La seguridad contra consultas clásicas se reduce al problema de Vector-en-el-Subespacio (VSP). En VSP, Bob posee un subespacio $H$, y Alice posee un vector prometido en $H$ o en $H^\perp$.
  • Cuántico: VSP es fácil (Alice envía el vector en $O(\log n)$ qubits; Bob mide).
  • Clásico: VSP es difícil, requiriendo $\Omega(n^{1/3})$ bits de comunicación (límite de Klartag–Regev).
  • El autor muestra que cualquier transcripción clásica de longitud $L$ sobre $H$ proporciona como máximo una ventaja de $O(L/n^{1/3})$ para distinguir los estados. Dado que el adversario está limitado a un número polinómico de bits clásicos, la ventaja es despreciable.
• Copias de Referencia: Se le otorga al adversario copias de referencia de los estados. El autor muestra que estas pueden reemplazarse por descripciones clásicas de los espacios generados (spans) de las copias. Condicionar sobre estos spans reduce el problema a una instancia de VSP más pequeña en el complemento ortogonal, con una pérdida de seguridad solo despreciable.
• Consulta Coherente (Concentración de Matrices): La única consulta coherente permitida al final de la interacción se acota utilizando herramientas de la teoría de matrices aleatorias. Se demuestra que el sesgo de un adversario de una sola consulta es de $O(\sqrt{\log M / n})$, lo cual es despreciable para un ancho polinómico $M$. Nota: La afirmación de seguridad de EFI está restringida específicamente a este modelo de "coherente al final"; la separación aún no se sostiene para adversarios con acceso coherente completo (múltiples consultas de superposición adaptativas) al oráculo clásico.

C. Colapso Interactivo (Teorema B)
Relativo a $\mathcal{O}'$, no existe prueba de "cuanticidad" para protocolos con mensajes clásicos. Cualquier parte de tiempo polinómico cuántico en tal protocolo puede ser simulada por una parte de tiempo polinómico clásico realizando consultas clásicas a $\mathcal{O}'$. Esto implica que el tiempo polinómico cuántico no ofrece ventaja sobre el tiempo polinómico clásico para ninguna tarea con entradas y salidas clásicas en este mundo de oráculo.

D. Separación de Primitivos
El artículo establece una barrera de caja negra: no existe una construcción de caja negra completa de OWPuzzs a partir de pares EFI dentro de la clase de distinguidores definida por el Modelo 1.1. Esto separa el mundo "NanoCrypt" (donde existen pares EFI, pero no OWPuzzs) del mundo "CountCrypt" (donde existen OWPuzzs).

4. Significancia y Limitaciones

Significancia:

• Separación de Dureza: El trabajo demuestra que la dureza de distinguir estados cuánticos (EFI) no implica necesariamente la dureza de los problemas de búsqueda clásicos (OWPuzzs). Esto sugiere que el supuesto mínimo para la criptografía cuántica podría ser más débil que la dureza de caso promedio clásica.
• Nueva Técnica de Demostración: El artículo introduce un método novedoso para demostrar la indistinguibilidad de estados cuánticos reduciéndola a límites inferiores de la complejidad de comunicación clásica (específicamente VSP).
• Construcción de Oráculo: Proporciona un único oráculo clásico concreto que elimina la dureza de salida clásica (búsqueda, decisión e interacción) preservando la indistinguibilidad del estado cuántico (bajo la restricción de coherencia al final).

Limitaciones y Preguntas Abiertas:

• Acceso Coherente: La prueba de seguridad de EFI depende de la restricción de una sola consulta coherente al final. El artículo deja abierta la cuestión (Conjetura 8.2) de si la separación se mantiene contra adversarios con acceso coherente completo (múltiples consultas de superposición adaptativas) al oráculo clásico.
• Asesoría (Advice): La seguridad se mantiene contra $O(\lambda)$ qubits de asesoría cuántica, pero no descarta la asesoría cuántica de tamaño polinómico combinada con consultas clásicas (lo que permitiría efectivamente al adversario sintetizar arbitraria información lateral cuántica antes de la transcripción clásica).
• Relativización: Los resultados son separaciones de oráculo. No resuelven si los OWPuzzs pueden construirse a partir de pares EFI en el mundo no relativo, ni implican $P \neq PSPACE$.

En resumen, el artículo construye un mundo de oráculo donde la criptografía cuántica puede descansar en la indistinguibilidad de los estados cuánticos (pares EFI) sin depender de la dureza de los problemas de búsqueda clásicos (OWPuzzs), aclarando así el panorama de los supuestos mínimos en la criptografía cuántica.