PLAIN QUANTUM
Quick answer

What is lattice-based cryptography?

By Muhammad Atif4 min readReviewed 12 October 2026
The short answer

Lattice-based cryptography is the family of maths behind most of the new post-quantum standards: ML-KEM for agreeing keys, and ML-DSA and FN-DSA for signatures. A lattice is simply a regular grid of points. The security comes from a puzzle about such grids that's easy to set but, as far as anyone knows, extremely hard to solve, for quantum computers as well as ordinary ones.

The puzzle, in two dimensions

Take a grid of points, skewed at an awkward angle. Pick one point as a secret, nudge it a small random distance off the grid, and share only the nudged position. The challenge is to work back to the grid point it came from.

TWO DIMENSIONS: A GRID AND A NUDGE the secret grid point what's shared: the nudged position
The puzzle in two dimensions. Given only the ring, find the grid point it came from. Here you can do it by eye, which is why real schemes don't use two dimensions.

On a flat page that's easy. The trick is that the same puzzle can be set in hundreds of dimensions, where there's nothing to see by eye.

Why size makes it hard

Every extra dimension multiplies the number of grid points near any spot. Real schemes use grids with hundreds of dimensions; ML-KEM-768, the version most widely deployed today, works in 768.

NEIGHBOURING GRID POINTS AROUND ONE SPOT 1 dimension2 2 dimensions8 3 dimensions26 768 dimensions (ML-KEM-768): a number with 367 digits and that's only the points right next door
Why size matters. Each extra dimension roughly triples the grid points surrounding any spot. ML-KEM-768 works in 768 dimensions, where even listing the immediate neighbours is far beyond any computer. Real attacks are cleverer than checking neighbours one by one, which is why the standards' sizes are set by years of public analysis of the best known attacks.

The same idea, as equations

In practice the standards express the puzzle as equations rather than pictures. The secret is a list of numbers. Anyone can be given equations involving it, but each answer has a small random error added. That version is called learning with errors, and it's what ML-KEM and ML-DSA rest on.

EXACT 2a + 3b = 29 5a + b = 27 3a + 4b = 40 any two pin downthe secret: 4 and 7 WITH SMALL ERRORS 2a + 3b = 30 +1 5a + b = 26 −1 3a + 4b = 40 0 no exact fit;hard at scale
The same idea as equations, which is how ML-KEM and ML-DSA are actually built. The secret is a list of numbers. Exact equations give it away with school algebra; add a small random error to each answer and the problem, known as learning with errors, becomes extremely hard once there are hundreds of unknowns and the arithmetic wraps around.

Why quantum computers don't break it

Shor's algorithm breaks RSA and elliptic-curve cryptography because those problems hide a repeating pattern, and quantum interference is very good at finding repeating patterns. Lattice problems have no known pattern of that kind. The best known quantum attacks on them are only modestly better than ordinary ones, which is why the standards could be set at sizes that stay secure against both.

That rests on decades of research and years of intense public analysis during NIST's selection process, plus results linking these problems to well-studied questions about lattices. It isn't a proof that no attack exists; no widely used cryptography has one. It's the same kind of confidence that today's algorithms earned.

Common confusions

  • "Lattice cryptography needs a quantum computer." No. It's ordinary maths running on ordinary computers; it's designed to resist quantum computers.
  • "ML stands for machine learning." No. It stands for module lattice, a structured kind of lattice that keeps keys and calculations manageable.
  • "All the new standards are lattice-based." Most, not all. SLH-DSA is built only on hash functions and HQC on error-correcting codes, deliberately, so one breakthrough can't knock out everything.
  • "Bigger grids just mean slower encryption." Mostly they mean bigger keys and messages. Speed is generally fine; size is the main practical cost.

Sources and further reading

Tags show what kind of source each one is (how sources are used). Checked against these sources on 12 October 2026. Spotted an error? Email hello@plainquantum.com and it will be corrected, with a note.

  1. StandardFIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM)NIST, 2024
  2. StandardFIPS 204: Module-Lattice-Based Digital Signature Standard (ML-DSA)NIST, 2024
  3. Peer-reviewed paperOn lattices, learning with errors, random linear codes, and cryptographyOded Regev, Journal of the ACM, 2009
  4. StandardPost-Quantum Cryptography project (status of FN-DSA and other work)NIST Computer Security Resource Center
← All quick answersNext: What is ML-KEM? →