Post-Quantum Cryptography Explained: Lattices and ML-KEM

Quick answer: Post-quantum cryptography (PQC) uses math problems believed to be hard for both classical and quantum computers. RSA and elliptic-curve cryptography could be broken by a large quantum computer running Shor’s algorithm, so NIST has standardized replacements built mainly on lattice problems. ML-KEM (FIPS 203) uses Module Learning With Errors to let two parties establish a shared secret key, and ML-DSA (FIPS 204) provides digital signatures. Neither is proven unbreakable, but no practical attack on either, classical or quantum, is known.

Facts checked November 22, 2026.

Your bank, messaging apps and browser are quietly switching to a new kind of math. The reason is a machine that does not exist yet: a large quantum computer that could break the encryption the internet has relied on for decades. The replacement, post-quantum cryptography, is mostly built on an idea you can understand with algebra you already know: equations with a little noise added.

Why We Need New Cryptography

Today’s public-key cryptography relies on two hard problems: factoring large numbers (RSA) and discrete logarithms on elliptic curves (ECC). In 1994, Peter Shor showed that a large quantum computer could solve both efficiently (see Shor’s algorithm explained). Published 2026 design estimates for breaking RSA-2048 have fallen to roughly 94,000 physical qubits (Iceberg Quantum’s Pinnacle design, assuming 0.1% error rates and 1-microsecond cycles), with some preprints claiming fewer under more optimistic assumptions. Because data recorded today could be decrypted later, a threat called “harvest now, decrypt later,” the switch has to happen before such a machine exists.

The New Standards

StandardNameJobHard problem
FIPS 203 (Aug 2024)ML-KEM (from CRYSTALS-Kyber)Agree on a secret keyModule Learning With Errors (lattices)
FIPS 204 (Aug 2024)ML-DSA (from CRYSTALS-Dilithium)Digital signaturesModule lattices
FIPS 205 (Aug 2024)SLH-DSA (from SPHINCS+)Backup signaturesSecurity of hash functions
FIPS 206 (in development)FN-DSA (from Falcon)Compact signaturesNTRU lattices
Selected March 2025 (standard in progress)HQCBackup key exchangeError-correcting codes

NIST’s final transition report, NIST IR 8547 (October 27, 2026), deprecates quantum-vulnerable public-key algorithms such as RSA and ECC after 2030 and disallows them under NIST standards after 2035. US federal high-value and high-impact systems face earlier requirements: post-quantum key establishment by December 31, 2030, and signatures by December 31, 2031. These are not deadlines for every private website, but they set the pace for industry.

What Is a Lattice?

Take two vectors in the plane, say \(\vec{b}_1 = (2, 0)\) and \(\vec{b}_2 = (1, 3)\). A lattice is every point you can reach by adding whole-number multiples of them: \(m\vec{b}_1 + n\vec{b}_2\) for integers \(m\) and \(n\). It looks like a slanted grid of dots. Two questions about lattices are very hard in high dimensions:

  • Shortest vector problem: find the nonzero lattice point closest to the origin.
  • Closest vector problem: given a point not on the lattice, find the nearest lattice point.

In two dimensions you can solve these by eye. In 500 or 1,000 dimensions, with a badly skewed set of basis vectors, the best known algorithms, classical or quantum, take time that grows exponentially with the dimension. For vector basics, see linear algebra for AI.

Learning With Errors: Equations Plus Noise

In 2005, Oded Regev introduced the Learning With Errors (LWE) problem, which is as hard as certain lattice problems. Each equation has the form \(b = \vec{a} \cdot \vec{s} + e \pmod{q}\), where \(e\) is a small random error. ML-KEM uses a structured version called Module-LWE. Start with a secret vector \(\vec{s}\) and work mod \(q\). Without errors, solving for \(\vec{s}\) is easy algebra. Here is a toy version with \(q = 17\) and secret \(\vec{s} = (2, 5)\):

Public \(\vec{a}\)\(\vec{a} \cdot \vec{s} \bmod 17\)Small error \(e\)Published \(b = \vec{a} \cdot \vec{s} + e \bmod 17\)
(3, 1)\(6 + 5 = 11\)+112
(4, 7)\(8 + 35 = 43 \equiv 9\)−18

An attacker sees only \((3, 1) \to 12\) and \((4, 7) \to 8\). Without the errors, two equations in two unknowns would give \(\vec{s}\) immediately by elimination. With small unknown errors, every guess for \(\vec{s}\) fits “approximately,” and in hundreds of dimensions with many equations, no known method separates the true secret from the noise efficiently. The errors are small enough not to matter to someone who knows \(\vec{s}\), but they destroy the shortcut for everyone else.

How Encryption Uses the Noise

In Regev-style encryption, a message bit is encoded by adding either 0 or about \(q/2\) to a noisy LWE value. With \(q = 17\), half is about 8. The receiver, who knows the secret, removes the masking and gets a number that is either near 0 or near 8:

  • Result 1: closer to 0 than to 8, so the bit is 0.
  • Result 9: closer to 8, so the bit is 1.

