Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

Este artículo presenta una implementación de circuito cuántico optimizada en cúbits del cifrado híbrido ligero ARX-SPN GFSPX y evalúa su seguridad postcuántica mediante un ataque de Grover paralelizado, revelando un costo cuántico total de $1.12 \times 2^{159}$ puertas que, aunque se sitúa por debajo de los umbrales del Nivel 1 del NIST, demuestra una resistencia superior en comparación con otros diseños ligeros.

Lo esencial

Imagina que tienes una cerradura digital muy especial y ligera (llamada GFSPX) diseñada para proteger datos en dispositivos pequeños como sensores inteligentes o etiquetas RFID. Esta cerradura está construida para ser rápida y consumir muy poca energía, lo que la hace perfecta para el "Internet de las Cosas".

Sin embargo, está surgiendo un nuevo tipo de "superherramienta" llamada Computadora Cuántica. A diferencia de las computadoras normales que comprueban las claves una por una, una computadora cuántica puede verificar muchas claves a la vez, potencialmente rompiendo estas cerraduras mucho más rápido. Este artículo plantea una pregunta sencilla: Si una computadora cuántica intenta romper esta cerradura específica, ¿qué tan difícil será realmente?

Aquí está el desglose de sus hallazgos utilizando analogías cotidianas:

1. El Diseño de la Cerradura: Un Motor Híbrido

La cerradura GFSPX no está construida con un solo tipo de mecanismo. Es un híbrido, como un automóvil que utiliza tanto un motor de gasolina como un motor eléctrico.

• La Parte de "Gasolina" (ARX): Utiliza operaciones matemáticas simples (Suma, Rotación, XOR) que son muy eficientes pero pueden ser un poco lentas al propagar cambios a través de los datos.
• La Parte "Eléctrica" (SPN): Utiliza una red compleja de sustitución (como barajar una baraja de cartas) que propaga los cambios muy rápidamente.
• El Resultado: Al combinarlas, la cerradura es rápida y eficiente. Los autores construyeron un plano digital de esta cerradura específicamente para una computadora cuántica para ver exactamente cómo funciona en su interior.

2. El Plano Cuántico: Construyendo el Circuito

Para probar la cerradura, los investigadores tuvieron que construir un "circuito cuántico". Piensa en esto como construir una fábrica en miniatura y reversible donde cada paso puede deshacerse perfectamente (para que no se pierda información).

• El Desafío: Las computadoras cuánticas son frágiles. No puedes simplemente copiar datos; debes tener mucho cuidado con los "qubits" (los bits cuánticos, como pequeños trompos giratorios).
• La Solución: Los investigadores optimizaron el diseño para utilizar la menor cantidad posible de qubits (209 de ellos). Utilizaron un truco inteligente llamado "sumador de acarreo en cascada" para las partes matemáticas, que es como una línea de ensamblaje muy eficiente que no desperdicia espacio.
• La Huella: El plano final es compacto, requiriendo un "piso de fábrica" de 209 qubits y un número específico de pasos (puertas) para ejecutar un cifrado completo.

3. El Ataque: La Búsqueda "Grover"

Para romper la cerradura, una computadora cuántica utiliza el Algoritmo de Grover.

• La Analogía: Imagina que tienes una biblioteca gigante con $2^{128}$ (un número tan enorme que es difícil de comprender) libros, y solo uno tiene la clave correcta.
  • Una computadora normal es como un bibliotecario que revisa un libro a la vez. Tomaría una eternidad.
  • Una computadora cuántica es como un bibliotecario mágico que puede revisar muchos libros simultáneamente. Encuentra el libro correcto en aproximadamente la raíz cuadrada del tiempo.
• La Trampa: Para asegurarse de que la computadora cuántica no elija el libro incorrecto (un "falso positivo"), los investigadores hicieron que la computadora verificara tres cerraduras diferentes (utilizando tres pares diferentes de mensajes cifrados/descifrados) al mismo tiempo. Si una clave abre las tres, definitivamente es la correcta.

4. El Veredicto: Fuerte, Pero No "Post-Cuántica"

Los investigadores calcularon el "costo" total de este ataque cuántico.

