Learning with errors (toy LWE encryption)

How it works

Learning with errors (LWE) asks to recover a secret $s \in \mathbb{Z}_q^n$ from many noisy inner products $b_i = a_i \cdot s + e_i \bmod q$, where the $a_i$ are uniform and the errors $e_i$ small. Without the errors Gaussian elimination would solve it; with them, Regev showed that it is as hard as worst-case lattice problems, which are believed to resist quantum computers.

Regev’s encryption of one bit $\mu$ uses $(A, b)$ as public key. The sender adds up a random subset $S$ of the samples, $u = \sum_{i \in S} a_i$ and $v = \sum_{i \in S} b_i + \mu \lfloor q/2 \rfloor$. The receiver computes $v - u \cdot s = \sum_{i \in S} e_i + \mu \lfloor q/2 \rfloor \bmod q$ and rounds: near 0 means 0, near $q/2$ means 1.

Decryption is correct as long as the accumulated noise $\sum_{i \in S} e_i$ stays below $q/4$ in absolute value. Larger errors make the scheme fail, smaller ones make it insecure, and parameters balance the two. The toy sizes here offer no security; Kyber (ML-KEM), standardized by NIST in 2024, uses module LWE in dimension 512 to 1024 with $q = 3329$ and packs a whole key into one ciphertext.