Distance here is measured around the “clock” mod 17, so 16 also counts as close to 0. Decryption works because the accumulated errors stay smaller than a quarter of \(q\); an attacker without the secret sees only numbers that look random. ML-KEM uses this idea with polynomials instead of single numbers: vectors of polynomials with 256 coefficients each, mod \(q = 3329\).

How ML-KEM Works in Three Steps

ML-KEM is a key-encapsulation mechanism: it does not encrypt your messages directly. It lets two parties agree on a shared secret key, which a fast symmetric cipher such as AES then uses to encrypt the data.

  1. Key generation: Alice creates a private key (a secret with small coefficients) and a public key (noisy Module-LWE equations built from it).
  2. Encapsulation: Bob uses Alice’s public key to wrap a random shared secret into a ciphertext and sends it.
  3. Decapsulation: Alice uses her private key to remove the noise and recover the same shared secret.

An eavesdropper sees the public key and the ciphertext, but recovering the secret would mean solving Module-LWE.

The Price: Bigger Keys

AlgorithmPublic keyCiphertext or signature
RSA-2048256-byte modulus256 bytes
X25519 (elliptic curve)32 bytes32 bytes
ML-KEM-7681,184 bytes1,088 bytes
ML-DSA-65 (signature)1,952 bytes3,309 bytes

(ML-KEM-768’s private key is 2,400 bytes.) Lattice keys are several times larger, but ML-KEM is very fast, so the cost is mostly a few extra kilobytes per connection.

Where It Is Already Used

  • Web browsers: Chrome and other major browsers use a hybrid key exchange combining X25519 with ML-KEM, so a connection stays safe if either one holds.
  • Messaging: Signal added post-quantum key agreement (PQXDH) in 2023, and Apple’s iMessage introduced its PQ3 protocol in 2024.
  • Governments: US federal agencies must move their most sensitive systems to post-quantum key establishment by the end of 2030.

Is Post-Quantum Cryptography Guaranteed Safe?

No cryptography is proven unbreakable. Confidence comes from decades of failed attacks. That is why NIST chose several different math foundations: lattices for the main standards, hash functions for SLH-DSA and error-correcting codes for HQC. In 2022, a different candidate, SIKE, which used isogenies of elliptic curves, was broken with an ordinary laptop in about an hour, a reminder of why diversity matters.

Common Misconceptions

“Post-quantum cryptography needs a quantum computer.” No. It runs on ordinary phones and laptops; it is designed to resist quantum attackers. It is also different from quantum key distribution, which uses physics instead of math, and it still depends on careful implementation.

“Quantum computers will break all encryption.” Symmetric ciphers such as AES-256 and lattice-based schemes have no known efficient quantum attack.

“There is plenty of time.” Data encrypted today with RSA or ECC could be stored and decrypted later, which is why migration is already under way.

Watch: Lattices and Post-Quantum Cryptography

If you learn better by watching, these videos are worth your time.

Lattice-based cryptography: The tricky math of dots (Chalk Talk). A clear visual introduction to lattices and why they are hard.
Learning with errors: Encrypting with unsolvable equations (Chalk Talk). The LWE idea from this article, animated step by step.
Post Quantum Cryptography – Computerphile (Computerphile). Why the migration is happening now.

Check Your Understanding

Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.

Answer each question and press Submit to see your result right away.

1. With s = (2, 5) and a = (3, 1), what is a · s mod 17?
Found a bug? Let us know!
2. With a = (4, 7), what is a · s mod 17?
Found a bug? Let us know!
3. Why do LWE equations add small errors?
Found a bug? Let us know!
4. Does ML-KEM directly encrypt your messages?
Found a bug? Let us know!
5. In toy decryption with q = 17, a result of 9 decodes to which bit?
Found a bug? Let us know!

Frequently Asked Questions

What is post-quantum cryptography?

Cryptography designed to resist attacks by large quantum computers, which could break RSA and elliptic-curve cryptography. It runs on ordinary computers and is based on problems such as lattices that have no known efficient quantum attack.

What is lattice-based cryptography?

Encryption based on hard problems about lattices, grids of points in many dimensions, such as finding the closest lattice point. ML-KEM and ML-DSA are lattice-based.

What is Learning With Errors?

A problem introduced by Oded Regev in 2005: recover a secret from many linear equations mod q that each have a small random error added. It is believed hard even for quantum computers.

What are the NIST post-quantum standards?

FIPS 203 (ML-KEM) for key establishment, FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) for signatures, published in August 2024. FN-DSA (FIPS 206) is in development, and HQC, selected in March 2025, is being standardized as a backup.

How does ML-KEM work?

Alice publishes a public key made of noisy lattice equations. Bob uses it to encapsulate a random shared secret in a ciphertext. Alice uses her private key to recover the secret, which then keys a fast cipher such as AES.

When will RSA be replaced?

NIST IR 8547, finalized October 27, 2026, deprecates RSA and other quantum-vulnerable public-key algorithms after 2030 and disallows them under NIST standards after 2035.

Is my browser already using post-quantum encryption?

Probably. Chrome and other major browsers use hybrid key exchange that combines classical X25519 with ML-KEM for many connections.

Keep Exploring

Sources and Further Reading

Related to This Article

What people say about "Post-Quantum Cryptography Explained: Lattices and ML-KEM - Effortless Math"?

No one replied yet.

Leave a Reply