Resumen Técnico: Preparación de Estados Remotos Ciega al Interceptor y Aplicaciones a la Criptografía de Clave Pública Cuántica

1. Planteamiento del Problema

La Preparación de Estados Remotos (RSP, por sus siglas en inglés) es un primitivo fundamental en la criptografía cuántica, que permite a un cliente clásico instruir a un servidor cuántico para preparar un estado cuántico específico utilizando únicamente comunicación clásica. Las construcciones de RSP existentes son centrales en el modelo de Computación Cuántica - Comunicación Clásica (QCCC), sustentando aplicaciones tales como la computación delegada, las pruebas de cualidad cuántica y la criptografía de clave pública cuántica (QPKE).

Sin embargo, los protocolos de RSP actuales enfrentan dos limitaciones significativas:

1. Supuestos Fuertes: Todas las construcciones conocidas dependen de primitivos criptográficos de "trampa" (trapdoor), notablemente de Funciones Libres de Trampa (TCF). Esta dependencia de las trampas es un problema abierto importante, ya que reducir los supuestos criptográficos (por ejemplo, a funciones de un solo sentido o estructuras algebraicas) sigue siendo un objetivo primordial en la criptografía.
2. Sobrecarga de Seguridad: Las definiciones estándar de RSP requieren "ceguera ante un servidor malicioso", asegurando que el servidor no aprenda nada sobre el estado incluso si se desvía arbitrariamente del protocolo. Esta noción de seguridad fuerte a menudo requiere protocolos complejos y supuestos específicos.

El artículo investiga si una forma más débil de RSP puede seguir sustentando aplicaciones criptográficas significativas admitiendo construcciones a partir de supuestos más débiles y libres de trampas. Específicamente, los autores se preguntan:

• ¿Pueden derivarse aplicaciones útiles de protocolos de RSP con garantías de seguridad relajadas?
• ¿Pueden construirse tales RSP más débiles sin el uso de trampas?

2. Metodología y Definiciones

Preparación de Estados Remotos Ciega al Interceptor (EB-RSP)

Los autores introducen un nuevo primitivo llamado Preparación de Estados Remotos Ciega al Interceptor (EB-RSP). Este relaja el requisito de ceguera estándar:

• Ceguera Estándar: El probador cuántico (servidor) no debe aprender nada sobre el estado preparado, incluso si es malicioso.
• Ceguidad de EB-RSP: El protocolo es ciego únicamente contra un interceptor externo que observa la transcripción clásica de una interacción honesta entre el verificador y el probador. El propio probador honesto tiene permitido conocer el estado que prepara.

Definición Formal: Un protocolo EB-RSP involucra a un verificador clásico $V$ y un probador cuántico $P$.

• Corrección: $P$ posee un estado $|+\theta\rangle = \frac{1}{\sqrt{2}}(|0\rangle + e^{i\theta}|1\rangle)$ donde $\theta \in \Theta_N = \{k \cdot \frac{2\pi}{N} \mid 0 \le k \le N-1\}$, y $V$ posee la descripción clásica $\theta$.
• Ceguera al Interceptor: Dada la transcripción de la ejecución honesta, ningún interceptor de tiempo polinómico cuántico (QPT) puede distinguir el $\theta$ verdadero de una muestra uniforme de $\Theta_N$.

Los autores se centran específicamente en protocolos EB-RSP de dos mensajes (un mensaje de $V$, un mensaje de $P$), ya que esta estructura es suficiente para su aplicación principal.

Supuestos Criptográficos

El artículo construye EB-RSP a partir de Acciones de Grupo de Un Solo Sentido (OWGAs).

• Acción de Grupo: Un mapa $\star: G \times X \to X$ que satisface los axiomas de acción de grupo.
• Libre (Semirregular): La acción es libre si $g \star x = x$ implica $g = 1$.
• Un Solo Sentido: Dado $(x, s \star x)$, es computacionalmente difícil para un adversario QPT encontrar $s'$ tal que $s' \star x = s \star x$.
• Distinción Clave: A diferencia de las TCF, las OWGAs no proporcionan inherentemente una trampa para que el verificador invierta la función. La construcción se basa en las propiedades algebraicas de la acción de grupo para cancelar parámetros desconocidos.

3. Contribuciones Clave y Resultados

A. Construcción de EB-RSP de Dos Mensajes a partir de OWGAs

Los autores presentan un protocolo concreto de EB-RSP de dos mensajes basado en OWGAs libres donde $G = \mathbb{Z}_p^\lambda$ para un primo $p$.

Descripción del Protocolo:

1. Verificador ($V$): Muestrea $x_0 \in X$ y $r, s \in G$. Computa $x_1 = (-s) \star x_0$. Envía $(x_0, x_1, r)$ a $P$.
2. Probador ($P$):
   • Prepara una superposición sobre $b \in \{0,1\}$ y $g \in G$.
   • Computa $g \star x_b$ en superposición.
   • Mide el registro de salida, colapsando el estado a un estado "garfio" (claw) $|0, g_0\rangle + |1, g_0 + s\rangle$ (debido a la libertad de la acción).
   • Computa productos internos con $r$ y aplica Transformadas de Fourier Cuánticas (QFT) a los registros.
   • Mide para obtener los resultados $g$ y $z$, enviándolos a $V$.
   • Genera el estado $|+\theta\rangle$ donde $\theta = \langle s, z \cdot r + g \rangle \cdot \frac{2\pi}{p}$.
