Introduction to Post-Quantum Cryptography (PQC)

TL;DR

NIST finalized its first three post-quantum standards in August 2024: FIPS 203 (ML-KEM, key encapsulation, from CRYSTALS-Kyber), FIPS 204 (ML-DSA, signatures, from CRYSTALS-Dilithium), and FIPS 205 (SLH-DSA, hash-based signatures, from SPHINCS+, kept as a structurally independent backup). The first two rest on lattice problems — informally, on the fact that finding a short vector or a nearby point in a high-dimensional grid of points is computationally hard. Their core hardness assumption is Learning With Errors (LWE): given $b = \langle a, s \rangle + e \pmod q$ for a public random $a$, secret $s$, and small noise $e$, recovering $s$ is easy without $e$ (plain linear algebra) and hard with it, because $e$ turns exact linear-equation solving into a nearest-lattice-point search. Unlike factoring or discrete log, lattice problems have no known periodic algebraic structure for Shor's algorithm's quantum Fourier transform to exploit — the best known quantum attacks (lattice sieving) only shave a Grover-style quadratic factor off an exponential running time, not collapse it to polynomial.

The NIST Standardization Process

NIST opened its post-quantum cryptography competition in 2016, evaluating submissions across four rounds of public cryptanalysis. In July 2022 it announced the first four algorithms selected for standardization; in August 2024 it published the finalized standards:

• FIPS 203 — ML-KEM (Module-Lattice-based Key-Encapsulation Mechanism, standardizing CRYSTALS-Kyber). A key encapsulation mechanism — the direct replacement for RSA and (EC)DHE key exchange in TLS.
• FIPS 204 — ML-DSA (Module-Lattice-based Digital Signature Algorithm, standardizing CRYSTALS-Dilithium). The primary replacement for RSA and ECDSA certificate and handshake signatures.
• FIPS 205 — SLH-DSA (Stateless Hash-based Digital Signature Algorithm, standardizing SPHINCS+). A signature scheme built entirely from hash functions, with no lattice assumption at all.

ML-KEM and ML-DSA are both lattice-based, sharing the same underlying hardness assumption. SLH-DSA exists specifically to avoid putting all signature security behind that one assumption: its security reduces only to the collision and preimage resistance of the underlying hash function, a far older and more thoroughly studied kind of hardness. If a structural weakness were ever found in lattice problems, SLH-DSA's signatures would remain unaffected — the standardization process deliberately hedges across independent mathematical foundations rather than betting entirely on one.

Lattices, Short Vectors, and Close Vectors

A lattice is the set of all integer linear combinations of a set of basis vectors $\mathbf{b}_1, \dots, \mathbf{b}_n \in \mathbb{R}^m$:

The same lattice — the same infinite set of points — has infinitely many valid bases. Two problems on this structure anchor essentially all lattice-based cryptography:

• Shortest Vector Problem (SVP): find the shortest nonzero vector in $L$.
• Closest Vector Problem (CVP): given an arbitrary target point $t \in \mathbb{R}^m$ not necessarily in $L$, find the lattice point closest to it.

Both are easy in two or three dimensions by inspection. Neither is easy in the hundreds of dimensions used by ML-KEM and ML-DSA — the best known algorithms (lattice basis reduction methods such as LLL and BKZ) take time exponential in the lattice dimension $n$ to find short vectors with any reliability, and that exponential wall is what these schemes' security parameters are built against.

A Basis Reveals — or Hides — the Short Vector

The same lattice looks either easy or hard to attack depending entirely on which basis you're handed. A good basis — short, close to orthogonal — makes the shortest vector visually obvious. A bad basis — long, nearly parallel vectors — generates the identical set of points but gives no visual or algebraic shortcut to the short vector hiding inside it.

Both pairs of arrows generate exactly the same set of dots — the bad-basis vectors are integer combinations of the good-basis vectors, and vice versa. SVP is the problem of recovering the green vectors' length when all you were handed is the red basis. In two dimensions this is a solved problem (LLL reduction finds the good basis in polynomial time). In the hundreds of dimensions ML-KEM operates in, no known algorithm does this efficiently — reduction algorithms either run in exponential time or return a vector only polynomially short, not the true shortest one.

