Post-Quantum Cryptography

The cryptographic algorithms that secure the internet — RSA, elliptic curve Diffie-Hellman, ECDSA — share a common dependency: the difficulty of problems that quantum computers solve efficiently. Specifically, Shor’s algorithm reduces integer factorisation and discrete logarithm to polynomial time on a sufficiently capable quantum machine. The security of everything built on those assumptions reduces with it.

This is not a new observation. Peter Shor published his algorithm in 1994. The cryptographic community has spent the intervening decades designing, analysing, and standardising replacements. NIST ran a formal competition from 2016 to 2024 and has now published three standards, with a fourth in progress.

This book covers the territory systematically: the threat model, the mathematics, the competing algorithm families, the standards that emerged, and the migration work required. It assumes familiarity with classical cryptography — if RSA and Diffie-Hellman are not already in your mental model, the appendices of any cryptography textbook will fill that gap quickly.

What is not covered

This book does not cover quantum key distribution (QKD). QKD is a physically interesting idea that requires fibre runs between endpoints, has no mechanism for authentication without a pre-shared key, and solves a narrower problem than post-quantum cryptography at significantly higher cost. It is also not in any NIST standard. It is therefore outside the scope of this book.

This book also does not attempt to predict when cryptographically relevant quantum computers will exist. The range of credible estimates is wide enough to be unhelpful, and the conclusion — begin migration now — is the same regardless of where in that range the answer falls.

A note on notation

Mathematical objects are typeset in standard LaTeX throughout. Vectors are bold lowercase (a), matrices are bold uppercase (A). Security parameters are written as λ. Modular arithmetic is written as operations over ℤ_q. Algorithm names use their official designations: ML-KEM rather than Kyber, ML-DSA rather than Dilithium, except when discussing the pre-standardisation designs where the original names are more recognisable.

Chapter 1: The Quantum Threat

What actually breaks

Not everything breaks. Before cataloguing what quantum computers destroy, it is worth establishing what they do not.

Symmetric cryptography — AES, ChaCha20, SHA-256 — survives. Grover’s algorithm provides a quadratic speedup for unstructured search, which halves the effective security level: AES-128 drops to roughly 64-bit security against a quantum adversary, AES-256 to 128-bit. The standard response is to double key lengths. AES-256 is already the conservative choice, and SHA-256 output truncation to 256 bits provides adequate preimage resistance. The symmetric world needs tuning, not replacement.

What breaks entirely is the asymmetric layer:

• RSA — security relies on the hardness of integer factorisation. Shor’s algorithm factors an n-bit number in O(n³) quantum gate operations (or O(n² log n log log n) with optimised circuits). A 2048-bit modulus offers no meaningful security.
• Diffie-Hellman and DSA — security relies on the discrete logarithm problem in ℤ_p. Also O(n³) for Shor’s algorithm on the multiplicative group.
• ECDH and ECDSA — security relies on the elliptic curve discrete logarithm problem. The same algorithm applies with minor modifications. A 256-bit elliptic curve key provides roughly the same quantum security as a 256-bit RSA key: none.

If you have deployed a system that uses RSA key exchange, ECDH key agreement, or any signature scheme based on integer factorisation or discrete logarithm, the relevant threat is not the ciphertext being broken now — it is the ciphertext being recorded now and decrypted later. This is the harvest-now-decrypt-later attack.

Harvest now, decrypt later

The attack is straightforward. An adversary with network access records encrypted traffic today. The adversary does not need to break the encryption immediately. When a cryptographically relevant quantum computer becomes available — in ten years, in twenty years, at some point — the adversary applies Shor’s algorithm to recover the session key and decrypts the stored ciphertext.

This makes the migration timeline urgent for any data with a long confidentiality requirement. Medical records, legal communications, classified information, intellectual property — anything that needs to remain confidential for more than a decade is already at risk if it travels over channels protected only by classical asymmetric cryptography.

For authentication — signatures, certificates, TLS mutual auth — the threat model is different. A signature is only useful at the moment of verification. Harvesting a signed message and breaking the key after the fact does not help an adversary forge new signatures; it only lets them verify (or potentially fabricate, if they can recover the private key) old ones. The forward secrecy requirement is less acute for authentication than for key exchange, but key forgery is still a serious threat.

Shor’s algorithm in brief

Shor’s algorithm reduces integer factorisation to the problem of finding the period of a function. Given N = p × q, the algorithm:

1. Chooses a random a < N
2. Computes the period r of f(x) = a^x mod N using quantum phase estimation
3. If r is even and a^(r/2) ≢ -1 (mod N), computes gcd(a^(r/2) ± 1, N) to obtain factors

The quantum speedup comes entirely from step 2. Phase estimation uses the quantum Fourier transform to find the period of a function exponentially faster than any known classical algorithm. The rest of the algorithm is classical number theory.

The gate complexity for factoring an n-bit number scales as O(n²) to O(n³) depending on implementation optimisations. Physical qubit counts required to break RSA-2048 have been estimated at several million physical qubits when accounting for error correction overhead, given current error rates. Current devices have thousands of physical qubits with error rates that remain orders of magnitude too high. The gap is large. It is not obviously permanent.

What quantum computers do not break

For completeness:

Symmetric ciphers and hash functions are not known to be broken by any quantum algorithm. Grover’s algorithm provides a square-root speedup for searching over a space of 2^n elements, reducing 128-bit symmetric security to roughly 64-bit quantum security. This is a degradation, not a collapse.

