Post-Quantum Cryptography and the NIST Competition

Post-quantum cryptography, usually shortened to PQC, is the project of building public-key cryptosystems whose trapdoor rests on a problem believed hard even for a quantum computer.

Two things about that definition are worth pinning down before going further.

It is not quantum cryptography. PQC schemes run on ordinary computers, the ones already on desks and in phones. There is a separate field, quantum key distribution, which uses quantum physics to build cryptography and needs specialised hardware and dedicated fibre. That is not this. PQC is classical software designed to resist a quantum attacker.

And "believed hard" is doing real work in that sentence. As the trapdoor note said, nobody can prove one-way functions exist at all. What can be said is that a problem has resisted sustained attack by people trying hard to break it, using both classical and quantum techniques. That is the standard, and it is the only standard available.

01.The competition

From 2016 through 2024, the U.S. National Institute of Standards and Technology ran an open competition to find replacements.

The format mattered as much as the outcome. It was public. Anybody could submit. Every submission was published in full, specification and reference implementation together, and anybody could attack anything. The rounds ran for years precisely so that attacks had time to mature.

That openness is not politeness. It is the only known way to get evidence about a hardness assumption. A scheme kept secret has not been tested, it has merely not been examined, and the two are easy to confuse from the inside.

The process worked as intended, including the parts that look like failure. Sixty-nine submissions entered the first round. Several well-regarded candidates were broken during the competition, some of them spectacularly. SIKE, an isogeny-based scheme that had reached the fourth round and was admired for its very small keys, was broken in 2022 by an attack that ran on a single classical core in about an hour. Rainbow, a multivariate signature finalist, fell similarly.

Those breaks are the competition delivering value. Each one happened before deployment rather than after.

02.The families that competed

Several mathematical foundations were in the running, and it is worth knowing the shape of the field even though this book follows only one branch.

Hash-based schemes build signatures out of nothing but hash functions. Their security assumptions are the most conservative available, because they need only that a hash function behaves like a hash function. The cost is size and statefulness.

Code-based schemes rest on the difficulty of decoding a random linear error-correcting code. The oldest of them, McEliece, dates to 1978 and has survived unbroken ever since, which is a remarkable record. The cost is a public key measured in hundreds of kilobytes.

Multivariate schemes rest on solving systems of multivariate polynomial equations. This family suffered the most casualties.

Isogeny-based schemes rest on relationships between elliptic curves and offered by far the smallest keys. This is where SIKE was broken.

Lattice-based schemes rest on problems about high-dimensional grids of points. This family won.

03.The standards

Three standards were published in 2024.

ML-KEM, standardised as FIPS 203 and originally submitted under the name Kyber, is a key encapsulation mechanism. It does the job Diffie-Hellman does, which is letting two parties establish a shared secret over an open channel. It is lattice-based.

ML-DSA, standardised as FIPS 204 and originally called Dilithium, is a digital signature algorithm. It does the job ECDSA does. It is lattice-based.

SLH-DSA, standardised as FIPS 205 and originally called SPHINCS$^+$, is also a signature scheme, but hash-based. It is deliberately the odd one out. Its security rests on completely different assumptions from the other two, so that a future break in lattice mathematics would not take down every standard at once. Its signatures are much larger and it is much slower, and it exists as insurance rather than as a default.

The naming is worth noting, because both conventions appear everywhere in the literature. Kyber and Dilithium are the names the schemes carried through the competition and are still what most papers and codebases say. ML-KEM and ML-DSA are the standardised names. They refer to the same schemes, with some parameter adjustments made during standardisation.

The "ML" prefix stands for module lattice, which points directly at the mathematics. A module is a structure built over the ring $R_q$ that Chapter 1 constructed. The name of the standard contains the reason Chapter 1 exists.

04.Why lattices won

Three criteria, and lattices were the only family strong on all three at once.

Security. The underlying problems have been studied since the 1990s, they have withstood both classical and quantum attack, and there is an unusual theoretical bonus: for certain lattice problems, breaking a randomly chosen instance is provably as hard as breaking the worst possible instance. Most cryptographic assumptions cannot say anything like that. It does not amount to a proof of security, since the worst case itself is only believed hard, but it removes an entire category of worry about unlucky parameter choices.

Size. ML-KEM ciphertexts are around a kilobyte. ML-DSA signatures run from about two to five kilobytes depending on parameters. These are larger than what they replace, and an elliptic-curve signature is sixty-four bytes, so the increase is substantial. But protocol designers can absorb a few kilobytes in a handshake. They could not absorb the hundreds of kilobytes a code-based public key would cost, which is why McEliece, despite its unmatched security record, did not become the general-purpose default.

Speed. This is where the family separated itself. Lattice arithmetic is polynomial multiplication in $R_q$, and polynomial multiplication has a fast algorithm, the Number Theoretic Transform. Well-implemented ML-KEM is competitive with, and in some operations faster than, the elliptic-curve schemes it replaces.

That last point is what turns this book from mathematics into engineering. The reason $R_q$ was chosen as the home for these schemes, out of all the algebraic structures available, is that multiplication inside it can be made fast. Chapter 4 is entirely about how.

05.Where this leaves the argument

The chain is now complete. Public-key cryptography needs a trapdoor one-way function. The two arithmetic problems that supplied one for fifty years both reduce to period-finding, and period-finding is what quantum interference does well. So both fail together. The replacement had to come from somewhere with no such structure, it had to be small enough to fit in real protocols and fast enough to deploy at scale, and lattices over $R_q$ were the only candidate family that satisfied all three.

Which is why a book about post-quantum cryptography opens with a chapter on polynomial rings.