Predicting Module-Lattice Reduction

Resumen Técnico: Predicción de la Reducción de Módulos-Retículos

Planteamiento del Problema
El artículo aborda una pregunta crítica en la criptoanálisis de esquemas criptográficos basados en módulos-retículos (como los estándares del NIST ML-KEM, ML-DSA y FN-DSA): ¿Es la reducción de módulos-retículos (específicamente module-BKZ) más o menos eficiente que la reducción de retículos no estructurados (BKZ) cuando se les proporciona el mismo oráculo del Problema del Vector más Corto (SVP)?

Si bien trabajos teóricos fundacionales establecieron la existencia de variantes de módulo de LLL y algoritmos de reducción por bloques, se centraron en el comportamiento asintótico del peor caso. Una preocupación específica, resaltada como "Q8" en la sumisión de Kyber al NIST, plantea si la estructura algebraica de los retículos de módulo sobre cuerpos cíclotómicos podría permitir aceleraciones (por ejemplo, un factor de $d$ a $d^2$) o, por el contrario, si podría degradar la calidad de la base reducida en comparación con BKZ no estructurado. El artículo tiene como objetivo proporcionar un análisis concreto de caso promedio para responder si module-BKZ ofrece una ganancia o una pérdida en términos del tamaño de bloque $\beta$ requerido para lograr una calidad de base específica (pendiente).

Metodología
Los autores emplean un análisis basado en heurísticas apoyado por experimentos extensos para predecir la "pendiente" del perfil de la base tras ejecutar module-BKZ. La pendiente se define como la tasa de decaimiento en las normas logarítmicas de los vectores ortogonalizados de Gram-Schmidt.

1. Implementación Experimental: Los autores desarrollaron la primera implementación de código abierto de module-BKZ para cuerpos cíclotómicos (hasta conductor 16), utilizando las librerías existentes fplll y G6K. Abordaron desafíos técnicos relacionados con la preservación de la estructura de módulo durante la reducción de tamaño y el uso de una "incrustación cíclica" para asegurar que el producto interno de la traza sea compatible con las librerías estándar de reducción de retículos enteros.
2. Modelado Teórico (GSA de Módulos-Retículos): Extienden la Suposición de la Serie Geométrica (GSA), comúnmente utilizada para BKZ no estructurado, a los módulos-retículos. Esto implica modelar el perfil $K$ esperado (promediado sobre el grado $d$ del cuerpo numérico) de una base reducida.
3. Descomposición de la Pendiente: La pendiente predicha de module-BKZ se descompone en cuatro términos distintos ($t_1$ a $t_4$) que impulsan la desviación de BKZ no estructurado:
   • $t_1$ (Heurística de Gauss): La longitud esperada del vector más corto en un módulo-retículo aleatorio, ajustada por el número de raíces de la unidad ($\mu_K$).
   • $t_2$ (Brecha del Discriminante): Un término dependiente del discriminante $\Delta_K$ del cuerpo $K$.
   • $t_3$ (Brecha de Asimetría): Mide la desviación de la norma algebraica del vector respecto a su norma euclidiana (asimetría del vector a través de las incrustaciones).
   • $t_4$ (Brecha de Índice): Contabiliza el índice del ideal generado por el vector más corto dentro del módulo.
4. Análisis Asintótico: Los autores derivan una fórmula asintótica para el "tamaño de bloque equivalente" $\beta_{eq}$ requerido para que module-BKZ iguale la pendiente de BKZ no estructurado con un tamaño de bloque $\beta$.

Contribuciones Clave y Resultados

• Predicción Cuantitativa de la Pendiente: El artículo proporciona una fórmula concreta que predice la pendiente de module-BKZ como una función del tamaño de bloque $\beta$, el grado del campo $d$ y el discriminante del campo $\Delta_K$.
• El Discriminante como Impulsor: El análisis identifica el discriminante $\Delta_K$ como la cantidad principal que impulsa la diferencia de rendimiento. Específicamente, el término $\ln(|\Delta_K|/d^d)$ determina si module-BKZ gana o pierde eficiencia.
• Ganancia/Pérdida de Tamaño de Bloque Asintótico: Los autores derivan la siguiente relación asintótica para el tamaño de bloque equivalente $\beta_{eq}$:
  $$\beta_{eq} \approx \beta + \ln\left(\frac{|\Delta_K|}{d^d}\right) \frac{\beta}{d \ln \beta} + (d - 1)$$
  • Campos Cíclicos de Potencia de Dos: Para campos donde el conductor es una potencia de dos (relevante para los estándares actuales del NIST), $|\Delta_K| = d^d$. En consecuencia, el término logarítmico desaparece y el costo está dominado por el término lineal $d-1$. Esto implica que module-BKZ requiere un tamaño de bloque mayor por aproximadamente $d-1$ para lograr la misma pendiente que BKZ no estructurado. Esto confirma y cuantifica la preocupación planteada en la Q8 de Kyber, sugiriendo una ligera penalización de rendimiento en lugar de una aceleración.
  • Otros Campos Cíclicos: Para campos con factores primos impares en su conductor (por ejemplo, conductores de la forma $2^i \cdot 3^j$), $|\Delta_K| < d^d$. En estos casos, el término logarítmico es negativo, lo que produce una ganancia sublineal en el tamaño de bloque requerido ($\Theta(\beta / \ln \beta)$). Esto se traduce en una aceleración subexponencial en la complejidad del ataque.
• Validación Experimental: Los datos experimentales de los autores sobre varios cuerpos cíclotómicos ($\mathbb{Q}(\omega_3), \mathbb{Q}(\omega_4), \mathbb{Q}(\omega_{15}), \mathbb{Q}(\omega_{16})$) se alinean bien con sus predicciones. Los datos confirman que $\mathbb{Q}(\omega_3)$ y $\mathbb{Q}(\omega_{15})$ exhiben perfiles más planos (mejor reducción) en comparación con la línea base no estructurada, mientras que $\mathbb{Q}(\omega_{16})$ (potencia de dos) muestra un perfil peor.

Significancia y Reivindicaciones
El artículo afirma ser el primer trabajo en proporcionar un análisis concreto de caso promedio de module-BKZ, yendo más allá de los límites teóricos del peor caso. Su importancia radica en:

1. Resolución de Q8: Aborda directamente la pregunta abierta sobre la eficiencia de module-BKZ en campos cíclotómicos de potencia de dos, concluyendo que para estos campos específicos, la estructura de módulo no proporciona una aceleración sobre BKZ no estructurado; de hecho, incurre en una pequeña sobrecarga (requiriendo un tamaño de bloque mayor).
2. Identificación de Construcciones Alternativas: Destaca que los esquemas de módulos-retículos que utilizan conductores con pequeños factores primos impares (por ejemplo, 3, 5) pueden ser significativamente más débiles de lo que se pensaba, ya que la estructura algebraica proporciona una aceleración subexponencial para los ataques de reducción de retículos.
3. Herramientas Prácticas: Al proporcionar la primera implementación de código abierto de module-BKZ, los autores permiten una mayor experimentación y estimación de seguridad para los esquemas de módulos-retículos.

Los autores mantienen la modestia respecto a sus afirmaciones, señalando que su análisis depende de heurísticas (como la Suposición de la Serie Geométrica adaptada para módulos) y que aún existen brechas en el modelado de los fenómenos de "cabeza y cola" y la velocidad de convergencia del algoritmo. Expresan explícitamente que sus resultados aún no proporcionan un costo preciso para ataques específicos, sino más bien un marco predictivo para la pendiente de la base reducida.