Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Lattices
Hardness assumptionKE: gives key exchangeTD: gives trapdoor functions

LWE

In plain words

Solve equations where every answer has a little random noise added. The noise is what makes it hard.

The idea: Take a secret list of numbers s and publish many equations of the form "a · s ≈ b", each with a small random error added, in remainder arithmetic. Without the errors, school elimination would find s instantly. With them, the errors snowball through the elimination and nothing useful comes out. To everyone else the equations look like random numbers. Encryption hides a message as a big jump on top of the noise: the key holder, who knows s, removes everything except a small error, and the big jump still shows through.

Why it matters: The foundation of ML-KEM, encryption that computes on data, and much more.

Noise that only the key holder can see through
Without the secret0q/2With the secretread as 0read as 10q/2
Think of numbers modulo q as positions on a clock. Each dot is one encrypted bit. To an eavesdropper (left) the values land anywhere. The key holder (right) subtracts what the secret explains and is left with just a little noise: bits that were 0 end up near 0 (blue), bits that were 1 near q/2 (red). As long as the noise stays small, rounding to the nearer half reads every bit correctly.

The details

On the map: learning with errors

Learning with errors: solve linear equations modulo q where every equation carries a small random error, like LPN but with bigger numbers. Regev (2005) showed[1, 2] it is as hard as worst-case lattice problems, against quantum algorithms.

It is remarkably versatile: key exchange, encryption, fully homomorphic encryption and much more (KE). Used without extra structure it gives FrodoKEM[3].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

About the tags

KE
This assumption gives key exchange on its own, so it needs more than one-way functions and falls if public-key encryption is impossible.
TD
This assumption gives trapdoor functions on its own (computable by anyone, invertible only with a secret), so it falls if trapdoor functions don't exist. Schemes built on it need not use a trapdoor: ElGamal doesn't.

References

  1. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, 2005. doi:10.1145/1060590.1060603
  2. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 2009. doi:10.1145/1568318.1568324
  3. Joppe Bos, Craig Costello, Leo Ducas et al. Frodo: Take Off the Ring! Practical, Quantum-Secure Key Exchange from LWE. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. doi:10.1145/2976749.2978425