A NISQ-friendly Coined Quantum Walk Algorithm for Chaos-based Cryptographic Applications

1. El Problema

Las caminatas cuánticas de tiempo discreto (DTQW) son herramientas prometedoras para la criptografía debido a su naturaleza caótica (sensibilidad a las condiciones iniciales, no linealidad y aperiodicidad). Sin embargo, su implementación práctica en dispositivos cuánticos de escala intermedia ruidosa (NISQ) enfrenta un obstáculo crítico: la profundidad del circuito.

• Limitación Actual: Los modelos existentes, como la Caminata Cuántica Alternada Controlada (CAQW), requieren una profundidad de circuito que escala como $O(n^2t)$ para una red de $n \times n$ durante $t$ pasos. Esta complejidad es demasiado alta para los procesadores cuánticos actuales, que sufren de decoherencia y errores de puertas, haciendo que los resultados no sean reproducibles ni útiles para la generación de claves.
• Restricción de Topología: Además, las implementaciones de CAQW en redes cíclicas de tamaño impar (necesarias para evitar patrones predecibles en la distribución de probabilidad) no pueden utilizar enfoques optimizados basados en la Transformada Rápida de Fourier (QFT) debido a que las matrices de desplazamiento no son circulares en sistemas de qubits de tamaño impar.

2. Metodología

Los autores proponen un nuevo modelo llamado Caminata Cuántica Alternada Descuidada (LAQW, por sus siglas en inglés: Lackadaisical Alternating Quantum Walk) y un esquema completo de generación de claves simétricas.

A. El Modelo LAQW

• Innovación: Se introduce un bucle de autoconexión (self-loop) en cada nodo de la red. Esto permite que el "caminante" tenga la opción de quedarse en su posición, además de moverse a la izquierda o derecha.
• Mecanismo: Se añade un segundo qubit de moneda. El operador de desplazamiento se redefine para que el movimiento ocurra solo si los qubits de moneda están en estados $|00\rangle$ o $|11\rangle$; de lo contrario, el caminante permanece en su lugar.
• Ventaja Computacional: Esta modificación hace que las matrices de desplazamiento sean circulares, permitiendo el uso de la aproximación basada en QFT. Esto reduce la complejidad de la profundidad del circuito de $O(n^2t)$ a $O(n^2 + nt)$.

B. Esquema de Generación de Claves

El proceso de generación de claves consta de dos etapas principales:

1. Generación de la Cadena de Bits "Cruda":
   • Se ejecuta la LAQW múltiples veces (shots) para obtener una distribución de probabilidad.
   • Se aplica un redondeo de intervalos determinista para mitigar fluctuaciones estadísticas menores y asegurar la reproducibilidad.
   • Se utiliza un mapeo de módulo primo para convertir los conteos enteros en bytes (0-255), rompiendo la estructura subyacente y logrando una distribución casi uniforme.
2. Extracción de la Clave:
   • Se estima la min-entropía de la distribución de probabilidad (usando el límite superior de confianza de Clopper-Pearson) para determinar la cantidad de bits aleatorios extraíbles.
   • Se aplica el Lema de la Hash Restante (LHL) para extraer una clave uniforme y segura.
   • Se utiliza un esquema de extracción ponderada determinista basado en el parámetro inicial del estado de la moneda ($\alpha$) para seleccionar bits de múltiples ejecuciones, asegurando que la clave final dependa de la dinámica subyacente.

3. Contribuciones Clave

1. Algoritmo LAQW: Presentación de un modelo de caminata cuántica que mantiene las propiedades caóticas necesarias para la criptografía pero con una profundidad de circuito significativamente reducida.
2. Implementación de Circuito: Diseño de un circuito cuántico optimizado que utiliza operadores de adición cuántica (QADD) y QFT, reduciendo drásticamente el número de puertas y la profundidad en comparación con la CAQW.
3. Esquema Criptográfico Completo: Propuesta de un método reproducible para generar claves simétricas de 128 bits a partir de la distribución de probabilidad de la LAQW, incluyendo técnicas de post-procesamiento para garantizar uniformidad y seguridad.
4. Evaluación Exhaustiva: Validación del esquema mediante pruebas de aleatoriedad (NIST), análisis de sensibilidad a parámetros y pruebas de ruido en hardware simulado.

4. Resultados

• Eficiencia del Circuito:
  • Comparado con la CAQW, el modelo LAQW logra una reducción promedio de profundidad de circuito del 88.28% (en simuladores sin ruido) y del 87.81% (en el backend ruidoso FakeTorino de IBM).
  • Para una red de $8 \times 8$ y $t=20$, la profundidad de LAQW es de ~550 puertas frente a ~5064 de la CAQW.
• Sensibilidad Caótica:
  • La LAQW muestra una mayor sensibilidad a cambios pequeños en los parámetros de la moneda ($\theta_0, \theta_1, \alpha$) en comparación con la CAQW (distancias de Hellinger un 30%, 29% y 18% más altas, respectivamente).
  • Sin embargo, la CAQW es ligeramente más sensible a cambios en el número de pasos ($t$).
• Calidad Estadística (NIST):
  • Las cadenas de bits extraídas (claves de 128 bits) pasan la mayoría de las pruebas de aleatoriedad del conjunto NIST SP 800-22.
  • La LAQW genera una entropía mínima promedio de 2.781 bits por bloque, superior a los 1.947 bits de la CAQW, permitiendo extraer más bits útiles (1619 vs 793).
• Reproducibilidad y Ruido:
  • La distancia de Hamming normalizada entre claves generadas con los mismos parámetros es casi nula (0.0003), demostrando alta reproducibilidad.
  • Bajo simulación de ruido real (FakeTorino), el esquema mantiene su integridad, con una distancia de Hamming de la clave aún menor (0.0002) y sin pérdida en el número de bits extraíbles.

5. Significado e Impacto

Este trabajo es significativo porque hace viable la implementación de primitivas criptográficas basadas en caminatas cuánticas en la era NISQ.

• Viabilidad Práctica: Al reducir la profundidad del circuito en un ~88%, el algoritmo LAQW se adapta a las limitaciones actuales de coherencia y conectividad de los procesadores cuánticos, algo que los modelos anteriores (CAQW) no permitían.
• Seguridad: El esquema demuestra que es posible generar claves simétricas reproducibles y altamente aleatorias a partir de un sistema cuántico ruidoso, aprovechando la sensibilidad caótica del sistema para resistir ataques de fuerza bruta.
• Futuro: Establece un nuevo estándar para el uso de caminatas cuánticas en criptografía, sugiriendo que la incorporación de bucles de autoconexión (self-loops) es una estrategia efectiva para optimizar algoritmos cuánticos para hardware real sin sacrificar las propiedades caóticas necesarias para la seguridad.

En resumen, los autores han transformado un modelo teórico prometedor pero inaplicable en hardware actual (CAQW) en una solución práctica (LAQW) que combina eficiencia computacional, robustez ante el ruido y seguridad criptográfica.