What does a quantum computer have no trick for, and what does the replacement weigh?
What Shor's algorithm takes and what it leaves, the two families of replacement (lattices and hashes) and what they weigh, and the order in which a real system moves. This is the section the tools on the post-quantum page put into practice.
A lattice is the set of all whole-number combinations of a few basis vectors, a regular grid of points. The same grid can be described by a short, tidy basis or by a long, skewed one, and the trouble is that the skewed description is easy to produce and very hard to undo. Given only the skewed basis, find the shortest nonzero vector in the lattice is the shortest vector problem (SVP), and in high dimensions it is believed to be hard even for quantum computers. That is the first reason to build cryptography on it: Shor's algorithm needs a hidden period, and no hidden period is known for a lattice.
The scheme the new standards use is built on a close cousin: learning with errors (LWE), introduced by Oded Regev in 2005. Take a secret vector s and publish many noisy linear equations in it: each is a random vector a and the value a·s plus a small random error. With no error, ordinary elimination recovers s from enough equations. With the error, every equation is slightly wrong and elimination collapses into a haystack. Regev showed, by a reduction that itself uses a quantum algorithm, that solving LWE would also solve certain worst-case lattice problems, which is the kind of link between a cryptosystem and a clean mathematical problem that RSA does not have.
The price is size. Lattice keys are not 32 or 64 bytes: they are kilobytes, because a whole matrix of numbers has to be published. And the honesty clause matters. Nobody has proved LWE is hard for quantum computers. In April 2024 a paper claimed a fast quantum algorithm for it; a bug was found within days, the author acknowledged he could not repair it and withdrew the claim. The standard parameters were never in its scope, and the question stays open.
The lattice in the figure. The vectors (3, 1) and (−1, 3) have determinant 3·3 − 1·(−1) = 10, and the skewed pair (−2, 16) and (−1, 13) have determinant (−2)(13) − (16)(−1) = −10. Equal magnitude and each skewed vector an integer combination of the good ones (for instance (−2, 16) = (3, 1) + 5·(−1, 3)) means the two bases generate the same points. The short vectors have length √10 ≈ 3.16 against about 16.1 for the longest skewed one.
Learning with errors, in miniature. Work modulo q = 97 with four unknowns. Four noiseless equations a·s = b (mod 97) fix s by elimination. Replace each b with b + e, where e is −1, 0 or +1, and the same elimination returns a different, wrong vector, because the errors have been mixed into the answer. With seven noisy equations the true s can still be found here by checking all 974 = 88,529,281 candidates against them, which is a toy. Real parameters make the dimension so large that no search, quantum or classical, is feasible.
What the replacement weighs. NIST's FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA) are built on module-lattice versions of this. Sizes in bytes:
X25519 public key 32 ML-KEM-768 public key 1,184 (37 ×) ML-KEM-768 ciphertext 1,088 ML-DSA-65 signature 3,309 (52 × ECDSA P-256's 64)
1,184 ÷ 32 = 37 exactly, and 3,309 ÷ 64 ≈ 51.7. The Size Cliff on the post-quantum page measures these on the wire rather than trusting a table.
Your next connection, perhaps ML-KEM is standardised (FIPS 203, August 2024), and the hybrid X25519MLKEM768 key exchange of topic 10 is already offered by current browsers and servers. The desk measured in August 2026 that OpenSSL 3.5 negotiates it by default.
Play the problem Lattice Heist is the two- and three-dimensional version of the shortest-vector problem with the fewest-moves answer proven for every level; it shows the mechanism, and says plainly that it measures nothing about how hard the real thing is. Real lattice parameters live in hundreds of dimensions with noise added.
Check yourself
The lattice figure shows the same points with a bad basis and a good basis. Why does that help cryptography?
Producing a long skewed description of a lattice is easy and undoing it is believed hard in high dimension, even for quantum computers. That is believed, not proved: nobody has shown it, and a 2024 claim to the contrary was withdrawn in practice.