Learning With Errors

Regev's LWE problem builds a cryptographic primitive directly on top of CVP's hardness. Fix a modulus $q$, a secret vector $s \in \mathbb{Z}_q^n$, and a narrow noise distribution $\chi$ (typically a discrete Gaussian concentrated near zero). A single LWE sample is:

Given $m$ such samples, stack them into matrix form:

Without the noise term, recovering $s$ from $(A, \mathbf{b})$ is trivial linear algebra: with $m \geq n$ independent samples, Gaussian elimination solves $A\mathbf{s} = \mathbf{b}$ for $s$ in polynomial time. With the noise term, the system is no longer exactly consistent, and there is no linear operation that removes $e$ without knowing it in advance. Worse for an attacker, any linear combination of equations sums the noise terms proportionally to the combination's coefficients — so any attempt to eliminate variables the way Gaussian elimination would amplifies rather than cancels the error. Recovering $s$ reliably requires finding the specific combination of samples for which the accumulated noise stays small relative to $q$ — which is exactly a bounded-distance decoding instance: find the lattice point (generated by $A$'s columns) closest to $\mathbf{b}$. LWE's average-case hardness is not assumed in isolation — Regev proved a reduction from worst-case lattice problems (approximate SVP and the shortest independent vectors problem) to average-case LWE, so an efficient LWE solver would imply an efficient solver for the worst case of the underlying lattice problem generally.

Search LWE asks for $s$ itself; decision LWE — the version cryptographic security proofs actually use — asks only to distinguish $(A, \mathbf{b})$ from a uniformly random pair. ML-KEM's security reduces to decision LWE remaining hard: an attacker who can distinguish real key-exchange transcripts from random noise can, by the same reduction, be turned into a lattice-problem solver.

Module-LWE: Why Kyber's Keys Fit in a Packet

Plain LWE with cryptographically sound parameters needs a matrix $A$ with tens of thousands of scalar entries, which is impractical to transmit per handshake. ML-KEM instead uses Module-LWE: entries of $A$, $s$, and $e$ are small polynomials in a ring $R_q = \mathbb{Z}_q[x] / (x^k + 1)$ rather than individual integers, letting one polynomial coefficient set stand in for what would otherwise be a large integer vector. This preserves the same worst-case-lattice-problem hardness reduction while shrinking public keys and ciphertexts to roughly 1–1.5 KB for ML-KEM-768 — small enough to fit in a single TLS handshake flight alongside a classical ECDHE share, which is how TLS 1.3's hybrid key exchange carries both simultaneously.

Why a Quantum Computer Doesn't Help Here

Shor's algorithm breaks factoring and discrete log because both problems reduce to finding the period of a function defined over a group — a hidden linear, periodic structure that the quantum Fourier transform detects directly. LWE has no equivalent structure to detect: the noise term $e$ is precisely what destroys the linear relationship between samples that a period-finding approach would need. There is no known way to phrase SVP, CVP, or LWE as a hidden-subgroup problem the way factoring and discrete log both are.

The best known quantum algorithms against lattice problems are quantum-accelerated variants of classical lattice sieving, and they only deliver a Grover-style quadratic speedup in the exponent — sieving's best classical running time is roughly $2^{0.292n}$ in the lattice dimension $n$; the best known quantum sieve brings that down to roughly $2^{0.265n}$. Both remain exponential in $n$. This is qualitatively different from Shor's algorithm turning an exponential classical problem into a polynomial quantum one — it is a constant-factor discount on an exponent that is still growing without bound. NIST's parameter sets (ML-KEM-512/768/1024, corresponding roughly to AES-128/192/256-equivalent security) are chosen with this quantum sieving speedup already priced in, not assuming a purely classical adversary.

This is the structural reason PQC migration replaces the key exchange and signature layer specifically — the layer resting on factoring and discrete log — while leaving AES essentially untouched: symmetric ciphers were never built on a hidden-subgroup-structured problem in the first place, and only need a key-length increase against Grover's algorithm, not a mathematical replacement.