Module Lattice Security (Part I): Unconditional Verification of Weber's Conjecture for $k \le 12$

Aquí presento un resumen técnico detallado del artículo "Unconditional Verification of Weber's Conjecture for k ≤ 12" (Verificación Incondicional de la Conjetura de Weber para k ≤ 12), escrito por Ming-Xing Luo.

1. El Problema: La Conjetura de Weber y su Relevancia Criptográfica

La conjetura de Weber (1886) establece que para todo entero $k \ge 1$, el número de clases del subcampo real máximo $K_k^+ = \mathbb{Q}(\zeta_{2^k} + \zeta_{2^k}^{-1})$ del cuerpo ciclotómico es igual a 1 (es decir, $h_k^+ = 1$).

Este problema es fundamental para la criptografía basada en retículos (Lattice-based Cryptography), que es la base de los estándares post-cuánticos finalizados por el NIST en 2024 (ML-KEM, ML-DSA, SLH-DSA). La resolución de esta conjetura afecta la seguridad en tres frentes críticos:

1. Problema del Ideal Principal (PIP): Si $h_k^+ = 1$, todos los ideales son principales. Esto podría permitir que algoritmos cuánticos resuelvan el PIP en tiempo polinomial, reduciendo la seguridad al "Problema del Generador Corto" (SGP).
2. Libertad de Módulos: En dominios de Dedekind, un módulo finitamente generado y sin torsión es libre si y solo si su clase de Steinitz es trivial. Si $h_k^+ = 1$, todos los módulos sobre el anillo de enteros son libres, una suposición clave en las pruebas de seguridad de ML-KEM y ML-DSA.
3. Reducciones de Peor Caso a Caso Promedio: La clase de número 1 simplifica el análisis de ruido y las reducciones de seguridad en Ring-LWE (R-LWE) y Module-LWE (MLWE).

Estado previo: Para $k \le 8$, la conjetura se había verificado incondicionalmente. Para $k \ge 9$, las verificaciones previas dependían de la Hipótesis de Riemann Generalizada (GRH), lo cual es insuficiente para garantizar seguridad incondicional en criptografía.

2. Metodología: Enfoque de Tres Etapas

El autor presenta la primera prueba incondicional para $k \le 12$. El método combina teoría de números algebraica avanzada y computación de alto rendimiento en tres etapas secuenciales para reducir el conjunto de posibles divisores primos del número de clases:

Etapa 1: Eliminación de Primos Pequeños (Tamiz de Fukuda-Komatsu)

• Objetivo: Eliminar todos los primos pequeños como posibles divisores de $h_k^+$.
• Método: Se utiliza el criterio de Wieferich aplicado a las unidades ciclotómicas.
• Resultado: Se demuestra computacionalmente que ningún primo $\ell < 10^9$ divide a $h_k^+$. Además, se establece que cualquier primo restante que divida a $h_k^+$ debe satisfacer la condición de congruencia fuerte $\ell \equiv \pm 1 \pmod{2^{k-1}}$. Esto reduce drásticamente la densidad de primos candidatos.

Etapa 2: Poda de Espacios Propios (Argumento de Coherencia de Normas)

• Objetivo: Eliminar la mayoría de los espacios propios (eigenspaces) en la descomposición del grupo de clases bajo la acción del grupo de Galois.
• Método: Se explota la estructura de torre del $\mathbb{Z}_2$-extensión ciclotómica ($K_8^+ \subset K_9^+ \subset \dots \subset K_{12}^+$).
• Lógica Inductiva: Asumiendo que $h_{k-1}^+ = 1$ (base $h_8^+ = 1$ ya probada), se demuestra que cualquier torsión $\ell$ en el grupo de clases de $K_k^+$ debe concentrarse exclusivamente en los espacios propios correspondientes a caracteres de orden completo (full-order characters). Los caracteres de orden inferior se eliminan inductivamente mediante el uso de mapas de norma entre los niveles de la torre.

Etapa 3: Acotación Finita (Teorema de Herbrand)

