Resumen Técnico: El Paseo de Kac en Paralelo Genera PRU

Planteamiento del Problema

La construcción de Unitarios Pseudialeatorios (PRUs) —conjuntos de unitarios que son implementables de manera eficiente pero computacionalmente indistinguibles de unitarios aleatorios de Haar para cualquier distinguidor cuántico de tiempo polinómico— ha sido un desafío significativo en la criptografía cuántica. Mientras que los Estados Pseudialeatorios (PRSs) se establecieron anteriormente, los PRUs siguieron siendo esquivos.

Avances recientes por Metger, Poremba, Sinha y Yuen [MPSY24] introdujeron la construcción PFC (una secuencia de puertas Clifford aleatorias, de fase aleatoria y de permutación aleatoria), la cual fue posteriormente demostrada por Ma y Huang [MH25] como adaptativamente segura contra adversarios. Sin embargo, todas las construcciones de PRU demostrablemente seguras conocidas hasta la fecha siguen este paradigma PFC. La pregunta abierta abordada en este trabajo es si otras construcciones, específicamente aquellas basadas en paseos aleatorios sobre grupos unitarios, también pueden lograr la seguridad de un PRU.

Metodología

Los autores analizan el Paseo de Kac en Paralelo, una variante del clásico paseo de Kac (un paseo aleatorio sobre grupos unitarios) adaptado para la computación cuántica. En un solo paso del paseo de Kac en paralelo:

1. Se aplica una permutación aleatoria $\sigma$ a la base computacional, emparejando los estados de la base $|i\rangle$ y $|j\rangle$ de tal manera que compartan el mismo sufijo de longitud $n-1$.
2. Para cada par, se aplica una unidad $2 \times 2$ de Haar-aleatoria independiente.

La construcción propuesta, denotada como $HP_{n, T}$, consiste en $T$ repeticiones secuenciales de este paso del paseo de Kac en paralelo, donde las funciones y permutaciones aleatorias son reemplazadas por contrapartes pseudialeatorias cuánticamente seguras (QPRF y QPRP). Los autores establecen $T = O(n)$ (específicamente $30n$) para asegurar que la construcción sea eficiente (lineal en el número de cúbits).

La estrategia de prueba se basa en la técnica de registro de trayectoria introducida por Ma y Huang [MH25], adaptada a la estructura específica del paseo de Kac. La metodología procede en tres fases principales:

1. Proyección al Subespacio de Bloques Distintos: Los autores demuestran primero que $O(n)$ pasos del paseo de Kac en paralelo actúan como un "mezclador de estados aleatorios" (RSS, por sus siglas en inglés). Cuando este es seguido por una permutación aleatoria, el estado del adversario es proyectado con alta probabilidad hacia el subespacio de bloques distintos. En este subespacio, las tuplas de consultas $(x_1, \dots, x_t)$ pertenecen a bloques distintos (donde un bloque se define por el sufijo de la cadena de bits). Esta proyección es crucial porque el análisis de seguridad depende de que las consultas del adversario estén restringidas a estos bloques distintos.

2. Oráculo Purificado de Función-Permutación y Registro de Trayectoria: Los autores introducen un Oráculo de Función-Permutación Purificado (HPO) para modelar la interacción del adversario con el unitario aleatorio $H_f \cdot P_\sigma$. Definen un nuevo Oráculo de Registro de Trayectoria (PR) diseñado para el subespacio de bloques distintos. A diferencia del oráculo de registro de trayectoria estándar que rastrea elementos distintos, esta variante asegura que los resultados muestreados pertenezcan a bloques distintos.

3. Indistinguibilidad mediante Isometría: Una contribución técnica clave es la construcción de una isometría, Compress, que mapea el estado del entorno del oráculo HPO purificado al espacio de estados del oráculo de registro de trayectoria. Los autores prueban que si el estado del adversario reside en el subespacio de bloques distintos (garantizado por los $O(n)$ pasos iniciales), el comportamiento del paso del paseo de Kac en paralelo es indistinguible del oráculo de registro de trayectoria. Dado que el oráculo de registro de trayectoria es indistinguible de un unitario de Haar bajo estas restricciones, se prueba la seguridad de toda la construcción.

