Resumen
Kyber basa su seguridad en el problema Module-LWE (Learning With Errors sobre módulos), una variante del LWE clásico definido por Regev en 2005. Entender LWE es entender por qué Kyber es seguro y, más importante, hasta cuándo podría serlo.
El Problema LWE
Dado un secreto s, una matriz A y un vector de errores e:
s = vector secreto (dimensión n)
A = matriz aleatoria (m × n)
e = vector de error pequeño (muestreado de una distribución χ)
b = A·s + e (módulo q)
Problema de búsqueda (Search-LWE): Dados (A, b), encontrar s.
Problema de decisión (Decision-LWE): Dados (A, b), distinguir si b = A·s + e o si b es uniformemente aleatorio.
La seguridad depende de que, aunque A·s es determinista, el error e hace que el sistema sea dificilmente invertible. Sin e, sería álgebra lineal trivial.
Por qué es duro
Recuperar s de (A, b) es equivalente a resolver problemas de retículos (latices) que son NP-duros en el peor caso. La reducción de Regev (2005) mostró que romper LWE es al menos tan duro como ciertos problemas de retículos en el peor caso (GapSVP, SIVP).
Module-LWE
Kyber usa Module-LWE, donde A y s no son enteros escalares sino elementos de un módulo sobre un anillo de polinomios:
R_q = Z_q[x] / (x^n + 1)
Donde n = 256 para Kyber. La matriz A tiene entradas en R_q y dimensión k × k (donde k = 2, 3, 4 según el nivel de seguridad).
A ∈ R_q^{k×k}, s ∈ R_q^{k}, e ∈ R_q^{k}
b = A·s + e
Ventaja sobre LWE estándar: Module-LWE ofrece un equilibrio entre eficiencia (los anillos permiten multiplicación rápida via NTT) y seguridad (el módulo k controla la dimensión sin crecer al cuadrado).
¿Por qué módulo y no anillo completo?
Ring-LWE (usado por NewHope, por ejemplo) opera sobre un solo anillo (R_q). Module-LWE interpola entre LWE estándar y Ring-LWE:
| Esquema | Dimensión | Eficiencia | Seguridad conservadora |
|---|---|---|---|
| LWE estándar | n × k |
Baja | Alta |
| Ring-LWE | n |
Alta | Media |
| Module-LWE | n × k |
Alta | Alta |
La Distribución de Error
Kyber usa una distribución binomial centrada CBD(η) en lugar de una gaussiana discreta. Esto simplifica la implementación (no requiere muestreo de tabla) y evita ataques de temporización.
Pr[ e = x ] = (C(2η, η+x)) / 2^(2η)
Para ML-KEM-512: η = 2. Para ML-KEM-768 y 1024: η = 3.
El Módulo q = 3329
La elección de q = 3329 no es accidental:
- Es un primo tal que
q ≡ 1 (mod 2n)paran = 256, lo que permite usar NTT (Number Theoretic Transform) para multiplicación rápida enR_q. - Es lo suficientemente pequeño para que los ciphertexts y claves sean compactos.
- Es lo suficientemente grande para que el error no desborde y cause descifrados incorrectos.
La Conjetura Central
La seguridad de Kyber (y de toda la criptografía basada en retículos) descansa en la conjetura de que:
No existe un algoritmo cuántico (ni clásico) que resuelva Module-LWE para los parámetros de Kyber en tiempo polinomial.
Esta conjetura es plausible pero no demostrada. La historia de la criptografía enseña que las conjeturas de dureza a veces fallan. Lo que distingue a LWE de RSA/ECC es que no se conoce un análogo cuántico de Shor para retículos — pero eso no significa que no pueda descubrirse.
Referencias
- Regev, O. (2005). "On lattices, learning with errors, random linear codes, and cryptography." STOC 2005.
- Bos, J. et al. (2018). "CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM." EuroS&P 2018.
- Langlois, A. & Stehlé, D. (2015). "Worst-case to average-case reductions for module lattices." Designs, Codes and Cryptography.