The new post-quantum schemes themselves are designed with quantum adversaries in mind. Their security is not based on integer factorisation or discrete logarithm. Their underlying hard problems — finding short vectors in lattices, decoding random linear codes, inverting hash functions — do not have known polynomial-time quantum algorithms.

One-time pads are information-theoretically secure regardless of the adversary’s computational model. They are also impractical for most applications for the same reasons they have always been impractical.

The cryptographic response

The response to Shor’s algorithm is to stop basing asymmetric cryptography on problems that Shor’s algorithm solves. The cryptographic community has identified several families of mathematical problems that appear hard for both classical and quantum computers:

• Lattice problems — finding short or close vectors in high-dimensional lattices
• Error-correcting code problems — decoding random linear codes
• Hash functions — inverting collision-resistant hash functions
• Multivariate polynomial systems — solving overdetermined systems of multivariate polynomials over finite fields

Each of these forms the basis of one or more candidate post-quantum algorithms. The remaining chapters examine each family in detail.

Timeline and urgency

No one can give you a precise date when cryptographically relevant quantum computers will exist. The theoretical requirements are understood; the engineering challenges are substantial and not fully characterised. The honest range of credible expert opinion spans from “within a decade” to “two or three decades, if ever at scale.”

The migration argument does not depend on resolving that uncertainty. Cryptographic migrations are slow. Replacing the asymmetric layer across a large organisation’s infrastructure takes years. Standardisation bodies, hardware security modules, TLS libraries, certificate authorities, and application code all need updating on different timescales. NIST’s standardisation process took eight years. The HTTPS deployment of TLS 1.3 took longer than it should have. Waiting for the threat to materialise before beginning migration is not a strategy — it is an abdication.

NIST published final standards in 2024. The work of migration has begun.

Chapter 2: Mathematical Foundations

Post-quantum cryptographic constructions rest on a small set of mathematical problems whose hardness survives quantum computation. Understanding those problems at a working level — not a research level, but enough to evaluate security arguments and read the literature without confusion — requires covering lattices, error-correcting codes, and the specific computational problems derived from each.

This chapter covers the foundations. Later chapters apply them.

Lattices

A lattice is the set of all integer linear combinations of a set of basis vectors. Given linearly independent vectors b₁, b₂, …, b_n ∈ ℝ^m, the lattice they generate is:

$$\mathcal{L}(\mathbf{B}) = \left{ \sum_{i=1}^{n} x_i \mathbf{b}_i ;\middle|; x_i \in \mathbb{Z} \right}$$

The matrix B = [b₁ | b₂ | … | b_n] is called a basis. A lattice has infinitely many valid bases — any basis obtained by applying an integer unimodular transformation (determinant ±1) generates the same lattice.

This non-uniqueness of bases is the structural feature that cryptographic constructions exploit. A “good” basis (short, nearly orthogonal vectors) makes hard lattice problems easy to solve. A “bad” basis (long, highly correlated vectors) makes those same problems computationally intractable. A trapdoor in lattice cryptography is typically knowledge of a good basis for a lattice that is publicly specified by a bad one.

Hard lattice problems

Shortest Vector Problem (SVP): Given a lattice basis B, find the shortest non-zero vector in ℒ(B).

SVP is NP-hard under randomised reductions. The best known classical algorithms for exact SVP run in 2^O(n) time and space. The best known quantum algorithms offer a constant factor improvement but not an asymptotic one — the exponent remains exponential in the dimension n.

Closest Vector Problem (CVP): Given a lattice basis B and a target vector t, find the lattice vector closest to t.

CVP is at least as hard as SVP and is also NP-hard. Most cryptographic constructions reduce to approximate variants of SVP or CVP, where the approximation factor is a polynomial in n — these approximate versions are not known to be NP-hard but are conjectured to require 2^Ω(n) time.

Learning With Errors (LWE)

LWE is the workhorse problem of lattice-based cryptography. It was introduced by Oded Regev in 2005, along with a proof that solving it (on average, over random instances) is at least as hard as solving approximate SVP in the worst case. This worst-case to average-case reduction is an unusually strong security guarantee — it means breaking an LWE-based scheme on typical instances is as hard as solving the hardest possible lattice instances.

The LWE problem: Let n be the dimension, q be a modulus, and χ be an error distribution (typically a discrete Gaussian over ℤ). The decisional LWE problem asks to distinguish the following two distributions:

• LWE samples: Choose s ∈ ℤ_q^n uniformly at random (the secret). For each sample, choose a ∈ ℤ_q^n uniformly and e ∈ χ, and output (a, a·s + e mod q).
• Uniform samples: Choose (a, b) ∈ ℤ_q^n × ℤ_q uniformly at random.

The error term e is the essential ingredient. Without it, recovering s from (a, b = a·s mod q) is a linear algebra problem solvable in polynomial time. With a small error added, recovering s or even distinguishing LWE samples from uniform appears exponentially hard.

The search variant asks to recover s given polynomially many LWE samples. Under mild parameter conditions, search and decisional LWE are equivalent.

