up:: The New Standards MOC

Lattice-Based Cryptography

Lattice-based cryptography is the family of post-quantum cryptography whose security rests on the hardness of certain problems in high-dimensional lattices, the geometric equivalent of finding the shortest or closest point in a vast grid of dots when you can only see a skewed, misleading map of it. It’s the mainstream of the post-quantum transition: the two finalized NIST standards for the two jobs public-key cryptography does, ML-KEM for key establishment and ML-DSA for signatures, are both lattice-based, and the compact signature standard FN-DSA is too. Lattices won that position because they hit the sweet spot classical cryptography set the bar at: fast, reasonably sized, and, as far as anyone can show, hard for a quantum computer.

The short version:

• Lattice-based cryptography secures data on the difficulty of geometry problems in high-dimensional grids, mainly finding an unusually short vector or the closest grid point when the lattice is described by a deliberately bad basis.
• It’s the only post-quantum family that covers both jobs at once: it does key establishment (ML-KEM) and signatures (ML-DSA, FN-DSA), which is a big part of why it became the default.
• It resists Shor’s algorithm because lattice problems have none of the periodic, number-theoretic structure that Shor’s needs to break RSA and elliptic-curve cryptography.
• Its cost is size: lattice keys and signatures are much larger than the elliptic-curve ones they replace, so the integration work is about bytes on the wire rather than compute.
• It’s a younger assumption than hash-based cryptography, which is exactly why NIST also standardized a non-lattice backup, the code-based KEM HQC, in case a future break ever weakens the lattice line.

Picture a city laid out as a perfect infinite grid of streetlamps, stretching in every direction, including dimensions you can’t draw. If someone hands you the tidy north-south, east-west directions, finding the lamp nearest any point you name is trivial. Now imagine you’re only ever given a terrible set of directions, two long diagonal avenues that still technically reach every lamp but wind all over the place first. With that skewed map, finding the lamp closest to a given spot, or the lamp closest to the center, becomes staggeringly hard as the number of dimensions climbs into the hundreds. Lattice cryptography lives in that gap. The public key is the bad map anyone can use to garble a message; the private key is the good map that snaps everything back to the nearest lamp. A quantum computer doesn’t hand an attacker a good map.

How does lattice-based cryptography work?

Lattice-based cryptography builds its security on how hard it is to answer simple-sounding geometry questions about a lattice when you’re only given a misleading description of it. A lattice is the set of all whole-number combinations of a handful of basis vectors, which produces a regular grid of points in n-dimensional space. Two questions about that grid anchor the whole family:

1. The Shortest Vector Problem (SVP). Find the shortest nonzero vector in the lattice, the grid point nearest the origin. In high dimensions, with a bad basis, there’s no known efficient way to do it, classically or quantumly.
2. The Closest Vector Problem (CVP). Given an arbitrary point in space, find the lattice point nearest to it. Same story: easy with the hidden good basis, brutally hard with the public bad one.

Most deployed schemes don’t use raw SVP or CVP directly. They use an averaged, noise-hardened cousin that’s far more convenient to build with, the Learning With Errors problem. LWE hands you a stack of linear equations whose answers have been fuzzed with small random errors and asks you to recover the secret. Pulling the secret back out of that noise is equivalent to solving a hard lattice problem, and the noise is precisely what makes decryption hard for anyone without the private key.

The mechanism, across the lattice family, has a consistent shape:

1. Key generation. You build a lattice you can navigate because you hold a short, well-behaved basis (the trapdoor), then publish a scrambled, long-vector version of it as your public key. It describes the same lattice, but it’s useless for finding short or close vectors.
2. Encapsulation or encryption. A sender uses your public key to encode a secret into a lattice equation and adds a bounded burst of small errors on top. Adding the noise is trivial and needs nothing but the public key.
3. Decapsulation or decryption. You use your private short basis to strip the noise away and recover the secret. Without it, recovering the secret means solving LWE, which means solving the hard lattice problem underneath.

That recovered secret then feeds ordinary symmetric cryptography and key derivation, the same downstream flow as any other KEM. Signatures work in a mirror image: instead of hiding a secret in noise, the signer produces a short vector that satisfies a lattice equation tied to the message, and a verifier checks that the vector really is short and really does fit. There’s no factoring and no discrete logarithm anywhere in this, which is the whole point.

