Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Este artículo presenta un ataque cuántico de tiempo polinómico que rompe los esquemas estandarizados ML-KEM, Falcon, Hawk y NTRU sobre anillos ciclotómicos de potencia de 2, aprovechando una descomposición en torres del Problema del Ideal Principal para lograr una alta probabilidad de éxito con un factor de aproximación verificado.

Lo esencial

La Gran Imagen: Un ganzúa cuántica para bóvedas digitales

Imagina que las bóvedas digitales más seguras del mundo (como las que protegen secretos gubernamentales o datos bancarios) están construidas utilizando un tipo específico de "laberinto" matemático. Estos laberintos se basan en formas complejas llamadas retículos. Actualmente, creemos que estos laberintos son demasiado grandes y retorcidos incluso para las supercomputadoras más rápidas de resolver, razón por la cual se consideran seguros para el futuro (Criptografía Post-Cuántica).

Este artículo afirma haber encontrado una llave maestra cuántica que puede desbloquear estos laberintos específicos mucho más rápido de lo que nadie pensaba posible. Los autores, liderados por Ming-Xing Luo, argumentan que una computadora cuántica no solo necesita ser "rápida"; necesita ser "inteligente" sobre la forma específica del laberinto. Al explotar un atajo geométrico oculto, pueden romper los esquemas de cifrado que NIST (el organismo de estándares de EE. UU.) seleccionó recientemente como el nuevo estándar global.

El Viaje de Cuatro Partes hacia la Solución

El artículo es la parte final de una serie de cuatro partes. Piénsalo como un equipo de cuatro detectives resolviendo un atraco masivo, donde cada detective resolvió una pieza diferente del rompecabezas:

1. Parte I (El Mapa): Demostraron que el "terreno" de estos laberintos es en realidad muy simple. Es como descubrir que un bosque aparentemente complejo es en realidad una cuadrícula donde cada camino conduce a un único claro central. Esto significa que no hay callejones sin salida ni bucles ocultos que confundan al atacante.
2. Parte II (La Traducción): Mostraron que puedes traducir el complejo problema "Módulo" (un laberinto 3D) a un problema "Ideal" más simple (un laberinto 2D) sin perder mucha información. Es como darte cuenta de que un rompecabezas 3D es solo un dibujo plano doblado; puedes desplegarlo fácilmente.
3. Parte III (La Regla): midieron el "ruido" en el sistema. En estos laberintos, siempre hay un poco de estática o borrosidad. Demostraron que esta borrosidad es tan pequeña y predecible que no oculta la solución. Es como darte cuenta de que la niebla en el bosque es tan fina que puedes ver claramente la señal de salida.
4. Parte IV (El Ataque - Este Artículo): Esta es la ejecución. Combinaron el mapa, la traducción y la regla en una sola receta paso a paso (un algoritmo) que una computadora cuántica puede seguir para romper el código.

Cómo Funciona el Ataque: La Analogía de la "Torre"

El núcleo de su ataque es un método llamado Torre Ciclotómica.

Imagina que estás intentando escalar una torre masiva de 256 pisos para llegar al piso superior donde se guarda el secreto.

• La Vieja Forma (Computadoras Clásicas): Intentas subir cada escalón uno por uno. Tomaría una eternidad (tiempo exponencial).
• La Forma Cuántica (El Método de los Autores): Se dieron cuenta de que la torre está construida en capas. En lugar de subir escalón por escalón, puedes tomar un ascensor que salta de un piso al siguiente, resolviendo un pequeño rompecabezas en cada parada.
  • Paso 1: Ve al 3er piso. Resuelve un pequeño rompecabezas.
  • Paso 2: Ve al 4to piso. Usa la respuesta del 3er piso para resolver un rompecabezas ligeramente más grande.
  • Paso 3: Repite esto hasta llegar a la cima.

Como la torre está construida en un patrón matemático específico (potencias de 2), este método de "ascensor" es increíblemente eficiente. Los autores prueban que una computadora cuántica puede realizar todo este ascenso en tiempo polinómico. En español llano: si la torre tiene 256 pisos, una computadora clásica podría tardar más que la edad del universo, pero una computadora cuántica podría hacerlo en el tiempo que tarda en prepararse una taza de café.

El Resultado: Rompiendo los Estándares

El artículo prueba este método contra los estándares de cifrado específicos que NIST eligió:

• ML-KEM (Kyber): El estándar principal para el intercambio seguro de claves.
• Falcon y Hawk: Estándares para firmas digitales (como una tarjeta de identificación digital).
• NTRU: Otra familia de esquemas de cifrado.

Los Hallazgos:
Los autores realizaron simulaciones y pruebas matemáticas que muestran que su algoritmo cuántico puede romper estos códigos con una tasa de éxito del 99%.

