Learning with errors explained: the hard problem behind lattice cryptography

Short answer: Learning with errors (LWE) is the problem of telling linear equations with added noise apart from random values, or of recovering the secret behind them. Published surveys say it is as hard as worst-case lattice problems that are believed hard even for quantum computers, which is why lattice-based cryptography is considered a post-quantum candidate. "Believed hard" is the key phrase: this is a conjecture backed by reductions, not a proof that no attack exists.

What the problem is

A 2021 survey on LWE and Ring-LWE describes the Learning with Errors problem as distinguishing linear equations with noise from uniformly sampled values. A survey from an MIT course frames the version that asks you to recover a secret vector, given an arbitrary number of independent samples that are linear equations in the secret with small random noise added. Without the noise the secret would be easy to find by ordinary linear algebra. The noise is what makes the problem hard.

Why it is considered hard

The 2021 survey says LWE enjoys a hardness reduction from worst-case lattice problems, which are believed to be hard for classical and quantum computers. The MIT survey puts it as LWE being as hard as worst-case lattice problems, so every construction based on it is secure under the assumption that worst-case lattice problems are hard.

That is an assumption, not a theorem. If someone found an efficient algorithm for those lattice problems, the security argument would fail. The papers cited here describe the problems as believed or conjectured to be hard.

Why people care for post-quantum cryptography

A 2015 survey of lattice cryptography lists the attractions of the field: apparent resistance to quantum attacks, in contrast with most number-theoretic cryptography, together with high asymptotic efficiency and parallelism, and security under worst-case intractability assumptions. It focuses on the short integer solution (SIS) and LWE problems and their more efficient ring-based variants.

Where Ring-LWE fits

The 2021 survey notes that plain LWE requires large key sizes and long computation times. To improve efficiency, Ring-LWE replaces linear equations with noisy ring products, and Ring-LWE and its variants are now frequently used to build post-quantum secure cryptosystems. The survey presents what it calls the strongest hardness result for Ring-LWE in the literature: a reduction from ideal lattice problems to its decision form. LWE has also allowed constructions such as fully homomorphic encryption and attribute-based cryptosystems.

What this does not tell you

This article explains the underlying problem at survey level. It does not describe any particular standard or product, and it makes no claim about specific parameter choices. Anyone relying on a scheme should read the relevant standard.

FAQ

What is learning with errors?

The problem of distinguishing linear equations with noise from uniformly random values, or of recovering the secret behind the noisy equations.

Why is it believed to be hard?

Surveys say it has a hardness reduction from worst-case lattice problems, which are believed to be hard for classical and quantum computers.

Is it proven secure against quantum computers?

No. The security rests on the assumption that the underlying lattice problems are hard, which is a conjecture.

What is Ring-LWE?

A variant that replaces linear equations with noisy ring products to improve efficiency over standard LWE.

What else is LWE used for?

The 2021 survey says it allows constructions such as fully homomorphic encryption and attribute-based cryptosystems.