Ring-LWE (RLWE): LWE requires key material proportional to n² (an n×n matrix A is part of the public key). Ring-LWE improves efficiency by working in the polynomial ring R_q = ℤ_q[x] / (xⁿ + 1), where n is a power of 2. Multiplication in this ring is efficiently computable via the Number Theoretic Transform (NTT), which is the modular analogue of the Fast Fourier Transform. RLWE achieves essentially the same security guarantees with O(n log n) operations instead of O(n²), and key sizes that scale as O(n) instead of O(n²).

Module-LWE (MLWE): A middle ground between LWE and RLWE. The secret and error are vectors of ring elements — small matrices over R_q rather than the full n×n matrix of plain LWE. CRYSTALS-Kyber and CRYSTALS-Dilithium use MLWE and its signature analogue, Module Learning With Errors over rings. The module structure provides parameter flexibility: the module rank k trades off between security and performance.

Error-Correcting Codes

An [n, k, d] linear code over a finite field 𝔽_q is a k-dimensional subspace of 𝔽_q^n, where d is the minimum Hamming distance between any two distinct codewords. The rate is k/n (the fraction of bits that carry information), and the code can correct up to ⌊(d−1)/2⌋ errors.

Codes are defined by a generator matrix G ∈ 𝔽_q^(k×n) (encoding: m → mG) and a parity check matrix H ∈ 𝔽_q^((n−k)×n) (syndrome: Hcᵀ = 0 for valid codewords). The syndrome Hsᵀ of a received word s = c + e (codeword plus error) equals Heᵀ, which is used to locate and correct errors.

The hard problem: syndrome decoding

Syndrome Decoding Problem (SDP): Given a parity check matrix H and a syndrome s, find a low-weight error vector e such that Heᵀ = s.

For a random linear code, SDP is NP-complete. This has been known since 1978 (Berlekamp, McEliece, van Tilborg). The best classical algorithms for SDP use information set decoding (ISD), and their complexity is exponential in the code’s error-correction capacity. Quantum algorithms improve the exponent by a constant factor via Grover-style search over ISD, but the speedup is sub-exponential — parameters can be increased to compensate.

The key point: unlike lattice problems, the hardness of syndrome decoding for random linear codes does not require a worst-case to average-case reduction argument. Random linear codes are provably hard on average, almost directly from the NP-hardness result.

Specific code families

Goppa codes (McEliece scheme): Binary Goppa codes have efficient decoding algorithms despite being drawn from a family that “looks” random. The public key is a randomly scrambled and permuted generator matrix; the trapdoor is the Goppa structure that enables efficient decoding. The original McEliece scheme from 1978 remains unbroken against both classical and quantum adversaries, though its large key sizes make it unwieldy.

Quasi-cyclic codes (BIKE, HQC): Applying cyclic or quasi-cyclic structure reduces key sizes substantially, at the cost of relying on the hardness of structured variants of syndrome decoding. These structured variants lack the same long history of cryptanalysis as random linear codes.

Hash Functions as Cryptographic Primitives

Hash functions require less mathematical setup — the hard problem is empirical rather than reducible to a clean worst-case problem. A collision-resistant hash function H: {0,1}* → {0,1}^n is one for which:

• Preimage resistance: Given y, finding x such that H(x) = y costs O(2^n) time.
• Second preimage resistance: Given x, finding x’ ≠ x such that H(x) = H(x’) costs O(2^n) time.
• Collision resistance: Finding any pair (x, x’) with H(x) = H(x’) costs O(2^(n/2)) time (by the birthday bound).

Against quantum adversaries, Grover’s algorithm finds preimages in O(2^(n/2)) time. The birthday bound for collisions is unaffected by Grover — collision finding is not directly a search problem over an unstructured space. Hash-based signature schemes built on SHA-256 or SHAKE-256 with 256-bit output provide around 128-bit quantum security for preimage resistance.

The Short Integer Solution Problem (SIS)

Alongside LWE, the Short Integer Solution problem appears frequently in signature schemes:

SIS_(n,m,q,β): Given a uniformly random matrix A ∈ ℤ_q^(n×m), find a non-zero integer vector z ∈ ℤ^m with ‖z‖ ≤ β such that Az = 0 mod q.

SIS is the “signature-side” analogue of LWE. Solving SIS is equivalent to finding short vectors in certain lattices (specifically, in the kernel lattice of A). Regev and Micciancio showed reductions between SIS and approximate SVP, giving SIS a similar worst-case hardness guarantee to LWE.

CRYSTALS-Dilithium and FALCON both base their signature security on variants of SIS (combined with LWE for the full scheme).

Summary of hard problems and their users

The chapters that follow examine each family with the above foundations in place.

Chapter 3: Lattice-Based Cryptography

Lattice-based cryptography produces the largest family of post-quantum algorithms and accounts for three of the four NIST standards. The mathematical foundations were covered in Chapter 2. This chapter covers the constructions built on those foundations, focusing on the three algorithms that achieved standardisation: CRYSTALS-Kyber (now ML-KEM), CRYSTALS-Dilithium (now ML-DSA), and FALCON (now FN-DSA).

From LWE to encryption: the basic construction

The simplest LWE-based encryption scheme illustrates how the problem translates into cryptography. Let n be the security parameter, q a modulus, and χ an error distribution.

Key generation: Sample s ←$ ℤ_q^n (private key), A ←$ ℤ_q^(m×n), e ←$ χ^m, compute b = As + e mod q. Public key is (A, b).