Source: NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard, August 2024, which standardizes ML-KEM on this Module-LWE basis; NIST FIPS 204, Module-Lattice-Based Digital Signature Standard, August 2024, which builds ML-DSA on Module-LWE and Module-SIS.

What hard problems is it built on?

The family rests on a small set of related lattice problems, and the “module” and “ring” versions are the ones that actually ship, because they’re fast enough for real protocols. Conceptually there are three pillars:

1. Learning With Errors (LWE) and Module-LWE. Recover a secret from noisy linear equations. This is the confidentiality workhorse, and Module-LWE is the structured, efficient variant that ML-KEM is built on. ML-DSA leans on it too.
2. Short Integer Solution (SIS) and Module-SIS. Find a short vector that satisfies a lattice equation. This is the signature-side problem, and Module-SIS is one of the two assumptions ML-DSA rests on.
3. NTRU. An older lattice construction from the 1990s with its own compact, efficient structure. It sits outside the primary key-establishment portfolio, and it’s the basis of the FALCON signature scheme that became the compact standard FN-DSA.

The “module” or “ring” qualifier is doing real work. Plain LWE and SIS are conservative but heavy. Wrapping them in algebraic rings or modules (Module-LWE, Ring-LWE) shrinks the keys and speeds the arithmetic dramatically, which is what makes lattice cryptography fast enough to be the default rather than a laboratory curiosity. The tradeoff is that the extra structure is, in principle, extra surface for a future attack to grab, which is a live thing cryptographers watch rather than a known weakness.

Source: NIST FIPS 204, August 2024 (Module-LWE and Module-SIS as the ML-DSA basis); FALCON/NTRU lineage of FN-DSA per NIST IR 8547, Transition to Post-Quantum Cryptography Standards, initial public draft, November 2024.

Why does it resist both classical and quantum attack?

Lattice-based cryptography resists quantum attack because the one quantum algorithm that actually demolishes today’s public-key cryptography, Shor’s algorithm, needs a specific kind of hidden periodic structure that lattices don’t have. Shor’s algorithm breaks RSA and elliptic-curve cryptography by turning factoring and the discrete logarithm into a period-finding problem, which a quantum computer solves in polynomial time. Lattice hardness has no such period to find. The shortest and closest vector problems are geometric, not number-theoretic, so Shor’s has nothing to hook into.

The remaining quantum lever is Grover’s algorithm, which speeds up brute-force search quadratically. That’s a real but modest discount, not a break, and the NIST parameter sets are chosen with Grover-style quantum search already priced in, so the security categories hold up against it.

The honest caveat is that the more serious question isn’t quantum at all. It’s whether a future advance in classical cryptanalysis could chip away at the hardness of Module-LWE or the structured lattice problems. NIST and the academic community watch that continuously, the standardized parameter sets carry deliberate margins, and the whole reason a non-lattice backup exists is to answer the “what if” honestly rather than pretend it away.

Source: NIST FIPS 203, August 2024, which sets ML-KEM parameters to account for quantum search and states the quantum-resistance basis.

Why did lattices become the mainstream post-quantum family?

Lattices became the default because they were the only candidate that did everything the transition needed at a workable cost. Three things stacked up in their favor:

1. They cover both jobs. Public-key cryptography does key establishment and it does signatures, and lattice math produces strong schemes for both. Code-based cryptography does key establishment but has no widely standardized signature; hash-based cryptography does signatures but has no KEM at all. Lattices are the one family that answered the whole question.
2. They’re practical. Structured (module and ring) lattices are fast on ordinary hardware, and their keys and signatures, while larger than elliptic-curve ones, are small enough to deploy in real protocols like TLS. That balance of speed and manageable size is exactly what a mainstream default needs.
3. They held up under scrutiny. Lattice problems have been studied since the 1990s, and after an intense multi-year NIST evaluation the lattice submissions came through as the well-analyzed, well-understood choice for the primary standards.

So when NIST finalized the first post-quantum standards in August 2024, lattice-based ML-KEM and ML-DSA were the headline picks, and the ecosystem, browsers, TLS libraries, HSM vendors, cloud providers, started building around them first.

