LWE (Learning With Errors)

Learning With Errors (LWE) is a computational problem that serves as the foundation for many modern cryptographic constructions, particularly those designed to be secure against quantum computers.

Definition

An LWE ciphertext is a pair $(b, a)$ where:

• $b \in \mathbb{Z}_q$ is a scalar
• $a \in \mathbb{Z}_q^N$ is a vector of $N$ elements

The phase (decryption result) is computed as:

$\mu = b + \langle a, s \rangle$

where $s$ is the secret key vector and $\langle \cdot, \cdot \rangle$ denotes the inner product.

Security

The LWE problem asks: given many samples $(a_i, b_i)$ where $b_i = \langle a_i, s \rangle + e_i$ for small errors $e_i$, recover the secret $s$.

This problem is believed to be hard even for quantum computers, making LWE a cornerstone of post-quantum cryptography.

Key Properties

• Worst-case to average-case reduction: LWE's hardness can be reduced to worst-case hardness of certain lattice problems
• Homomorphic: LWE ciphertexts support additive homomorphism naturally
• Noise growth: Operations increase noise; too much noise prevents correct decryption

Related Concepts

• RLWE - Ring variant with polynomial structure for efficiency
• Gadget Decomposition - Technique to control noise growth