Encryption of bit μ ∈ {0,1}: Sample r ←$ {0,1}^m (sparse), compute u = Aᵀr mod q, v = bᵀr + μ·⌊q/2⌋ mod q. Ciphertext is (u, v).

Decryption: Compute v − sᵀu = bᵀr − sᵀ(Aᵀr) + μ·⌊q/2⌋ = (As + e)ᵀr − sᵀAᵀr + μ·⌊q/2⌋ = eᵀr + μ·⌊q/2⌋. If eᵀr is small (which it is, since both e and r are small), round to recover μ.

This basic construction is IND-CPA secure under the decisional LWE assumption. Key sizes and ciphertext sizes scale as O(n²) due to the matrix A. Ring-LWE and Module-LWE reduce this to O(n) and O(kn) respectively, where k is the module rank.

CRYSTALS-Kyber / ML-KEM

Kyber is a key encapsulation mechanism (KEM) based on Module Learning With Errors (MLWE). It was selected by NIST and standardised as ML-KEM (FIPS 203) in 2024.

Structure

Working over the polynomial ring R_q = ℤ_q[x] / (x^256 + 1) with q = 3329, Kyber uses a module of rank k. Three parameter sets are defined:

For comparison, an X25519 public key is 32 bytes and a Diffie-Hellman shared secret exchange produces a 32-byte result. The size increase is the cost of lattice-based security.

Key generation

1. Sample matrix A ←$ R_q^(k×k) from a hash of a random seed ρ (the matrix is derived pseudorandomly, not transmitted in full)
2. Sample secret s ←$ χ^k and error e ←$ χ^k (small coefficients drawn from a binomial distribution)
3. Compute t = As + e
4. Public key: (ρ, t); Private key: s

Encapsulation

1. Sample message m ∈ {0,1}^256
2. Derive randomness from m and the public key hash (making it deterministic given m)
3. Sample r, e₁, e₂ from χ
4. Compute u = Aᵀr + e₁, v = tᵀr + e₂ + ⌈q/2⌉·m
5. Ciphertext: (u, v); Shared secret: KDF(m, H(ciphertext))

Decapsulation

1. Compute m’ = Decompress(v − sᵀu)
2. Re-encapsulate with m’ to produce ciphertext (u‘, v’)
3. If (u‘, v’) = (u, v), output the shared secret; otherwise output a pseudorandom value derived from a rejection token

The implicit rejection in step 3 is critical for CCA2 security (the Fujisaki-Okamoto transform applied to the base scheme). An active adversary who submits a malformed ciphertext receives a pseudorandom output indistinguishable from a legitimate shared secret, learning nothing.

Number Theoretic Transform

The dominant cost in Kyber is polynomial multiplication in R_q. The NTT is the efficient algorithm: since q = 3329 and n = 256, q ≡ 1 (mod 512), so 512th roots of unity exist in ℤ_q, enabling a length-256 NTT. Polynomial multiplication reduces to point-wise multiplication in the transform domain in O(n log n) operations, versus O(n²) for schoolbook multiplication.

This is the reason behind the specific value q = 3329: it is the smallest prime satisfying q ≡ 1 (mod 512) that provides adequate security margin.

CRYSTALS-Dilithium / ML-DSA

Dilithium is a digital signature scheme standardised as ML-DSA (FIPS 204). It uses the same MLWE foundation as Kyber, plus the Module-SIS problem for the signing security argument.

Fiat-Shamir with aborts

Dilithium uses a Fiat-Shamir identification scheme converted to a signature by the Fiat-Shamir transform. The “with aborts” technique is essential for lattice-based Fiat-Shamir — unlike classical schemes, the signer must sometimes restart the signing process to avoid leaking information about the private key through the distribution of signature components.

The signing algorithm:

1. Sample masking vector y ←$ S_γ₁^ℓ (uniform over small coefficients)
2. Compute w = Ay mod q, let w₁ = HighBits(w, 2γ₂)
3. Compute challenge c ← H(μ, w₁) where μ is the message hash
4. Compute z = y + cs₁
5. If ‖z‖_∞ ≥ γ₁ − β or LowBits(Ay − cs₂, 2γ₂) is large: abort and restart
6. Output signature (z, c, hint)

The abort condition ensures that z reveals no information about s₁ — the masking y completely hides s₁·c only when z falls within the safe range. The abort probability is tuned to be low (around 1/7 for ML-DSA-65) while ensuring the distribution of accepted signatures leaks nothing.

Parameter sets

For context, an Ed25519 signature is 64 bytes and a public key is 32 bytes. Lattice-based signatures are larger; the tradeoff is post-quantum security.

FALCON / FN-DSA

FALCON is a lattice-based signature scheme standardised as FN-DSA (FIPS 206). It uses NTRU lattices — a different lattice structure from Dilithium — and produces significantly smaller signatures at the cost of substantially more complex implementation.

NTRU lattices

An NTRU lattice is defined by polynomials f, g ∈ R = ℤ[x]/(xⁿ + 1) where f is invertible mod q. The lattice has a particularly useful structure: the Gram matrix has block form with efficient representation. FALCON uses this structure to sample short lattice vectors during signing via the Fast Fourier sampling algorithm — a randomised algorithm that produces vectors whose distribution is an approximation of a discrete Gaussian over the lattice.

The Fast Fourier Sampling trapdoor