Source: NIST FIPS 203 and NIST FIPS 204, both finalized August 13, 2024.

Which NIST standards are lattice-based?

Three of the four signed-and-sealed NIST post-quantum algorithm standards are lattice-based. The one exception is the conservative hash-based signature standard, which deliberately uses a different foundation.

Standard	Algorithm	Job	Lattice problem	Status
FIPS 203	ML-KEM	Key establishment	Module-LWE	Finalized August 13, 2024
FIPS 204	ML-DSA	Signatures (general-purpose)	Module-LWE + Module-SIS	Finalized August 13, 2024
FIPS 206	FN-DSA	Signatures (compact)	NTRU lattices	Draft; not finalized in the November 2024 work
FIPS 205	SLH-DSA	Signatures (conservative)	Hash-based, not lattice	Finalized August 13, 2024

The pattern to hold onto: if you’re deploying the NIST primary defaults for both confidentiality and signing today, you’re almost certainly running lattice cryptography, because ML-KEM and ML-DSA are both lattice-based. FN-DSA adds a compact lattice signature for size-constrained roles, but it was still in draft in NIST’s late-2024 signature work, so it’s a design-for, not a deploy-today. The lone non-lattice standard, SLH-DSA, is there on purpose, as the conservative anchor whose security doesn’t depend on lattice math at all.

Source: NIST FIPS 203, NIST FIPS 204, NIST FIPS 205, all August 2024; FN-DSA draft status per NIST IR 8547, November 2024.

What are the tradeoffs?

The strengths and the costs of the lattice family are both easy to name.

1. Strength: coverage. It’s the only family that standardizes both a KEM and signatures, so a whole migration can lean on one well-studied foundation instead of stitching several together.
2. Strength: performance. Structured lattices are fast on mainstream hardware. The compute is rarely the bottleneck; the schemes were chosen partly because signing, verification, and key exchange are all quick enough for everyday use.
3. Cost: size. Lattice keys, ciphertexts, and signatures are much larger than the elliptic-curve artifacts they replace. An ML-KEM-768 public key runs over a kilobyte where an elliptic-curve public key is 32 bytes, so the integration work lands on bandwidth, certificate size, protocol handling, and storage.
4. Cost: a younger assumption. Lattice problems are well-studied, but not with the multi-decade, hammered-relentlessly confidence of a plain hash function. That’s the honest gap between this family and hash-based cryptography, and it’s the reason mature programs keep a non-lattice option in view.
5. Cost: implementation care. Lattice arithmetic carries its own side-channel and correctness pitfalls, from constant-time noise handling to the rejection-sampling loops in signing, so hardening the implementation is real engineering rather than a compile flag.

Source: ML-KEM-768 public-key size (1,184 bytes) from NIST FIPS 203, August 2024.

Where does lattice-based cryptography sit among the families?

Lattices are the center of gravity, and the other post-quantum families are best understood as answers to the question “what if the center ever cracks.” Because ML-KEM, ML-DSA, and FN-DSA all draw on the same broad lattice assumptions, a single future advance against lattices, classical or quantum, could weaken several primary standards at once. That’s an efficient design and a real concentration, and the whole point of standardizing more than one mathematical foundation is to make sure a bad day for lattices isn’t a bad day for the entire estate.

The two neighbors that matter most:

1. Code-based cryptography rests on the hardness of decoding random error-correcting codes, a foundation completely separate from lattices. NIST selected the code-based KEM HQC in March 2025 explicitly as the non-lattice backup for ML-KEM, so that if lattices were ever weakened, there’s a ready alternative that a lattice break wouldn’t touch.
2. Hash-based cryptography rests only on the strength of a hash function, the single most-studied primitive in the field, which gives it the strongest long-term confidence of any option. It does signatures only, and it’s the conservative anchor for long-lived roots of trust where you want maximum assurance and can absorb a large signature.

That post-quantum candidates really can fall is not hypothetical. The isogeny-based scheme SIDH/SIKE was a serious NIST contender until it was broken by an ordinary classical computer in 2022 and withdrawn. Lattices show no such crack, but that history is exactly why keeping independent families available, the instinct behind crypto-agility, is the right one.

Source: NIST, “NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption”, March 11, 2025; SIDH/SIKE break in W. Castryck and T. Decru, “An Efficient Key Recovery Attack on SIDH,” 2022, IACR ePrint 2022/975.