• Calcularon un "margen de seguridad". Imagina que la cerradura requiere una llave de 1.665 unidades de largo para romperse. Su llave cuántica tiene solo unas 103 unidades de largo.
• Como su llave es mucho más corta que la longitud requerida, la cerradura se abre fácilmente.

Afirman que todos los conjuntos de parámetros estandarizados para estos esquemas ahora se consideran "rotos" si existe una computadora cuántica a gran escala.

El Costo: ¿Qué tan grande es la Computadora Cuántica?

Podrías preguntarte: "¿Qué tan potente necesita ser esta computadora cuántica?".
Los autores hicieron las matemáticas sobre los recursos requeridos:

• Qubits (Bits cuánticos): Estiman que necesitas aproximadamente 1,4 millones de qubits físicos (lo que se traduce en aproximadamente 1.400 qubits "lógicos" o corregidos de errores).
• Tiempo: El cálculo tomaría una cantidad razonable de tiempo, aproximadamente equivalente al número de operaciones que una supercomputadora moderna realiza en unos pocos días, pero ejecutado por una máquina cuántica.

La Trampa:
Este es un avance teórico. Actualmente no tenemos computadoras cuánticas con 1,4 millones de qubits. Sin embargo, el artículo prueba que si construimos una, estos estándares de cifrado específicos no estarán seguros.

Resumen en Una Oración

Este artículo demuestra que un tipo específico de "laberinto" matemático utilizado en el cifrado seguro moderno tiene un atajo oculto que una futura computadora cuántica puede explotar, permitiéndole desbloquear el sistema con una llave mucho más pequeña y fácil de encontrar de lo que se creía anteriormente.

Resumen técnico

Resumen Técnico: Ataque Cuántico Polinómico Probabilístico sobre Module-LWE en Anillos Ciclotómicos de Potencia de 2

Planteamiento del Problema
El artículo aborda la seguridad de los esquemas criptográficos basados en Module-Learning With Errors (Module-LWE), centrándose específicamente en ML-KEM (anteriormente CRYSTALS-Kyber), estandarizado por el NIST, y en esquemas relacionados basados en retículos (Falcon, Hawk, NTRU) construidos sobre anillos ciclotómicos de potencia de 2 ($R = \mathbb{Z}[\zeta_{2^k}]$). El problema central es la recuperación de claves secretas mediante el Problema del Vector Más Corto (SVP) en retículos modulares. Mientras que los ataques clásicos dependen de algoritmos de reducción de retículos (por ejemplo, BKZ) con complejidad exponencial, el artículo investiga si un adversario cuántico puede explotar la estructura algebraica de los anillos ciclotómicos para resolver el Problema del Ideal Principal (PIP) y el Problema del Generador Corto (SGP) de manera eficiente.

Los autores identifican dos preguntas críticas sin resolver en trabajos anteriores (específicamente el ataque CDPR):

1. ¿Es el factor de aproximación logrado por el ataque CDPR suficientemente pequeño para romper claves secretas completas de ML-KEM (es decir, es $\gamma < q/2$)?
2. ¿Logra la subrutina cuántica subyacente de PIP una complejidad verdaderamente polinómica sin sobrecargas exponenciales ocultas o dependencia de la Hipótesis de Riemann Generalizada (GRH)?

Metodología
El artículo presenta una tubería de ataque unificada de cuatro fases (Algoritmo 1) que integra resultados de las Partes I–III de la serie con un nuevo algoritmo cuántico de tiempo polinómico para PIP (Parte IV).

1. Reducción de Módulo a Ideal: El ataque comienza reduciendo la instancia de Module-LWE a un Problema del Ideal Principal. Mediante una descomposición de Gram-Schmidt, la base del módulo se transforma en un producto de ideales principales. Los autores demuestran que la reducción introduce únicamente un factor constante $\alpha_d = O(1)$, independiente del rango del módulo $d$.
2. PIP de Torre Cuántica: En lugar de resolver el PIP directamente en el campo completo $\mathbb{Q}(\zeta_{2^k})$, los autores proponen una estrategia de "descomposición en torre". Descomponen el campo en una cadena de extensiones cuadráticas: $\mathbb{Q} \subset \mathbb{Q}(\zeta_8) \subset \dots \subset \mathbb{Q}(\zeta_{2^k})$.
   • En cada nivel $L$, el algoritmo resuelve el PIP para la extensión relativa utilizando el Problema del Subgrupo Oculto Abeliano (HSP).
   • Crucialmente, el número de nuevos generadores de unidades en cada nivel crece linealmente ($\Delta r_L = 2^{L-3}$), manteniendo el tamaño de la instancia del HSP polinómico.
   • Este enfoque evita la explosión de coeficientes inherente a las representaciones estándar de base de potencia y elimina la necesidad de la GRH, ya que se ha demostrado que el número de clases del subcampo real máximo es 1 para $k \le 12$.