The private key in FALCON is a “good” basis for the NTRU lattice — specifically the pair (f, g) and their NTRU-conjugates F, G satisfying fG − gF = q (the NTRU equation). Key generation finds such a pair using a recursive structure over towers of rings.

Signing reduces to finding a short lattice vector close to a target determined by the message hash. The Fast Fourier Sampler uses the private basis to sample from a discrete Gaussian distribution centred near that target. An adversary with only the public key — a single polynomial h = gf⁻¹ mod q, the “bad” basis — cannot perform this sampling efficiently.

Parameter sets

FALCON signatures are variable-length because the discrete Gaussian output is compressed before transmission. The average sizes quoted are typical. The signature is substantially smaller than ML-DSA for equivalent security levels — the penalty is implementation complexity.

Implementation hazard: the Gaussian sampler

FALCON’s correctness and security depend critically on the quality of the discrete Gaussian sampler. A biased sampler can leak private key information through signature distributions. The reference implementation uses a carefully designed sampler with rejection sampling and polynomial arithmetic over ℂ encoded as 64-bit floats, which introduces floating-point correctness requirements that are non-trivial on constrained hardware.

The NIST standard (FIPS 206) is explicit about this: implementers must use the reference sampler or an implementation proven to be equivalent. Rolling your own Gaussian sampler is a category of mistake with a poor historical record.

Comparative summary

ML-KEM and ML-DSA are the pragmatic defaults. FN-DSA is for applications where signature size is a binding constraint and the implementer has sufficient expertise to handle the Gaussian sampler correctly.

Chapter 4: Code-Based Cryptography

Code-based cryptography is the oldest post-quantum candidate family. Robert McEliece proposed the first code-based public-key encryption scheme in 1978, and it has remained unbroken — classically and quantumly — for nearly fifty years. That longevity is the primary argument in its favour. The primary argument against it is that the public keys are enormous.

The McEliece cryptosystem

The original McEliece scheme instantiates with binary Goppa codes, which have the property of efficient decoding (there is a known polynomial-time algorithm for correcting up to t errors) despite being indistinguishable from random linear codes to an observer who does not know the code structure.

Hard problem

The McEliece scheme’s security reduces to the hardness of:

1. Code indistinguishability: The public key matrix is a random-looking generator matrix. Distinguishing it from a truly random linear code requires recovering the Goppa structure, which is equivalent to solving the code equivalence problem — believed hard for large parameters.

2. Syndrome decoding: Given the disguised generator matrix and a ciphertext with intentional errors added, recovering the message requires correcting those errors without knowing the Goppa structure. This is an instance of the syndrome decoding problem, which is NP-complete for random linear codes.

Key generation

1. Select a t-error-correcting binary [n, k, d≥2t+1] Goppa code with generator matrix G
2. Choose a random k×k invertible matrix S (scrambling)
3. Choose a random n×n permutation matrix P
4. Public key: G’ = SGP (size k×n); Private key: (S, G, P)

The public key is a scrambled, permuted version of the original generator matrix. The Goppa structure is hidden.

Encryption and decryption

Encryption of message m ∈ 𝔽_2^k:

1. Compute c = mG’ + e where e ∈ 𝔽_2^n is a random vector of weight exactly t

Decryption:

1. Compute cP⁻¹ = mSG + eP⁻¹
2. Apply the Goppa decoder to cP⁻¹ — it corrects t errors regardless of the scrambling S
3. Recover mS, then apply S⁻¹ to get m

The decoder works on mSG + eP⁻¹ because eP⁻¹ still has weight t (permutations preserve weight), and the Goppa decoder corrects any error pattern of weight ≤ t.

Niederreiter variant

Harald Niederreiter proposed a dual formulation using parity check matrices instead of generator matrices. In the Niederreiter scheme, the public key is a parity check matrix H’ = SHP, and encryption is syndrome-based. The Niederreiter scheme is equivalent in security to McEliece, produces smaller ciphertexts, and is used as the basis for Classic McEliece.

Classic McEliece

Classic McEliece is the NIST submission that survived to the fourth round without standardisation — NIST ultimately chose not to standardise it in the first wave due to its large public keys, but acknowledged it as the most conservative and best-understood code-based candidate. NIST’s security considerations document describes it as a strong candidate for future standardisation.

Parameters

Classic McEliece uses binary Goppa codes with parameters chosen to resist the best known attacks (primarily information set decoding attacks, with both classical and quantum variants):

Public keys ranging from 261 KB to 1.3 MB are not suitable for most TLS-style key exchange scenarios. For offline key establishment, pre-provisioned public keys, or systems where bandwidth constraints are secondary to long-term security confidence, Classic McEliece is a defensible choice.

The ciphertexts, by contrast, are tiny — 128 to 240 bytes, smaller than any competing PQC scheme.

Why the long track record matters

The original McEliece construction was published in 1978. The specific algebraic structure of binary Goppa codes has been the subject of cryptanalytic attention for nearly five decades. Major attack improvements:

• 1988: Lee-Brickell algorithm — improved information set decoding, practical speedup
• 1988: Stern’s algorithm — probabilistic ISD, asymptotic improvement
• 2008–2011: BJMM and May-Meurer-Thomae algorithms — improved birthday-based ISD
• 2015–2018: Various ball-collision decoding improvements

Each of these attacks improved the exponent of the exponential — reducing the effective security level by a constant number of bits — but none found a polynomial-time algorithm. The parameters in Classic McEliece are chosen to provide adequate margin against the best known ISD attacks, including quantum-accelerated variants.