• El Costo: Descubrieron que romper la cerradura requeriría una cantidad masiva de potencia de cálculo, equivalente aproximadamente a $1.12 \times 2^{159}$ operaciones.
• El Estándar: El Instituto Nacional de Estándares y Tecnología (NIST) de EE. UU. ha establecido una "barrera de seguridad" para el futuro. Para considerarse verdaderamente segura contra computadoras cuánticas (Nivel 1 de seguridad), una cerradura necesita un costo de al menos $2^{170}$.
• El Resultado: La cerradura GFSPX está por debajo de la barra de seguridad. No es lo suficientemente segura para los estándares post-cuánticos más estrictos.
  • Sin embargo, el artículo señala que, en comparación con otras cerraduras ligeras, GFSPX es en realidad una de las más difíciles de romper. Se sitúa en un "punto dulce" donde es muy eficiente para dispositivos pequeños pero aún ofrece una resistencia decente contra ataques cuánticos, incluso si no supera la prueba de seguridad más alta.

5. La Conclusión

El artículo concluye que, aunque esta cerradura híbrida es excelente para dispositivos actuales con recursos limitados, el tamaño de clave de 128 bits es simplemente demasiado pequeño para sobrevivir a un ataque cuántico determinado en el futuro.

• El Compromiso: Puedes tener una cerradura que sea pequeña y rápida (buena para los sensores de hoy), o una cerradura que sea masiva y lenta (buena para la seguridad futura cuántica), pero este diseño específico intenta hacer ambas cosas y queda ligeramente corto en el frente de la "seguridad futura".
• Consejo Futuro: Para hacer que este diseño sea verdaderamente inmune a la computación cuántica, los autores sugieren ya sea hacer la clave más larga (como 192 o 256 bits) o ajustar las partes matemáticas para hacerlas aún más difíciles de procesar para las computadoras cuánticas.

En resumen: GFSPX es una cerradura muy inteligente y eficiente que es más difícil de crackear que la mayoría de sus pares, pero no es lo suficientemente fuerte para resistir las computadoras cuánticas superpoderosas del futuro sin algunas actualizaciones.

Resumen técnico

Resumen Técnico: Realización de Circuito Cuántico y Criptoanálisis de Grover del Cifrado Híbrido ARX-SPN GFSPX

Enunciado del Problema
La emergencia de la computación cuántica desafía fundamentalmente la seguridad de las primitivas de clave simétrica clásicas. Mientras que el algoritmo de Shor amenaza la criptografía de clave pública, el algoritmo de Grover proporciona una aceleración cuadrática para la búsqueda no estructurada, reduciendo efectivamente a la mitad el margen de seguridad de las construcciones de clave simétrica. En consecuencia, los cifrados de bloque ligeros (BC), diseñados para entornos con recursos limitados como el Internet de las Cosas (IoT) y la RFID, requieren una reevaluación rigurosa de su resistencia post-cuántica. Específicamente, existe la necesidad de cuantificar los recursos cuánticos requeridos para montar un ataque de recuperación de clave sobre diseños híbridos que combinan los paradigmas de Adición-Rotación-XOR (ARX) y Red de Sustitución-Permutación (SPN).

Metodología
Los autores presentan una realización integral de circuito cuántico y un criptoanálisis de Grover de GFSPX, un cifrado de bloque ligero que cuenta con un bloque de datos de 64 bits y una clave secreta de 128 bits. GFSPX utiliza una Estructura Feistel Generalizada (GFS) de 4 ramas que integra dos bloques funcionales distintos: una función basada en ARX ($F_1$) para no linealidad y una estructura SPN de 32 bits ($F_2$) para difusión rápida.

La metodología procede en tres etapas:

1. Realización de Circuito Cuántico: La estructura clásica de GFSPX se mapea en un circuito cuántico reversible. Los autores aprovechan la reversibilidad inherente de la red Feistel para minimizar el uso de qubits auxiliares.
   • $F_1$ (ARX): Implementada utilizando un sumador de acarreo en cascada (RCA) compacto basado en la arquitectura de Cuccaro et al. Este enfoque minimiza la sobrecarga de qubits omitiendo el bit de acarreo final para la suma modular y utilizando puertas de mayoría in situ (MAJ) y UnMajority-and-Add (UMA).
   • $F_2$ (SPN): La capa de S-box (basada en PRESENT) se sintetiza utilizando un conjunto mínimo de puertas CNOT y Toffoli sin auxiliares adicionales. La capa de permutación (capa P) se implementa mediante puertas SWAP paralelizables para mantener una profundidad de circuito baja.
   • Programa de Claves: El programa de clave maestra de 128 bits se realiza como una evolución unitaria que involucra una rotación cíclica izquierda de 113 bits, sustituciones de S-box y XORs de contador de ronda, optimizado para ejecución in situ.