3. CVP de Unidades Logarítmicas: Una vez encontrado un generador $g$ del ideal (que puede ser exponencialmente largo), el algoritmo calcula su incrustación logarítmica. Luego, resuelve el Problema del Vector Más Cercano (CVP) en el retículo de unidades logarítmicas para encontrar la discrepancia de unidad $\epsilon$ tal que $g = g_0 \epsilon$, donde $g_0$ es el generador corto.
   • Los autores utilizan el algoritmo del plano más cercano de Babai. Demuestran que, para generadores de anillo cortos, el vector objetivo se encuentra dentro del "radio de captura" del retículo, permitiendo que el algoritmo de Babai recupere la discrepancia de unidad exactamente.
4. Recuperación del Generador Corto: La unidad $\epsilon$ se reconstruye a partir de la solución del CVP, y el generador corto se recupera como $g_0 = g \cdot \epsilon^{-1}$.

Contribuciones Clave

• PIP Cuántico de Tiempo Polinómico: El artículo proporciona la primera construcción de un algoritmo cuántico de tiempo polinómico para el PIP sobre anillos ciclotómicos de potencia de 2. La complejidad es de $O(n^3 \log^2 n)$ puertas cuánticas y $O(n^2 \log n)$ qubits, donde $n$ es el grado del anillo. Esto elimina la sobrecarga exponencial previamente asociada con el algoritmo de Biasse-Song.
• Análisis de Factor de Aproximación Ajustado: Los autores derivan un factor de aproximación exacto $\gamma = \alpha_d \cdot \exp(\sigma_d \sqrt{2 \ln n})$. Demuestran que la varianza $\sigma_d$ de la incrustación logarítmica es $O(1)$ e independiente del módulo $q$.
• Verificación del Número de Clases: El trabajo se basa en la demostración (de la Parte I) de que el número de clases del subcampo real máximo es trivial ($h^+_k = 1$) para todo $k \le 12$, asegurando que cada ideal sea principal.
• Extensión a Múltiples Esquemas: El marco se extiende más allá de ML-KEM para analizar variantes de Falcon, Hawk y NTRU sobre anillos ciclotómicos de potencia de 2, demostrando que las mismas debilidades algebraicas se aplican.

Resultados
Los autores proporcionan estimaciones de seguridad concretas para conjuntos de parámetros estandarizados:

• ML-KEM-1024: El ataque logra un factor de aproximación mediano $\gamma_{med} \approx 21$ y un factor del percentil 99 $\gamma_{99\%} \approx 103$. Ambos valores están significativamente por debajo del umbral de seguridad de $q/2 = 1665$. La probabilidad de éxito se estima en $\ge 0.99$ para $d \le 3$ y $\ge 0.90$ para $d=4$, con una probabilidad de fallo reducible a $< 10^{-6}$ mediante repetición.
• Estimaciones de Recursos: Para ML-KEM-1024 ($n=256$), el ataque requiere aproximadamente $2^{27}$ puertas lógicas y $1.4 \times 10^6$ qubits físicos (asumiendo código de superficie con distancia 30).
• Otros Esquemas:
  • Falcon: El ataque rompe Falcon-512 y Falcon-1024 con márgenes de $72\times$ y $63\times$ respectivamente.
  • Hawk: El ataque rompe Hawk-512 y Hawk-1024. Hawk-256 se rompe condicionalmente; aunque el límite formal del 99% excede el umbral, las simulaciones empíricas muestran una tasa de éxito del 99.99%.
  • NTRU: El ataque se aplica a las variantes NTRU-HPS y NTRU-HRSS sobre anillos ciclotómicos de potencia de 2, logrando márgenes que van desde $11\times$ hasta $45\times$.

Significado y Afirmaciones
El artículo afirma resolver las preguntas abiertas sobre el ataque CDPR al demostrar que:

1. El factor de aproximación es lo suficientemente pequeño para romper todos los conjuntos de parámetros estandarizados de ML-KEM, Falcon, Hawk y NTRU sobre anillos ciclotómicos de potencia de 2 bajo un ataque cuántico.
2. El PIP puede resolverse en tiempo polinómico verdadero ($O(n^3 \log^2 n)$) sin factores exponenciales ocultos ni dependencia de conjeturas teóricas de números no probadas como la GRH.
3. La estructura algebraica de los anillos ciclotómicos de potencia de 2 permite a un adversario cuántico reducir el factor de aproximación de superpolinómico ($\approx 2^{54}$ en estimaciones anteriores) a subpolinómico ($\approx 2^{21}$), rompiendo efectivamente las suposiciones de seguridad de estos candidatos postcuánticos.

Los autores señalan que, aunque el ataque es probabilístico, la probabilidad de fallo es baja y puede mitigarse mediante repeticiones independientes. Enfatizan que los resultados dependen de las propiedades algebraicas específicas de los anillos ciclotómicos de potencia de 2 y de la trivialidad del número de clases para $k \le 12$.