LWE and Lattice FundamentalsLWE and Lattice Fundamentals

Summary

Kyber bases its security on the Module-LWE (Learning With Errors over modules) problem, a variant of classical LWE defined by Regev in 2005. Understanding LWE means understanding why Kyber is secure and, more importantly, for how long it might be.

The LWE Problem

Given a secret s, a matrix A, and an error vector e:

s = secret vector (dimension n)
A = random matrix (m × n)
e = small error vector (sampled from a distribution χ)
b = A·s + e   (modulo q)

Search problem (Search-LWE): Given (A, b), find s.

Decision problem (Decision-LWE): Given (A, b), distinguish whether b = A·s + e or b is uniformly random.

Security depends on the fact that, although A·s is deterministic, the error e makes the system difficult to invert. Without e, it would be trivial linear algebra.

Why It Is Hard

Recovering s from (A, b) is equivalent to solving lattice problems that are NP-hard in the worst case. Regev's reduction (2005) showed that breaking LWE is at least as hard as certain worst-case lattice problems (GapSVP, SIVP).

Module-LWE

Kyber uses Module-LWE, where A and s are not scalar integers but elements of a module over a polynomial ring:

R_q = Z_q[x] / (x^n + 1)

Where n = 256 for Kyber. The matrix A has entries in R_q and dimension k × k (where k = 2, 3, 4 depending on the security level).

A ∈ R_q^{k×k},  s ∈ R_q^{k},  e ∈ R_q^{k}
b = A·s + e

Advantage over standard LWE: Module-LWE offers a balance between efficiency (rings allow fast multiplication via NTT) and security (the module k controls the dimension without growing quadratically).

Why Module and Not Full Ring?

Ring-LWE (used by NewHope, for example) operates on a single ring (R_q). Module-LWE interpolates between standard LWE and Ring-LWE:

The Error Distribution

Kyber uses a centered binomial distribution CBD(η) instead of a discrete Gaussian. This simplifies implementation (no table sampling required) and avoids timing attacks.

Pr[ e = x ] = (C(2η, η+x)) / 2^(2η)

For ML-KEM-512: η = 2. For ML-KEM-768 and 1024: η = 3.

The Modulus q = 3329

The choice of q = 3329 is not accidental:

• It is a prime such that q ≡ 1 (mod 2n) for n = 256, which allows using NTT (Number Theoretic Transform) for fast multiplication in R_q.
• It is small enough that ciphertexts and keys are compact.
• It is large enough that the error does not overflow and cause incorrect decryptions.

The Central Conjecture

The security of Kyber (and all lattice-based cryptography) rests on the conjecture that:

There exists no quantum (nor classical) algorithm that solves Module-LWE for Kyber's parameters in polynomial time.

This conjecture is plausible but unproven. The history of cryptography teaches that hardness conjectures sometimes fail. What distinguishes LWE from RSA/ECC is that no quantum analogue of Shor is known for lattices — but that does not mean one cannot be discovered.

References

• 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.