Common misconceptions

“Lattice-based means it can be broken like the other math families.” No lattice-based standard has been broken. The cautionary tale people remember, SIDH/SIKE falling in 2022, was isogeny-based, a different family entirely. Lattices remain the well-analyzed primary choice; the reason a backup exists is prudent hedging, not a known weakness.

“Lattice cryptography is only for encryption.” It covers both halves of the transition. ML-KEM does key establishment and ML-DSA and FN-DSA do signatures, which is precisely the coverage that made lattices the mainstream family.

“All the NIST post-quantum standards are lattice-based.” Three of the four finalized-and-drafted standards are, but SLH-DSA is deliberately hash-based, and the code-based KEM HQC was selected as a non-lattice backup. Treating the whole portfolio as lattice-only misses the diversity that was designed into it on purpose.

“The big keys mean lattice cryptography is slow.” Size and speed are separate axes. Lattice schemes are fast on ordinary hardware; the cost is the larger bytes on the wire and in certificates, which is a bandwidth and protocol-handling problem, not a compute one.

“LWE and NTRU are unrelated to each other.” They’re different constructions, but both are lattice problems. LWE and its module variant underpin ML-KEM and ML-DSA, while NTRU underpins the FALCON-derived FN-DSA. All of it is the same family resting on the hardness of high-dimensional lattice geometry.

Questions people ask

Is lattice-based cryptography safe against quantum computers? As far as the current science shows, yes. Shor’s algorithm, which breaks RSA and elliptic-curve cryptography, relies on periodic structure that lattice problems don’t have, and Grover’s algorithm offers only a modest search speedup that the NIST parameter sets already account for. The standardized lattice schemes have no known practical break.

Which NIST standards are lattice-based? ML-KEM (FIPS 203) for key establishment, ML-DSA (FIPS 204) as the general-purpose signature, and FN-DSA (FIPS 206) as the compact signature. The conservative signature standard SLH-DSA (FIPS 205) is hash-based, not lattice-based.

What’s the difference between LWE, Module-LWE, and Ring-LWE? They’re the same underlying idea (recover a secret from noisy linear equations) at different levels of algebraic structure. Plain LWE is the most conservative and the heaviest; Ring-LWE and Module-LWE add ring or module structure to shrink keys and speed the math, which is what makes them practical enough to standardize. ML-KEM and ML-DSA use the module variant.

Why are lattice keys and signatures so much bigger than RSA or elliptic-curve? The security comes from working in high-dimensional lattices, and describing points and vectors in those spaces simply takes more bytes than a single elliptic-curve coordinate. An ML-KEM-768 public key is over a kilobyte where an elliptic-curve one is 32 bytes. It’s the defining integration cost of the family, and it lands on bandwidth and storage rather than processing time.

If lattice cryptography is so dominant, why did NIST also pick HQC? Because relying on one mathematical family for the primary standards is a concentration, and a single future break against lattices could weaken several standards at once. HQC is code-based, so a lattice break wouldn’t affect it, which makes it a genuine backup rather than a redundant second lattice scheme.

Is lattice cryptography less trustworthy than hash-based cryptography? It’s a younger assumption. Hash-based security rests on the single best-understood primitive in the field, so it carries the strongest long-term confidence, but it only does signatures and its signatures are large. Lattices are well-studied and cover both jobs at practical sizes, which is why they’re the default; hash-based is the conservative reserve for the highest-assurance, longest-lived signing.

Do I have to understand lattice math to migrate to ML-KEM and ML-DSA? No. The algorithms arrive through cryptographic libraries and providers (TLS stacks, OpenSSL, HSM firmware), so the migration work is about integration, sizing, and testing, not implementing lattice arithmetic yourself. Understanding the family helps you reason about why the standards exist and where the concentration risk sits.

---

Lattice-based cryptography is the ground most of the post-quantum transition is built on, and understanding it explains why ML-KEM and ML-DSA are the defaults, what their security assumptions actually mean, and why a non-lattice backup still earns its place on the roadmap. Everything here is the map, given freely. When your team needs to decide how the lattice standards get sized and sequenced into your own protocols and estate, that’s what an alignment briefing is for.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.