Contribuciones Clave y Resultados

1. Construcción de PRU con Seguridad Adaptativa

El artículo demuestra que un número lineal de repeticiones secuenciales del paseo de Kac en paralelo forma un PRU de seguridad adaptativa.

• Teorema 1 (Informal): La distribución de un unitario correspondiente a un paseo de Kac en paralelo aleatorio de $O(n)$ pasos es computacionalmente indistinguible de la distribución de Haar contra adversarios adaptativos.
• Teorema 16: Establece formalmente que $HP_{n, T+1}$ (con $T=30n$) es computacionalmente indistinguible de la distribución de Haar.

2. Seguridad Fuerte contra Consultas Inversas

Se demuestra que la construcción satisface la seguridad fuerte, lo que significa que permanece indistinguible de Haar-aleatorio incluso cuando el adversario tiene acceso tanto a consultas directas ($O$) como inversas ($O^\dagger$).

• Teorema 33: Al utilizar $2T+1$ pasos (específicamente $HP_{n, 2T+1}$), la construcción logra seguridad fuerte estadística. Esto implica la existencia de PRUs de seguridad fuerte computacional bajo el supuesto de funciones de un solo sentido post-cuánticas.

3. Alternativa al Paradigma PFC

Este trabajo proporciona la primera construcción de PRU segura que se desvía significativamente del paradigma PFC (Clifford-Fase-Permutación).

• La construcción es modular, consistiendo en la repetición de un módulo básico de "mezclado" (el paso del paseo de Kac en paralelo).
• Ofrece una nueva perspectiva en el diseño de PRU, sugiriendo que un "filtro" (como un 2-diseño o un RSS) seguido de un solo paso de un "compilador de aleatoriedad" (como el paseo de Kac en paralelo) puede producir un PRU completo.

4. Generalización de las Condiciones de Seguridad

Los autores destilan una condición general (Teorema 32 y Teorema 34) para la construcción de PRU y de PRU fuerte. Muestran que cualquier distribución unitaria $K$ que aproxime la aleatoriedad de Haar bajo operaciones de torcido específicas (por ejemplo, ser un 2-diseño aproximado o un RSS), al componerse con un solo paso del paseo de Kac en paralelo, produce un PRU. Esto proporciona una plantilla para generar nuevos candidatos a PRU.

Significado y Reivindicaciones

El artículo afirma confirmar una conjetura de [LQS+26] de que el paseo de Kac en paralelo puede generar un PRU. Su importancia radica en:

• Diversificación de Candidatos a PRU: Al proporcionar una construcción fuera de la familia PFC, mitiga el riesgo asociado con posibles vulnerabilidades en un solo paradigma.
• Demostración de la Versatilidad del Registro de Trayectoria: El trabajo extiende la técnica de registro de trayectoria para manejar la estructura de "bloques distintos" inherente a los paseos de Kac, mostrando la adaptabilidad de la técnica para analizar diferentes procesos aleatorios cuánticos.
• Conexión con la Criptografía Clásica: La naturaleza iterativa de la construcción (repitiendo un módulo básico) establece un paralelo con los cifrados de bloque clásicos como AES y las redes de Feistel, ofreciendo un análogo cuántico a estas estructuras bien comprendidas.

Los autores mantienen la modestia respecto a la eficiencia, señalando que su construcción no ofrece actualmente ventajas de eficiencia asintótica sobre la construcción PFC. Identifican preguntas abiertas, tales como si el número de rondas puede reducirse a una constante o si la construcción puede simplificarse a circuitos aleatorios locales, lo que resolvería un problema de larga data en la teoría de la complejidad cuántica.