The confidence in McEliece comes from this history: the construction has been publicly analysed by a large portion of the cryptographic community for nearly fifty years, and the best known attack remains exponential.

Quasi-cyclic code-based schemes: BIKE and HQC

Both BIKE and HQC were NIST alternate candidates (fourth round). They use quasi-cyclic codes to achieve dramatically smaller keys at the cost of a shorter cryptanalytic history and reliance on structured variants of syndrome decoding.

BIKE (Bit Flipping Key Encapsulation)

BIKE uses quasi-cyclic moderate density parity check (QC-MDPC) codes. The key insight: a random-looking parity check matrix with quasi-cyclic structure enables efficient decoding while appearing indistinguishable from random to an adversary.

Structure: The parity check matrix has the form H = [H₀ | H₁] where H₀ and H₁ are r×r circulant matrices (each row is a cyclic rotation of the previous). A circulant matrix is fully specified by its first row — storing one row of length r suffices to represent an r×r matrix. This reduces key storage from O(r²) to O(r).

Decoder: BIKE uses a bit-flipping decoder (Black-Gray-Flip, a variant of Gallager’s original algorithm) rather than an algebraic decoder. The decoder is probabilistic — it fails to decode with small probability δ, which creates a subtle security issue: decryption failure events can leak information about the private key. BIKE’s design carefully bounds δ and the information leakage.

Parameters (approximate):

HQC (Hamming Quasi-Cyclic)

HQC is also quasi-cyclic but uses a different algebraic structure and a Reed-Muller decoder for the inner code. The security reduction is cleaner than BIKE’s: HQC’s security reduces to the hardness of the syndrome decoding problem for quasi-cyclic codes, without the decryption failure complication.

Parameters (approximate):

The structured code risk

The critical difference between Classic McEliece and the quasi-cyclic schemes is the nature of the hard problem. Classic McEliece rests on syndrome decoding for random linear codes — a problem proven NP-complete in 1978 with fifty years of cryptanalysis. BIKE and HQC rest on syndrome decoding for quasi-cyclic codes, a structured variant whose hardness is not known to reduce to the random case.

Structured problems in cryptography have a mixed historical record. The quasi-cyclic structure creates algebraic relationships that might admit attacks unavailable for unstructured codes. This is not a hypothetical concern — several earlier structured code-based schemes were broken when the structure was successfully exploited.

BIKE and HQC have survived the NIST process without structural breaks, but their cryptanalytic history is measured in years rather than decades.

Practical recommendation

For most applications, ML-KEM (lattice-based) is the right choice. Code-based cryptography is worth considering for:

1. Diversity: An organisation that wants to hedge against a breakthrough in lattice cryptanalysis can deploy Classic McEliece as an alternative or in addition to ML-KEM.
2. Long-horizon threat models: Classic McEliece’s fifty-year security history is reassuring for applications with multi-decade confidentiality requirements.
3. Embedded/constrained environments where small ciphertexts matter: Classic McEliece’s ciphertext size is tiny; only the key generation and storage is painful.

For general-purpose network security, the 261 KB–1.3 MB public key is a decisive disadvantage that the lattice-based schemes do not have.

Chapter 5: Hash-Based Signatures

Hash-based signatures derive their security from a single assumption: the collision resistance and preimage resistance of a cryptographic hash function. No algebraic structure, no lattice problems, no integer factorisation. If SHA-256 or SHAKE-256 is secure, hash-based signatures are secure. This makes their security argument unusually clean.

The tradeoff is that they are signature-only — hash functions alone do not readily yield key encapsulation mechanisms. The other tradeoff, historically, was statefulness: many early hash-based schemes required the signer to track which one-time keys had been used. SLH-DSA (SPHINCS+) eliminates that requirement.

One-time signatures: Lamport and Winternitz

The foundation of all hash-based signature schemes is the one-time signature (OTS). As the name suggests, an OTS key pair can sign exactly one message. Signing a second message with the same key reveals enough information to forge signatures.

Lamport signatures

Leslie Lamport’s scheme from 1979 is the simplest possible hash-based signature:

Key generation: For an n-bit message hash, generate 2n random values: x[0][0], x[0][1], …, x[n-1][0], x[n-1][1]. Compute the public key y[i][b] = H(x[i][b]) for all i, b.

Signing message m (after hashing to n bits): For each bit position i, reveal x[i][m_i] — that is, reveal the preimage corresponding to the bit value in the message.

Verification: Check H(σ[i]) = y[i][m_i] for all i.

Security: revealing x[i][0] to sign a 0-bit at position i means the adversary cannot forge a 1-bit at position i without inverting H. Correct, but using 2n random values for an n-bit message means a 256-bit hash requires 512 secret values. Signatures are large.

Winternitz OTS (W-OTS)

W-OTS reduces signature size by applying the hash function multiple times in a chain. Instead of signing individual bits, W-OTS signs w-bit blocks using hash chains of length 2^w − 1.

For a block value b ∈ [0, 2^w), the chain is: x → H(x) → H(H(x)) → … (applied 2^w − 1 − b times from the secret key to produce the public key component, and applied b times during signing to produce the signature component).

Larger w means shorter signatures (fewer chains needed) but higher computational cost (longer chains). XMSS uses W-OTS+, a hardened variant; SLH-DSA uses WOTS+ with small modifications.

