Learning With Errors (LWE) Foundation

Learning With Errors (LWE) by Regev (2005): given many noisy linear equations over Z_q, find the secret vector s. The noise e is small but prevents Gaussian elimination. Without noise, the system is easy; with even tiny noise, it becomes computationally hard.

Secret s ∈ Z_q^n. Adversary receives samples (a_i, b_i) where a_i ∈ Z_q^n random, b_i = + e_i mod q, e_i small noise from distribution χ (e.g., Gaussian with σ = √n). Task: find s given polynomially many samples.

Without noise: b_i = mod q. Gaussian elimination recovers s in O(n^3). With noise: even one wrong equation corrupts elimination. The noise is small enough that decryption works (using the key), but large enough to prevent cryptanalysis.

Regev proved LWE reduces to worst-case lattice problems (SIVP, GapSVP) with quantum reduction. This means: if LWE is broken, many hard lattice problems are solved — but no quantum algorithm is known for lattice problems. LWE is post-quantum secure.

RLWE replaces Z_q^n with the ring Z_q[x]/(f(x)) for a cyclotomic polynomial f. One RLWE sample encodes n equations — much more efficient. RLWE is the basis for Kyber (KEM), Dilithium (signature), and BFV/BGV/CKKS HE schemes.

Security depends on: n (dimension, typically 512-2048), q (modulus, 1024-2^60), σ (noise standard deviation). Larger n and smaller σ/q ratio = harder. NIST Post-Quantum standards use n=256 (module dimension) with k modules (k=2,3,4).

Public key: (A, b=As+e). Encrypt bit m: choose random r, compute ciphertext (u=A^T r, v = b^T r + m*q/2). Decrypt: v - s^T u = e^T r + m*q/2 ≈ m*q/2. Round to nearest m. Noise e keeps the ciphertext hiding m during encryption.

Decision-LWE: distinguish (a, As+e) from (a, u) where u is uniform random. Computationally indistinguishable assuming LWE hardness. This is the semantic security basis — ciphertexts look like random noise to adversaries without the secret key.

Best known attacks: BKZ (Block Korkine-Zolotarev) lattice reduction. Complexity: sub-exponential but not polynomial. BKZ-β requires 2^{0.292β} operations. For LWE-512: security ≈ 128 bits against BKZ. No quantum speedup known for BKZ.

Module-LWE (used in Kyber) is RLWE over modules of rank k. Provides flexibility: k=2 for 512-bit security, k=3 for 768-bit, k=4 for 1024-bit. Security and performance scale with k. NIST selected Kyber (renamed ML-KEM) as the PQC standard.

RSA/ECC security: based on integer factoring/discrete log (quantum-vulnerable via Shor). LWE security: based on worst-case lattice problems (no known quantum speedup). Key sizes: LWE keys ~1 KB vs RSA-2048 256 bytes. LWE is larger but quantum-safe.

What makes LWE hard to solve even with many samples?

LWE: find secret s from noisy linear equations — quantum-hard. RLWE uses polynomial rings for efficiency. Basis for Kyber, Dilithium, and HE schemes. Next: BGV and BFV HE schemes for integer operations.