• Objetivo: Reducir el problema a una verificación finita de un conjunto computable de primos.
• Método: Se aplica el Teorema de Herbrand (y su extensión Ribet). Este teorema conecta la no nulidad de un espacio propio del grupo de clases con la divisibilidad de un número de Bernoulli generalizado ($B_{1,\psi}$).
• Resultado: Para cada carácter de orden completo restante, se calcula la norma del número de Bernoulli asociado. El teorema implica que si un primo $\ell$ divide a $h_k^+$, entonces $\ell$ debe dividir la norma de este número de Bernoulli.
• Acotación: Se utilizan cotas de segundo momento para demostrar que estas normas son enteros finitos y manejables (máximo 143 dígitos para $k=10$, y hasta 325 para $k=11$).

3. Contribuciones Clave y Resultados

1. Prueba Incondicional: Se demuestra que $h_k^+ = 1$ para $k \in \{9, 10, 11, 12\}$ sin depender de la Hipótesis de Riemann Generalizada.
2. Algoritmo de Verificación: Se propone un algoritmo (Algoritmo 1) que:
   • Calcula las normas de los números de Bernoulli.
   • Factoriza estos enteros grandes (usando métodos como ECM - Curva Elíptica y NFS - Tamiz de Campo Numérico).
   • Filtra los factores primos mediante las condiciones de congruencia.
   • Ejecuta pruebas de Wieferich para confirmar que los primos candidatos no dividen realmente al número de clases.
3. Optimizaciones Computacionales:
   • Reducción de Órbita Galois: Se demuestra que todos los pares conjugados de caracteres de orden completo generan la misma norma, reduciendo el número de factorizaciones necesarias de $n/4$ a 1 por capa de la torre.
   • Uso de Teorema de Thaine: Se menciona la posibilidad de usar primos auxiliares para generar anuladores adicionales, reemplazando la factorización de enteros grandes por cálculos de MCD polinomial en $\mathbb{F}_\ell$.

Resultados Numéricos:

• Para $k=10$ (relevante para ML-KEM/ML-DSA), el entero a factorizar tiene como máximo 143 dígitos.
• La verificación completa para $k \le 12$ es computacionalmente factible (minutos a semanas dependiendo de $k$, utilizando hardware estándar y algoritmos modernos).

4. Significado e Implicaciones para la Criptografía Post-Cuántica

La confirmación incondicional de $h_k^+ = 1$ para los parámetros utilizados en los estándares NIST tiene implicaciones profundas:

• Validación de Supuestos de Seguridad: Confirma que los módulos sobre los anillos de enteros de estos cuerpos son libres, lo cual es un requisito esencial para las reducciones de seguridad de Ring-LWE a Module-LWE. Sin esto, las pruebas de seguridad podrían tener brechas teóricas.
• Simplificación del Análisis de Ruido: La estructura de ideales principales simplifica el análisis de errores en Ring-LWE y la corrección de los algoritmos de descifrado (decapsulation) en ML-KEM.
• Resistencia a Ataques Cuánticos: Aunque la clase de número 1 hace que el Problema del Ideal Principal (PIP) sea trivialmente resoluble por algoritmos cuánticos, el artículo aclara que los estándares ML-KEM y ML-DSA se basan en Module-LWE, no en Ideal-LWE. La literatura actual (Peikert, Rosen, Brakerski, etc.) indica que Module-LWE resiste los ataques basados en PIP. Por lo tanto, la conjetura de Weber no debilita la seguridad de estos estándares, sino que fortalece la base teórica sobre la que se construyen sus pruebas de seguridad.
• Equivalencia PLWE-R-LWE: Garantiza que la equivalencia entre Ring-LWE y Polynomial-LWE (PLWE) se mantiene incondicionalmente para estos parámetros.

Conclusión

El artículo resuelve un problema abierto de más de 130 años para el rango de parámetros crítico en la criptografía moderna. Al combinar técnicas de la teoría de Iwasawa, teoría de caracteres y computación de números de Bernoulli, el autor elimina la dependencia de hipótesis no probadas (GRH) en la seguridad de los estándares post-cuánticos más importantes, proporcionando una base matemática sólida y verificable para la era post-cuántica.