Merkle trees: from one-time to many-time

A one-time signature is useless for real applications. The standard solution is a Merkle tree.

Construction: Generate a set of L OTS key pairs (sk₁, pk₁), …, (sk_L, pk_L). Build a binary hash tree over the public keys: leaf nodes are H(pk_i), internal nodes are H(left child || right child). The root is the public key of the many-time scheme.

Signing with leaf i: Include the OTS signature under sk_i, the OTS public key pk_i, and the authentication path — the sibling hashes on the path from leaf i to the root. The verifier hashes pk_i up to the root using the authentication path and checks it matches the public root.

Statefulness: The signer must track which leaves have been used. Using leaf i twice exposes the OTS private key sk_i, enabling forgery. Tracking a counter across process restarts, migrations, and distributed deployments is operationally non-trivial.

XMSS (eXtended Merkle Signature Scheme) and LMS (Leighton-Micali Signatures) are stateful hash-based schemes standardised by NIST and the IETF. They are appropriate for controlled environments where state management is feasible — firmware signing, certificate authorities, HSM-backed key usage.

SPHINCS+ and SLH-DSA

SPHINCS+ eliminates the statefulness requirement by using a hypertree — a tree of trees — combined with a FORS (Forest Of Random Subsets) few-time signature scheme. NIST standardised SPHINCS+ as SLH-DSA (FIPS 205).

Architecture

SLH-DSA uses three components:

1. WOTS+: A Winternitz one-time signature scheme with domain separation and bitmask operations that strengthen the security proof.

2. FORS: A few-time signature scheme based on random subsets. FORS can safely sign a small number of messages with the same key (the exact count depends on parameters), which breaks the pure OTS statefulness requirement.

3. Hypertree: A d-layer binary tree where each internal node is signed by a WOTS+ key in the layer above. The leaves are FORS key pairs. The root is the public key.

Signing: To sign message m:

1. Derive a pseudorandom index from m and a secret random value R. This index determines which FORS key pair to use and which hypertree leaf to use — deterministically, without a counter.
2. Sign m using the selected FORS key pair
3. Sign the FORS public key using the WOTS+ key at the corresponding hypertree leaf
4. Produce WOTS+ signatures up each layer of the hypertree to the root

The critical property: the leaf index is derived pseudorandomly from (m, R) where R is part of the private key. The same (m, R) always produces the same index, but different messages produce different (pseudorandom) indices. The probability of two distinct messages hitting the same FORS leaf is negligible under the parameter settings — the hypertree is large enough that collision probability is below the target security level.

Parameter sets

SLH-DSA offers two hash function families (SHA-256 and SHAKE-256) at each security level, and two variants per level: -s (small, prioritising smaller signatures at the cost of slower signing) and -f (fast, prioritising faster signing at the cost of larger signatures).

The public and private keys are tiny. The signatures are large — substantially larger than ML-DSA and orders of magnitude larger than Ed25519. The -s variants produce smaller signatures but signing can take tens of milliseconds on modern hardware. The -f variants sign in under a millisecond but signatures exceed 17 KB.

Verification performance

Verification is fast for all parameter sets — comparable to Ed25519 in the 128-bit case. The verification algorithm processes a fixed number of hash evaluations regardless of variant. Signing is the expensive operation.

Security confidence

SLH-DSA’s security reduces entirely to the properties of the underlying hash function. No lattice assumptions, no code assumptions, no assumption about algebraic structure. If SHA-256 or SHAKE-256 is modelled as a random oracle and has 256-bit preimage resistance, SLH-DSA provides the stated security level.

This makes SLH-DSA the most conservative signature choice in the NIST portfolio. It is recommended as a secondary signature option in the NIST migration guidance — not the default (due to signature size) but a hedge against advances in lattice cryptanalysis.

When to use hash-based signatures

Use stateful hash-based signatures (XMSS, LMS) when:

• Signing is done in a controlled, audited environment (firmware signing, CA operations)
• State management is guaranteed by HSM or hardware
• Very long-term security confidence is required
• Signature size is acceptable

Use SLH-DSA when:

• Statefulness is not acceptable
• Maximum security confidence is required regardless of signature size
• Verification performance matters more than signing performance
• Serving as a hedge alongside ML-DSA

Do not use hash-based signatures when:

• Signature size is a hard constraint (TLS handshakes, packed protocols)
• Signing frequency is high and latency is critical (the -s variants are slow)

In practice, most systems will deploy ML-DSA as the primary signature scheme and optionally SLH-DSA as a backup, depending on how conservatively they want to hedge their lattice assumptions.

Chapter 6: Multivariate Cryptography

Multivariate cryptography builds public-key schemes around the difficulty of solving systems of multivariate polynomial equations over finite fields. The fundamental hard problem — solving an overdetermined system of quadratic equations over 𝔽_2 — is NP-complete. The engineering challenge is constructing public keys that hide a tractable special structure while appearing to be instances of the hard problem.

This chapter covers a family that has produced useful signature schemes and a cautionary tale about what happens when the hidden structure is more visible than expected.

The hard problem: MQ

Multivariate Quadratic (MQ) problem: Given m polynomial equations p₁, …, p_m ∈ 𝔽_q[x₁, …, x_n] of degree 2, find a solution (a₁, …, a_n) ∈ 𝔽_q^n such that p_i(a₁, …, a_n) = 0 for all i.

