Learning With Errors: el problema difícil

El problema Learning With Errors (LWE) fue introducido por Oded Regev en 2005 como fundamento de la criptografía poscuántica. Dada una matriz aleatoria A sobre Z_q y un vector b = As + e, el objetivo es encontrar el vector secreto s. El vector e es un error pequeño extraído de una distribución gaussiana discreta, lo que hace que el problema sea computacionalmente intratable.

En el problema LWE, A es una matriz aleatoria de m x n muestreada uniformemente sobre Z_q, donde q es un módulo primo. El secreto s es un vector de dimensión n, y e es un vector de error pequeño cuyos elementos se extraen de una distribución gaussiana estrecha. Incluso conocer la estructura de A no ayuda a un adversario a distinguir b de un vector uniformemente aleatorio.

Existen dos formulaciones estándar de LWE. LWE de búsqueda pide recuperar el secreto s a partir de muchas muestras (A, b). LWE decisional pide distinguir las muestras (A, As + e) de pares uniformemente aleatorios (A, u). Ambas formulaciones son polinómicamente equivalentes, lo que significa que un algoritmo que resuelva una puede transformarse para resolver la otra.

El término de error en LWE se extrae de una distribución gaussiana discreta sobre los enteros, parametrizada por la desviación estándar sigma. Los valores pequeños de sigma garantizan que e sea corto en comparación con q, lo que hace que b parezca casi igual a As mod q. Si sigma fuera cero, no habría error y el sistema podría resolverse mediante eliminación gaussiana; por tanto, el error es esencial para la dificultad.

Regev demostró una reducción extraordinaria: resolver muestras LWE del caso promedio es al menos tan difícil como resolver instancias del peor caso del problema del vector más corto (SVP) en retículos. Esto significa que, si se logra romper LWE de manera eficiente, se puede resolver cualquier problema de retículos eficientemente. No se conoce ningún algoritmo clásico o cuántico que resuelva SVP del peor caso en tiempo polinómico.

A diferencia de RSA y la criptografía de curvas elípticas, no se conoce ningún algoritmo cuántico que proporcione una aceleración exponencial contra LWE. El algoritmo de Grover ofrece como máximo una aceleración cuadrática, y los mejores algoritmos cuánticos para retículos, variantes de BKZ, no rompen LWE con parámetros elegidos correctamente. Esto convierte a LWE en una base sólida para la seguridad poscuántica.

La seguridad de LWE está determinada por tres parámetros: la dimensión n (longitud del secreto), el módulo q y la desviación estándar del error sigma. Un n mayor y una proporción q/sigma menor aumentan la seguridad. Para alcanzar una seguridad poscuántica de 128 bits, los valores habituales son n = 1024, q alrededor de 12289 y sigma alrededor de 3.2. La herramienta lattice estimator de Albrecht et al. se utiliza para evaluar la seguridad concreta.

El problema de la solución entera corta (SIS) es una suposición de dificultad relacionada, utilizada para firmas. Dada una matriz aleatoria A sobre Z_q, hay que encontrar un vector corto y distinto de cero x tal que Ax = 0 mod q. SIS constituye la base de las funciones hash y los esquemas de firma en el ámbito de los retículos, y complementa a LWE, que sustenta el cifrado y la encapsulación de claves.

Un esquema de cifrado LWE sencillo funciona de la siguiente manera: la clave pública es (A, b = As + e) y la clave secreta es s. Para cifrar un bit m, el remitente calcula (u, v) = (A^T r, b^T r + m * floor(q/2)) usando un vector binario aleatorio r. El descifrado calcula v - s^T u y redondea el resultado para recuperar m. Este esquema alcanza seguridad IND-CPA bajo la suposición LWE.

LWE ha permitido una amplia variedad de construcciones criptográficas más allá del cifrado básico. Entre ellas se incluyen el cifrado homomórfico completo (FHE), el cifrado basado en identidad (IBE), el cifrado basado en atributos (ABE) y los protocolos de intercambio de claves. CRYSTALS-Kyber (ahora ML-KEM, estandarizado como FIPS 203) es el esquema basado en LWE con mayor despliegue práctico.

La criptografía basada en LWE ya está llegando a los sistemas de producción. Google y Cloudflare realizaron experimentos de TLS usando Kyber entre 2018 y 2020. Chrome y Firefox añadieron compatibilidad con ML-KEM-768 en handshakes híbridos de TLS en 2024. Signal Protocol añadió una capa poscuántica (PQXDH) que utiliza ML-KEM-1024 para el secreto hacia adelante, protegiendo la confidencialidad de los mensajes a largo plazo frente a futuros ordenadores cuánticos.

¿Qué afirmación describe mejor la garantía de dificultad del problema LWE?

LWE es una de las suposiciones de dificultad poscuántica más estudiadas, respaldada por una sólida reducción desde problemas de retículos del peor caso. Sus tres parámetros (n, q, sigma) controlan el equilibrio entre seguridad y rendimiento. LWE resiste los ataques cuánticos y sustenta los esquemas estandarizados por NIST. Comprender LWE es la puerta de entrada a toda la criptografía moderna basada en retículos, incluidos ML-KEM y ML-DSA.