2. Estimación de Recursos: El costo cuántico se calcula utilizando métricas de descomposición estándar (costo de NOT y CNOT = 1, costo de Toffoli = 6). El análisis evalúa tanto un costo base (excluyendo la sobrecarga de enrutamiento SWAP) como un límite superior (descomponiendo los SWAPs en tres CNOTs).
3. Criptoanálisis de Grover: Se construye un oráculo de Grover paralelo ($U_f$) para evaluar el cifrado frente a ataques de recuperación de clave. Para eliminar coincidencias espurias en el espacio de claves de 128 bits, el oráculo utiliza tres pares de texto plano-texto cifrado ($r=3$). La complejidad del ataque se estima escalando las métricas de recursos del oráculo por el número óptimo de iteraciones de Grover ($\approx \frac{\pi}{4}2^{64}$).

Contribuciones Clave

• Implementación Cuántica Optimizada: El artículo proporciona un circuito cuántico optimizado en qubits para GFSPX, logrando una huella de 209 qubits. El diseño alcanza un costo cuántico base de 32,498 puertas con una profundidad de circuito de 7,617.
• Análisis de Arquitectura Híbrida: El estudio detalla la distribución de recursos de un diseño híbrido ARX-SPN, demostrando que, aunque el primitivo de suma modular domina el conteo total de puertas, las capas de permutación paralelizadas en el componente SPN ayudan a mantener una relación puerta-profundidad competitiva.
• Evaluación Cuantitativa de Seguridad: Los autores construyen un oráculo de Grover utilizando tres pares de texto plano-texto cifrado y calculan el costo total del ataque bajo el marco MAXDEPTH de NIST. El análisis revela un costo total de ataque cuántico de aproximadamente $1.12 \times 2^{159}$ puertas para $r=3$.
• Comparación de Referencia: La implementación se compara con otros cifrados ligeros (por ejemplo, PRESENT, GIFT, SIMON, SPECK). GFSPX logra la relación costo-profundidad más baja (4.27) entre los diseños comparados, lo que indica una alta eficiencia de ejecución paralela.

Resultados

• Métricas de Recursos: El circuito completo de GFSPX de 20 rondas requiere 209 qubits. El costo base es de 32,498, aumentando a 47,789 cuando se incluye la sobrecarga de enrutamiento SWAP. La profundidad del circuito es de 7,617.
• Complejidad del Ataque: El costo cuántico total para un ataque de recuperación de clave se estima en $1.12 \times 2^{159}$ (para $r=3$).
• Clasificación de Seguridad: Bajo el marco de Criptografía Post-Cuántica de NIST, el umbral de seguridad de Nivel 1 (equivalente a AES-128) requiere un costo total de ataque de al menos $2^{170}$. El costo estimado para GFSPX ($2^{159}$) cae por debajo de este umbral.
• Compensaciones de Diseño: Aunque GFSPX demuestra una mayor resistencia al ataque cuántico que muchos diseños puramente SPN (que se agrupan alrededor de $2^{152}$), no cumple con los estrictos criterios de seguridad de Nivel 1 para una longitud de clave de 128 bits. El costo del diseño híbrido está fuertemente influenciado por el componente ARX (suma modular), situando su perfil de seguridad más cerca de los cifrados basados en ARX como SIMON y SPECK.

Significado
El artículo afirma que sus hallazgos proporcionan ideas críticas sobre el equilibrio entre la eficiencia del hardware clásico y la resistencia cuántica para los diseños criptográficos de próxima generación. El estudio destaca una compensación fundamental: mientras que las construcciones híbridas ARX-SPN ofrecen un rendimiento clásico robusto y una mejor resistencia cuántica que los diseños puramente SPN, una longitud de clave de 128 bits sigue siendo estructuralmente insuficiente para lograr la seguridad de Nivel 1 de NIST frente a adversarios cuánticos avanzados. Los autores sugieren que la investigación futura debe centrarse en extender las longitudes de clave (por ejemplo, a 192 o 256 bits) u optimizar los primitivos reversibles de suma modular para mejorar los márgenes de seguridad. La metodología establecida en este trabajo sirve como un marco riguroso para evaluar otros diseños híbridos en entornos con recursos limitados.