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.