Over 𝔽_2, MQ is NP-complete (Garey and Johnson, 1979). Over larger fields the problem is similarly hard in the worst case. The best known algorithms for random instances run in exponential time — XL (eXtended Linearisation), Groebner basis methods (F4, F5), and hybrid approaches. Quantum speedups via Grover’s algorithm apply, roughly halving the security level, which is addressed by choosing larger parameters.

Building a trapdoor: the oil and vinegar structure

The central technique in most practical multivariate signature schemes is the oil and vinegar (OV) structure, introduced by Patarin in 1997.

Partition the n variables into “oil” variables O = {x₁, …, x_o} and “vinegar” variables V = {x_{o+1}, …, x_n}. Define central polynomials of the form:

$$\bar{p}k(x) = \sum{i \in O, j \in V} \alpha_{ijk} x_i x_j + \sum_{i,j \in V} \beta_{ijk} x_i x_j + \sum_{i \in O} \gamma_{ik} x_i + \sum_{i \in V} \delta_{ik} x_i + \epsilon_k$$

Crucially: there are no oil-oil terms (no x_i x_j where both i, j ∈ O).

Why this enables inversion (signing): Given a target value y ∈ 𝔽_q^m, fixing random vinegar values turns each central polynomial into a linear equation in the oil variables (since all remaining terms involving oil variables are now linear, given fixed vinegars). With o = m, the resulting linear system has a square coefficient matrix over 𝔽_q; the probability it is invertible is high, and if not, simply try different vinegar values.

The public key is the central map composed with invertible affine transformations S: 𝔽_q^m → 𝔽_q^m and T: 𝔽_q^n → 𝔽_q^n, hiding the oil-vinegar structure. The private key is S, T, and the central map.

Rainbow

Rainbow extends oil and vinegar by applying multiple layers. In an L-layer Rainbow scheme, the variable space is partitioned into L+1 sets V₁ ⊂ V₂ ⊂ … ⊂ V_{L+1}, where layer ℓ uses variables in V_{ℓ+1} as oils and variables in V_ℓ as vinegars.

Rainbow submitted to the NIST PQC competition and reached the third round as a signature finalist. It was broken.

The Rainbow attack (2022)

In February 2022, Ward Beullens published an attack that broke Rainbow III (128-bit security) on a standard laptop in 53 hours. The attack exploited the rectangular MinRank structure inherent in Rainbow’s layered construction — the linear relationships between the oil spaces of consecutive layers create a recoverable structure that allows recovery of an equivalent private key.

Beullens’ attack demonstrated that the effective security of Rainbow III was closer to 50–60 bits rather than 128 bits. Rainbow was eliminated from the NIST process shortly after.

This is a recurring pattern in multivariate cryptography: the structured trapdoor that enables efficient signing also creates structured linear algebra in the public key that cryptanalysts can exploit. Getting this balance right is difficult. Rainbow had been considered secure for over a decade before the attack.

GeMSS and other MQ-based schemes

GeMSS (Great Multivariate Short Signature) uses a different trapdoor: the HFEv− (Hidden Field Equations with vinegar and minus modifiers) structure. Instead of oil and vinegar, HFE represents the central map as a univariate polynomial over a large field extension — solving for preimages reduces to solving a univariate polynomial, which is efficient.

GeMSS survived the NIST process as an alternate candidate but was not standardised. Its parameter sizes (extremely large public keys: 352 KB to 1.2 MB) and relatively slow verification made it unattractive compared to lattice-based alternatives.

MAYO and UOV: the current state

After the Rainbow break, the multivariate community largely converged on two directions:

UOV (Unbalanced Oil and Vinegar): The original oil and vinegar scheme (no layering) has no known attack analogous to Beullens’ Rainbow break. The trade-off is that pure UOV requires more vinegar variables relative to oil variables to achieve adequate security, resulting in larger keys.

MAYO: A variant submitted to the NIST Additional Signatures project that uses “whipping” — evaluating the public map multiple times with different inputs and combining results — to reduce signature sizes while using the UOV structure. MAYO has 256-byte to 838-byte public keys (much smaller than classic UOV) and is an active NIST candidate.

Quantum resistance assessment

Multivariate schemes resist known quantum attacks reasonably well. The Grover speedup applies to the underlying MQ problem search, and parameters are chosen with this in mind. There are no known polynomial-time quantum algorithms for MQ analogous to Shor’s algorithm for factorisation.

The practical concern with multivariate cryptography is different: the history of structural breaks. Nearly every specific instantiation of a multivariate trapdoor has eventually had its structure exploited — sometimes subtly, sometimes catastrophically. The community has learned from each break and the current generation of schemes (MAYO, UOV) is more carefully designed. But the confidence level derived from a five- to eight-year cryptanalytic history is qualitatively different from the decades behind lattice problems or random code decoding.

Summary

No multivariate scheme is in the current primary NIST PQC standards. MAYO and UOV are candidates in the NIST Additional Signatures project (a separate process for signatures beyond the initial three standards). Whether multivariate cryptography achieves mainstream standardisation depends on whether the current generation of schemes survives continued cryptanalytic scrutiny — the same test that Rainbow failed.

The NIST PQC Standards

Hybrid Approaches and Migration

Implementation and Performance

Acknowledgements