3. Verificador ($V$): Computa $\theta$ usando su secreto $s$ y los recibidos $g, z$.

Significancia de la Construcción:

• Libre de Trampas: El verificador no necesita una trampa para computar $\theta$. En su lugar, la estructura algebraica de la acción de grupo asegura que los parámetros desconocidos (como $g_0$) se cancelen durante la medición de la QFT, dejando solo términos conocidos para el verificador.
• Seguridad: La seguridad se basa en el Teorema de Goldreich-Levin Cuántico. Dado que $g$ es uniformemente aleatorio e independiente de la visión del adversario, el término $\langle s, z \cdot r + g \rangle$ es computacionalmente indistinguible de uno uniforme, ocultando $\theta$ del interceptor.
• Generalización: El protocolo puede extenderse a $N$ compuesto (producto de primos distintos) ejecutando subrutinas paralelas.

B. Construcción de QPKE a partir de EB-RSP

Los autores demuestran que la EB-RSP de dos mensajes es suficiente para construir Criptografía de Clave Pública Cuántica (QPKE) con claves públicas clásicas y textos cifrados cuánticos.

Construcción (Caja Negra):

• KeyGen (Generación de Claves): Ejecutar la configuración EB-RSP $n$ veces. La clave pública $pk$ consiste en los primeros mensajes del verificador; la clave secreta $sk$ consiste en los estados internos del verificador.
• Enc (Cifrado): Para cifrar un bit $b$, el encriptador (actuando como el probador) ejecuta la computación EB-RSP para cada instancia de $pk$ para generar los estados $|+\theta_i\rangle$. Luego aplica una unitaria $U_b = R_z(b \cdot \lfloor N/2 \rfloor \cdot \frac{2\pi}{N})$ para invertir la fase basada en $b$. El texto cifrado es el conjunto de estados transformados y los mensajes del probador.
• Dec (Descifrado): El descifrador utiliza $sk$ para recuperar $\theta_i$, aplica $R_z(-\theta_i)$ para eliminar la fase y mide en la base de Hadamard para recuperar $b$.

Seguridad:
La seguridad IND-CPA de la QPKE depende directamente de la ceguera al interceptor de la EB-RSP subyacente. Dado que el interceptor no puede distinguir el ángulo aleatorio $\theta$ de uno uniforme, no puede distinguir el estado cifrado (que depende de $\theta + b \cdot \text{desplazamiento}$) de un estado aleatorio.

C. Adaptación de Protocolos Existentes Basados en TCF

El artículo observa que las construcciones de RSP existentes basadas en TCF simples (por ejemplo, [BKM+25]) pueden adaptarse al modelo EB-RSP de dos mensajes. Al fusionar mensajes y notar que el "bit de producto lateral" (byproduct bit) en la RSP basada en TCF es independiente del ángulo en ejecuciones honestas, estos protocolos también satisfacen la ceguera al interceptor. Esto resulta en una segunda construcción de QPKE a partir de TCF puras.

4. Significancia y Reivindicaciones

El artículo reivindica la siguiente significancia:

1. Primer Primitivo de Tipo RSP Libre de Trampas: Según el conocimiento de los autores, este es el primer primitivo de tipo RSP con aplicaciones criptográficas útiles que no depende de ningún primitivo de trampa. Demuestra que los supuestos algebraicos (OWGAs) pueden reemplazar los supuestos de trampa para tareas específicas de RSP.
2. Seguridad Más Débil, Misma Utilidad: El trabajo establece que la ceguera al interceptor (una noción de seguridad más débil que la ceguera ante un servidor malicioso) es suficiente para construir QPKE con claves públicas clásicas. Esto sugiere que los fuertes requisitos de seguridad de la RSP estándar pueden ser innecesarios para ciertas aplicaciones, permitiendo potencialmente protocolos más simples y supuestos más débiles.
3. Enfoque Modular: Los autores proporcionan una reducción genérica de caja negra de EB-RSP de dos mensajes a QPKE. Esto separa la construcción del primitivo de preparación de estados de su aplicación en el cifrado, permitiendo mejoras modulares en cualquiera de los dos componentes.
4. Paso Fundamental: Aunque la construcción se limita a acciones de grupo específicas y aún no logra una RSP verificable o una RSP contra servidores maliciosos sin trampas, proporciona un "primer paso" hacia la reducción de los supuestos criptográficos que sustentan los esquemas criptográficos cuánticos.

Limitaciones y Preguntas Abiertas:

• La construcción actualmente funciona para $N$ siendo un primo o un producto de primos distintos; extenderlo a potencias de primos sigue siendo incierto debido a problemas de corrección con la QFT sobre potencias de primos.
• El artículo no pretende construir una RSP verificable o una RSP ciega ante servidores maliciosos sin trampas; lo deja explícitamente como una dirección abierta.
• El esquema de QPKE resultante produce textos cifrados cuánticos, no clásicos (a diferencia de algunas construcciones basadas en TCF).

En resumen, el artículo inicia el estudio de una noción de RSP más débil (EB-RSP), construye una a partir de acciones de grupo de un solo sentido sin trampas, y demuestra su suficiencia para construir QPKE, expandiendo así el panorama de los supuestos disponibles para la criptografía cuántica.