Fundamentos de Learning With Errors (LWE)

Learning With Errors (LWE), de Regev (2005): dadas muchas ecuaciones lineales con ruido sobre Z_q, hay que encontrar el vector secreto s. El ruido e es pequeño, pero impide la eliminación gaussiana. Sin ruido, el sistema es sencillo; incluso con un ruido mínimo, se vuelve computacionalmente difícil.

Secreto s ∈ Z_q^n. El adversario recibe muestras (a_i, b_i), donde a_i ∈ Z_q^n es aleatorio, b_i = + e_i mod q y e_i es un ruido pequeño procedente de la distribución χ (por ejemplo, gaussiana con σ = √n). La tarea consiste en encontrar s a partir de un número polinómico de muestras.

Sin ruido: b_i = mod q. La eliminación gaussiana recupera s en O(n^3). Con ruido: incluso una sola ecuación incorrecta corrompe la eliminación. El ruido es lo bastante pequeño para que el descifrado funcione (usando la clave), pero lo bastante grande para impedir el criptoanálisis.

Regev demostró que LWE se reduce a problemas de retículas del peor caso (SIVP, GapSVP) mediante una reducción cuántica. Esto significa que, si se rompe LWE, se resuelven muchos problemas difíciles de retículas, pero no se conoce ningún algoritmo cuántico para estos problemas. LWE es seguro frente a la computación poscuántica.

RLWE sustituye Z_q^n por el anillo Z_q[x]/(f(x)), donde f es un polinomio ciclotómico. Una muestra de RLWE codifica n ecuaciones, lo que resulta mucho más eficiente. RLWE es la base de Kyber (KEM), Dilithium (firma) y los esquemas de HE BFV/BGV/CKKS.

La seguridad depende de: n (dimensión, normalmente 512-2048), q (módulo, 1024-2^60), σ (desviación estándar del ruido). A mayor n y menor razón σ/q, mayor es la dificultad. Las normas poscuánticas de NIST utilizan n=256 (dimensión del módulo) con k módulos (k=2,3,4).

Clave pública: (A, b=As+e). Cifrar el bit m: elegir r aleatoriamente y calcular el texto cifrado (u=A^T r, v = b^T r + m*q/2). Descifrar: v - s^T u = e^T r + m*q/2 ≈ m*q/2. Redondear al valor de m más cercano. El ruido e mantiene m oculto en el texto cifrado durante el cifrado.

LWE decisional: distinguir (a, As+e) de (a, u), donde u es uniformemente aleatorio. Son computacionalmente indistinguibles suponiendo la dificultad de LWE. Esta es la base de la seguridad semántica: los textos cifrados parecen ruido aleatorio para los adversarios que no tienen la clave secreta.

Los mejores ataques conocidos utilizan la reducción de retículas BKZ (Block Korkine-Zolotarev). Complejidad: subexponencial, pero no polinómica. BKZ-β requiere 2^{0.292β} operaciones. Para LWE-512: seguridad ≈ 128 bits frente a BKZ. No se conoce ninguna aceleración cuántica para BKZ.

Module-LWE (utilizado en Kyber) es RLWE sobre módulos de rango k. Proporciona flexibilidad: k=2 para una seguridad de 512 bits, k=3 para 768 bits y k=4 para 1024 bits. La seguridad y el rendimiento escalan con k. NIST seleccionó Kyber (renombrado ML-KEM) como estándar de PQC.

La seguridad de RSA/ECC se basa en la factorización de enteros o el logaritmo discreto, vulnerables a la computación cuántica mediante Shor. La seguridad de LWE se basa en problemas de retículas del peor caso, sin ninguna aceleración cuántica conocida. Tamaños de clave: claves LWE de ~1 KB frente a 256 bytes de RSA-2048. LWE ocupa más espacio, pero es resistente a la computación cuántica.

¿Qué hace que LWE sea difícil de resolver incluso con muchas muestras?

LWE: encontrar el secreto s a partir de ecuaciones lineales con ruido; es difícil incluso para un ordenador cuántico. RLWE utiliza anillos polinómicos para mejorar la eficiencia. Es la base de Kyber, Dilithium y los esquemas de HE. Siguiente: los esquemas de HE BGV y BFV para operaciones con enteros.