Ring-LWE y retículos modulares

LWE estándar requiere grandes productos de matriz por vector, lo que da lugar a claves de gran tamaño. Ring-LWE, introducido por Lyubashevsky, Peikert y Regev en 2010, sustituye los vectores y las matrices por polinomios en un anillo R_q = Z_q[X]/(f(X)). Este marco estructurado permite obtener claves mucho más compactas y una aritmética más rápida, lo que convierte a Ring-LWE en la base práctica de la criptografía de retículos del mundo real.

El polinomio f(X) utilizado en Ring-LWE suele ser f(X) = X^n + 1, donde n es una potencia de 2. Este es el polinomio ciclotómico de orden 2n. Se elige porque es irreducible sobre Z, garantiza que el anillo R_q tenga buenas propiedades algebraicas y permite utilizar la Transformada teórica de números (NTT) para realizar multiplicaciones eficientes. Los anillos ciclotómicos se han estudiado profundamente y se consideran seguros.

En Ring-LWE, el secreto s es un polinomio en R_q, y las muestras tienen la forma (a, b = a*s + e), donde a es un elemento aleatorio uniforme del anillo y e es un polinomio de error pequeño. El adversario observa muchas muestras de este tipo y debe recuperar s o distinguirlas de muestras uniformes. La dificultad se basa en la suposición Ring-LWE, que cuenta con una reducción desde problemas del peor caso en retículos ideales.

Ring-LWE ofrece mayor dificultad a un adversario, pero también cuenta con una reducción de seguridad ligeramente distinta de la de LWE convencional. La reducción parte de problemas del peor caso en retículos ideales (ideal-SVP), no de retículos arbitrarios. En principio, la estructura adicional de los retículos ideales podría hacer que fueran más fáciles que los retículos generales, y esta es un área de investigación activa. No se conoce ningún ataque práctico que aproveche esta estructura.

Module-LWE (M-LWE) generaliza LWE y Ring-LWE al trabajar con una matriz k x k de elementos del anillo en lugar de un único elemento del anillo o una matriz grande de enteros. Cuando k = 1, se reduce a Ring-LWE; a medida que k crece, se aproxima a LWE estándar. Este parámetro ajustable k permite equilibrar la confianza en la seguridad y el rendimiento.

CRYSTALS-Kyber (ahora ML-KEM, FIPS 203) se basa en Module-LWE con una matriz de rango k sobre R_q. El parámetro k controla directamente el nivel de seguridad: k=2 se orienta a una seguridad de 128 bits (ML-KEM-512), k=3 a 192 bits (ML-KEM-768) y k=4 a 256 bits (ML-KEM-1024). La estructura modular permite utilizar una única base de código y escalar la seguridad cambiando k.

La multiplicación de polinomios en R_q = Z_q[X]/(X^n + 1) es el cuello de botella del rendimiento. La Transformada teórica de números (NTT) es una transformada discreta de Fourier sobre Z_q que convierte los polinomios a una representación de evaluación, donde la multiplicación pasa a ser elemento a elemento. Con q elegido de modo que se pueda aplicar la NTT, la multiplicación de polinomios tarda O(n log n) en lugar de O(n^2), una optimización fundamental en ML-KEM y ML-DSA.

La NTT exige que q sea un número primo tal que q = 1 mod 2n, lo que garantiza que Z_q contenga una raíz primitiva de la unidad de orden 2n. Para ML-KEM con n = 256, q = 3329 cumple este requisito. La NTT sobre Z_3329 es extremadamente rápida en el hardware moderno con instrucciones SIMD, lo que permite realizar miles de operaciones de ML-KEM por segundo en CPU convencionales.

Ring-LWE y Module-LWE reducen drásticamente el tamaño de las claves en comparación con LWE estándar. Una clave pública LWE estándar para una seguridad de 128 bits podría ocupar 1 MB; Ring-LWE reduce este tamaño a unos 800 bytes, y Module-LWE (ML-KEM-768) logra una clave pública de 1184 bytes con una seguridad poscuántica de 192 bits. Esta compacidad hace que los esquemas reticulares sean prácticos para TLS y sistemas embebidos.

A algunos criptógrafos les preocupa que la estructura algebraica adicional de los anillos ciclotómicos pueda permitir ataques que no se aplicarían al LWE básico. En 2024, Elias Rokicki y sus colaboradores publicaron un análisis del polinomio ciclotómico de orden 2n, en el que no encontraron vulnerabilidades prácticas, pero destacaron la importancia de mantener un análisis continuo. El proceso de NIST para la PQC tuvo en cuenta este riesgo y eligió Module-LWE, en parte para reducir la dependencia de una única estructura de anillo.

Además de Kyber, Ring-LWE sustenta CRYSTALS-Dilithium (ML-DSA), el esquema de firma estandarizado por NIST. La biblioteca SEAL de Microsoft permite realizar cifrado homomórfico mediante Ring-LWE. La biblioteca criptográfica Tink de Google incluye compatibilidad con ML-KEM. Ring-LWE ha pasado de ser una construcción teórica a utilizarse en producción en un tiempo extraordinariamente corto, impulsado por el proceso de estandarización de NIST.

¿Cuál es la principal ventaja de Ring-LWE frente al LWE estándar?

Ring-LWE traslada LWE al anillo de polinomios R_q = Z_q[X]/(X^n+1), reduciendo drásticamente el tamaño de las claves y permitiendo operaciones aritméticas rápidas basadas en NTT. Module-LWE generaliza este enfoque mediante una estructura de rango k, en la que se fundamentan ML-KEM (FIPS 203) y ML-DSA (FIPS 204). El primo q = 3329, adecuado para NTT, permite una implementación eficiente. La seguridad se basa en la dificultad de problemas sobre retículos ideales y retículos modulares.