Chapter 1: The quantum threat

Before you start. The book as a whole assumes modular arithmetic, basic linear algebra, basic discrete probability, classical-algorithms thinking, familiarity with deployed cryptography (TLS, Diffie-Hellman, AES, certificates), and Python 3. This chapter needs less than that. It reasons about cited results rather than deriving them, so the deployed-cryptography items carry most of the weight and the mathematics arrives in Chapter 2. The Prerequisites page is the full checklist, grouped by when each item is needed, and it names a free brush-up resource for each gap. The book does not teach quantum computing from scratch. Nothing before Part VI needs it, and the Prerequisites page names Quantum Country’s free primer for readers who want it sooner, with Nielsen and Chuang (Nielsen & Chuang, 2010) as the deeper reference.

An adversary sits on a backbone cable and captures a classical-only TLS 1.3 handshake, one that negotiated X25519 or P-256 rather than a hybrid post-quantum group. The cleartext part of the exchange is small but load-bearing: ClientHello carries the client’s ephemeral Diffie-Hellman public share, and ServerHello carries the server’s. Both shares are visible to anyone on the wire (Rescorla, 2026). The Certificate and CertificateVerify messages that follow are sent under handshake encryption, and the certificate is not what protects the session secrets in the first place: the session keys are derived from the ephemeral key exchange. The adversary writes everything (cleartext key shares, encrypted handshake messages, encrypted application data) to cheap disk and waits.

Today the adversary cannot decrypt the recorded session. Recovering the scalar behind an X25519 ephemeral share is classically infeasible, the RSA-2048 or ECDSA/P-256 certificate key is classically hard to break, and the AES-GCM session itself rests on Shor-immune symmetric primitives. The classical assumptions still hold.

Tomorrow the adversary runs Shor’s algorithm against the captured X25519 ephemeral share. The vulnerable object is the ephemeral key exchange, not the certificate. In TLS 1.3 the CertificateVerify signature, verified against the certificate’s public key, authenticates the preceding handshake transcript; the session’s confidentiality comes from the ephemeral key exchange instead (Rescorla, 2026). Breaking the certificate key after the fact does not, by itself, decrypt past traffic. Once Shor recovers either side’s ephemeral scalar, the shared secret can be reconstructed, the handshake and application traffic secrets can be derived, and the recorded application data decrypts. Classical forward secrecy does not imply post-quantum forward secrecy when the ephemeral group is Shor-reducible.

The certificate key is a separate problem. If the server authenticates with RSA, ECDSA, EdDSA, or Schnorr over a Shor-reducible group, a future quantum attacker can recover the signing key from the public verification key and impersonate that identity in future sessions. That is a different threat: it does not retroactively decrypt the recorded session, but it lets the attacker masquerade as the server going forward unless authentication has also migrated.

The gap between “today” and “tomorrow” is the threat. It has a name: harvest now, decrypt later.

Almost all public-key cryptography deployed today rests on two hard problems: factoring a large integer, and finding a discrete logarithm. Shor’s algorithm, run on a large fault-tolerant quantum computer, solves both in polynomial time. That breaks RSA, finite-field Diffie-Hellman, elliptic-curve Diffie-Hellman, ECDSA, EdDSA, and Schnorr over any Shor-reducible group: most of the public-key authentication deployed today. The book cites Shor’s result rather than deriving it.

The rest of the book is about the constructions that replace them and how to deploy them. This chapter gives the threat its numbers and its sources; every later chapter assumes the threat model set out here.

The book uses one threat model throughout Part I and refines it later. The threat model has three parts.

Adversary capability. A cryptographically relevant quantum computer (CRQC) exists: large, fault-tolerant, and programmable, with enough logical qubits and enough runtime to execute Shor’s algorithm on a 256-bit elliptic-curve discrete log or a 2048-bit RSA modulus. The same adversary has state-level classical resources for collection, indexing, and long-term retention; it does not have enough classical compute to brute-force modern symmetric primitives or to attack RSA or the elliptic-curve discrete-log problem (ECDLP) without Shor.
Attack goals. Key recovery against asymmetric primitives via Shor, and brute-force speedup against symmetric primitives via Grover. Forgery of artifacts that still verify under long-lived classical public keys, decryption of past ciphertexts, and impersonation in future sessions are all in scope. Real-time on-spend attacks against pending public-ledger transactions are in scope when a pending transaction exposes a Shor-vulnerable public verification key (or lets one be recovered) before finality. The attacker has time to recover the private key and front-run or replace the legitimate transaction. In the minutes-scale scenario analyzed by Babbush et al., this requires fast-clock superconducting hardware (Babbush et al., 2026).
Knowledge model. The adversary knows the public algorithm. The adversary has been recording ciphertexts and handshakes for years and keeps doing so. The adversary can wait between capture and attack.

Two points about this model.

First, it does not assume the quantum computer is sitting in an academic lab. The worst case is a state-level adversary or a well-funded commercial operator with the budget to keep a fault-tolerant machine running. The resource estimates below tell you what “well-funded” has to cover.

Second, the model is deliberately independent of the transition timeline. “When” is a question the cryptographic community cannot answer with a date. “What breaks, and by how much” is a question the cryptographic community has answered with numbers. The rest of this chapter is about the numbers.

Chapter 2 introduces the algebra, Chapter 3 introduces the problems each post-quantum family is built on, and Chapters 4 through 6 apply this threat model to the primitives it breaks. For now, three bullets is enough.

Classical factoring, to calibrate the threat

Before Shor, factoring is hard. After Shor, factoring is easy.

RSA security rests on the practical assumption that no efficient classical algorithm can factor a properly generated public modulus $n = pq$ . The best known general-purpose classical algorithms run in sub-exponential time, not polynomial. No proof of a superpolynomial classical lower bound is known. The textbook attack is trial division: try every candidate divisor from $2$ up to $\sqrt{n}$ and stop at the first one that divides $n$ . For a toy modulus this finishes in microseconds. For a real modulus it does not finish in the age of the universe.

Here is a tiny RSA modulus and the trial-division routine that breaks it:

def factor_trial_division(n: int) -> tuple[int, int] | None:
    """Return (p, q) with p * q == n if n is composite, else None.

    Trial division up to sqrt(n) is correct for any composite, since every
    composite has a prime factor at most sqrt(n). It is just catastrophically
    slow for moduli the size of any real RSA key.
    """
    candidate = 2
    while candidate * candidate <= n:
        if n % candidate == 0:
            return candidate, n // candidate
        candidate += 1
    return None


toy_modulus = 3233  # the secret factors are 53 and 61
result = factor_trial_division(toy_modulus)
assert result is not None
p, q = result
print(f"{toy_modulus} = {p} x {q}")
# ==> 3233 = 53 x 61

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch01/, one file per block. Appendix C covers the clone and the environment they run on.

At $n = 3233$ this returns instantly. Now scale up. For RSA-2048, $\sqrt{n}$ is on the order of $2^{1024} \approx 1.8 \times 10^{308}$ . A single core at $10^9$ trial divisions per second would need roughly $1.8 \times 10^{308} / 10^9 \approx 1.8 \times 10^{299}$ seconds. A year has about $3.15 \times 10^7$ seconds, so that is roughly $5.7 \times 10^{291}$ years. The age of the universe is around $1.4 \times 10^{10}$ years. The gap is not a matter of throwing more cores at the problem.

Faster classical factoring algorithms exist. The general number field sieve runs in sub-exponential time, with leading-constant complexity

\exp\!\left(\left(\left(64/9\right)^{1/3} + o(1)\right) (\ln n)^{1/3} (\ln \ln n)^{2/3}\right),

where $(64/9)^{1/3} \approx 1.923$ . That is the algorithm modern RSA parameters are set against. RSA-2048 is chosen to keep the expected cost of a number-field-sieve attack beyond any classical budget anybody is willing to fund.

Shor’s algorithm turns factoring into a polynomial-time problem on a quantum computer. Instead of sub-exponential in $\log n$ , the runtime is polynomial in $\log n$ . The same 2048-bit modulus that is classically out of reach becomes an hours-to-months job under published fault-tolerant resource estimates, depending on the architecture and chosen space-time point. For 256-bit elliptic-curve discrete log, the newest estimates reach minutes-scale runtimes under fast-clock superconducting assumptions. The next section gives the resource numbers.

Shor and Grover, at working level

Two quantum algorithms do the damage. Know them both.

Shor, 1994

Shor’s algorithm (Shor, 1994) solves integer factorization and discrete logarithm in polynomial time on a fault-tolerant quantum computer. That is enough to break the pre-quantum public-key primitives used at scale today:

RSA encryption and signatures, because factoring the modulus recovers the private key
Finite-field Diffie-Hellman, because an efficient discrete-log algorithm recovers the private exponent from the public share and breaks the exchange
Elliptic-curve Diffie-Hellman including X25519, because an efficient algorithm for the elliptic-curve discrete-log problem recovers the private scalar from the public share, and Shor is such an algorithm
ECDSA and EdDSA (Ed25519, Ed448), because Shor recovers the signer’s private scalar from the public verification key, after which forgery is trivial
Schnorr signatures on any Shor-reducible group, including secp256k1 Schnorr as used in Bitcoin Taproot

Bitcoin Taproot outputs (Wuille, Nick, & Ruffing, 2020; Wuille, Nick, & Towns, 2020) publish a 32-byte x-only secp256k1 output public key in the output script. That key may be a tweak of an internal key plus a script-tree commitment, but it is still a discrete-log public key. Once Shor is practical for secp256k1, the corresponding private scalar becomes recoverable. Ethereum has a related exposure pattern: any externally owned account (EOA) that has sent a standard ECDSA transaction has exposed enough signature material for its public verification key to be recovered. Ethereum signs transactions with recoverable ECDSA signatures by design, and the Yellow Paper’s Appendix F defines the recovery function that does it (Wood, 2025). From the public verification key, a future Shor-capable attacker recovers the private key. Both classes of key sit on an immutable ledger and become forgeable once Shor lands. Part VII (Chapter 36 and Chapter 37) walks the L1 signature migration.

Resource estimates for running Shor on concrete parameter sets have tightened over the last five years as algorithmic improvements compound.

Roetteler, Naehrig, Svore, and Lauter (Roetteler et al., 2017) give the canonical pre-2023 resource estimate for running Shor against a 256-bit elliptic-curve discrete log.
Gidney and Ekerå (Gidney & Ekerå, 2021) show that RSA-2048 can be factored in about 8 hours using roughly 20 million noisy physical qubits with a surface-code error-correcting layer.
Webber et al. (Webber et al., 2022) study how a resource estimate depends on hardware assumptions (ion-trap versus superconducting, gate fidelity, code distance), taking as their case study the 256-bit elliptic-curve keys the Bitcoin network uses. They report 317 million physical qubits to break one within an hour, and 13 million to break one within a day, under a surface code with a one-microsecond code cycle and a $10^{-3}$ physical gate error rate. The takeaway is methodological: these cost numbers are a function of the hardware model, not physical constants, and they move when the assumptions move.
Litinski (Litinski, 2023) tightens the ECDLP estimate. Its headline figure, roughly 50 million Toffoli gates for a 256-bit ECDLP, is an amortized per-key cost that depends on running many instances in parallel, with state reuse and batched modular inversion spreading the work across keys; the single-instance baseline, under strict 2D-nearest-neighbor connectivity, is about 109 million Toffoli gates and 6000 logical qubits. Either figure is a tightening on (Roetteler et al., 2017). The wall-clock runtime they imply is sensitive to architecture (code-cycle time, locality of two-qubit connections), not just to gate count. No such computation has been executed.
Gidney (Gidney, 2025), in “How to factor 2048-bit RSA integers with less than a million noisy qubits”, returns to the RSA-2048 problem and reduces the physical-qubit estimate from roughly 20 million to fewer than 1 million. Runtime stretches to less than a week, under the same surface-code and gate-error assumptions as the 2021 estimate. The drop comes from algorithmic and error-correction improvements (approximate residue arithmetic, yoked surface codes, magic-state cultivation), not from a hardware-assumption change. The paper is the reference for those techniques, which the book does not cover.
Webster et al. (Webster et al., 2026) push the RSA-2048 physical-qubit count below 100,000 in a preprint, using a quantum low-density-parity-check (qLDPC) code architecture rather than a surface code. That number is one point on a space-time tradeoff: fewer than 100,000 physical qubits at about one month, about 140,000 at one week, and about 400,000 at one day. Because it changes the error-correcting code, it is not directly comparable with the surface-code estimates above. The lower physical-qubit count is bought with a different fault-tolerance architecture and a longer runtime.
Babbush et al. (Babbush et al., 2026) report an ECDLP resource estimate for secp256k1 under fewer than 500,000 physical qubits and minutes-scale runtime. That runtime is comparable to Bitcoin’s roughly 10-minute average block interval, which brings on-spend attacks into scope: an attacker who sees a Shor-vulnerable verification key in a pending transaction can recover the private key in time to front-run or replace it before finality. The paper analyses this in a fast-clock superconducting configuration.

Two things about these numbers matter.

First, every one of them is a cost estimate, not a timeline. The estimate answers “how big does the machine have to be, and how long does the job take, if you built one”; it does not answer “when will somebody build one”. The answer to “when” depends on hardware progress, which the estimates do not model.

Second, the trajectory is down and to the left. Year over year, new work publishes tighter bounds. The threat model should be set against the tightest published estimate, not the loosest, and should be refreshed when a new estimate lands.

Where did demonstrated hardware sit at the end of 2024, the latest date these three figures cover? IBM Condor has 1,121 physical qubits (IBM Research, 2023). IBM Heron r2 has 156 physical qubits (IBM Research, 2024). Google Willow has 105 physical qubits (Acharya et al., 2024). None of these is fault-tolerant at the scale any of the Shor estimates above assume; Willow is the first superconducting device to demonstrate below-threshold logical-qubit error suppression, which is a prerequisite for the fault-tolerant regime, not a demonstration of it.

The gap between “physical qubits demonstrated in hardware” and “physical qubits required for Shor on RSA-2048 or secp256k1” is several orders of magnitude on raw count, but raw count is not the metric that matters. The relevant axes are fault tolerance, logical-qubit error rate, surface-code cycle time, qubit connectivity, and the ability to run long circuits reliably. Progress on those axes is what closes the gap. The book’s working assumption for long-lived cryptographic material is that the gap will eventually close. The threat model is set against that assumption rather than a specific arrival date.

Vendor roadmaps put concrete dates against that trajectory. IBM’s current Quantum Development Roadmap targets Starling, a modular error-corrected quantum-centric supercomputer planned at 200 logical qubits and 100 million gates, by 2029 (IBM Research, 2025). The book treats vendor targets as forecasts rather than commitments and continues to set the threat model against the trajectory rather than against any single dated milestone.

Grover, 1996

Grover’s algorithm (Grover, 1996) gives a quadratic speedup on unstructured search. If an attack on a primitive reduces to searching through $N$ possible values, a classical attacker runs in $O(N)$ , and a Grover attacker runs in $O(\sqrt{N})$ .

The naive $\sqrt{N}$ is the cost in the idealized serial-query model, not the concrete attack cost. Every Grover iteration has to evaluate the target primitive reversibly, under error correction, within whatever circuit-depth budget the attacker can tolerate. The real cost is $\sqrt{N}$ times the quantum cost of one oracle call, plus the depth and parallelization overhead that comes with it. Grassl et al. (Grassl et al., 2016) and Jaques et al. (Jaques et al., 2020) work out the concrete Grover cost on AES key search and find that it is considerably higher than the naive bound. This is why NIST uses AES-128 key search as the Category 1 benchmark rather than treating AES-128 as obsolete under Grover.

For symmetric primitives Grover is still the main quantum attack to reason about. The effect, at the lower-bound level of approximation, is simpler than Shor’s:

AES-128 has a $2^{128}$ brute-force search space classically. In the idealized serial-query model, Grover reduces that to about $2^{64}$ quantum oracle queries, but the concrete cost remains higher because each oracle call has to evaluate AES reversibly and because depth, error-correction, and parallelization overhead matter (Grassl et al., 2016; Jaques et al., 2020). NIST keeps it as Category 1.
AES-256 has $2^{256}$ classically and $2^{128}$ (lower bound) under Grover, which is fine.
SHA-256 preimage search has $2^{256}$ classically and $2^{128}$ (lower bound) under Grover, again fine.
SHA-384, SHA-512, SHA3-384, SHA3-512 are safe by even larger margins.

Preimage and collision resistance do not degrade at the same rate, which is why the categories below name both. Grover searches an $n$ -bit preimage space in about $2^{n/2}$ queries. Collision finding is cheaper: the Brassard-Hoyer-Tapp algorithm finds one in about $2^{n/3}$ quantum evaluations (Brassard et al., 1998), against a classical birthday bound of about $2^{n/2}$ . Query counts are not concrete costs, and the gap matters here. BHT buys its speedup with quantum-accessible memory on the same $2^{n/3}$ scale, so the query exponent alone does not determine a NIST category. NIST measures an attack against several resource metrics rather than one, and a category comparison needs a concrete circuit and memory cost model (National Institute of Standards and Technology, 2016). Chapter 18 works through both bounds for hash-based signatures, and Chapter 32 sizes parameters against them.

The mitigation for symmetric primitives is usually simple: increase the relevant security parameter (key length for block ciphers, output length for hash functions, tag and key sizes for MACs where needed). The harder migration is asymmetric, because RSA, finite-field DH, ECDH, ECDSA, EdDSA, and Schnorr over Shor-reducible groups have no analogous one-line fix. They need new primitives. NIST’s post-quantum security categories are defined in exactly these terms (National Institute of Standards and Technology, 2016). There are five, not three:

Category 1: any attack at least as hard as AES-128 key search
Category 2: SHA-256 or SHA3-256 collision search
Category 3: AES-192 key search
Category 4: SHA-384 or SHA3-384 collision search
Category 5: AES-256 key search

Every PQC parameter set standardized in FIPS 203, 204, and 205 is tagged to one of these categories. Chapter 13 returns to them when lattice parameter selection is discussed.

Grover is dominated by Shor on Shor-reducible problems; for symmetric primitives it remains the main quantum attack to reason about. Do not conflate the two algorithms when reading popular coverage. They are routinely blurred together.

Harvest now, decrypt later

The consequence of Shor is that the threat does not wait for the quantum computer to arrive. Any ciphertext whose confidentiality depends on a Shor-vulnerable public-key layer, or on a classical-only key exchange recorded today, is exposed the day Shor becomes executable at scale. This is “harvest now, decrypt later”, abbreviated HNDL. Chapter 34 names the proof-system version of the same timing problem “collect now, forge later”, or CNFL (Renz, 2026), where the exposed asset is a verifier still accepting proofs after the crossover. The signature side does not have that shape and gets no name here: a verification key is public by construction, so nothing has to be recorded first. Once Shor recovers the signing key behind a verification key that is still trusted, an attacker forges objects that verify under old trust anchors, whether or not it collected anything beforehand.

Mosca (Mosca, 2018) frames the timing question with an inequality that is now standard in migration planning. Let $X$ be the useful lifetime of your secrets, $Y$ the time needed to migrate your systems, and $Z$ the time until a fault-tolerant quantum computer exists. If $X + Y > Z$ , your secrets are already at risk. The inequality has three unknowns. $X$ is the data owner’s responsibility, $Y$ is the organization’s, and $Z$ is nobody’s. Estimating $Y$ is a years-long planning exercise for any non-trivial system; estimating $X$ depends on the data class; $Z$ has no reliable consensus date. Agencies can set migration deadlines and experts can defend planning ranges, but nobody can currently assign a dependable arrival date to a CRQC.

The practical consequence: migration is not something to defer for data whose confidentiality must hold into the mid-2030s. The book adopts “confidentiality lifetime past roughly 2035” as an operational rule of thumb for classifying a secret as HNDL-exposed. The threshold is a planning heuristic, not a derivation from those policy deadlines. The right threshold for each deployment depends on its own assumed quantum-arrival range.

Several national policies anchor the timeline. The National Cyber Security Centre (NCSC) in the UK sets a phased path with three dates: a migration plan by 2028, high-priority migrations by 2031, and full migration by 2035 (UK National Cyber Security Centre, 2025). In the US, National Security Memorandum 10 (NSM-10, a 2022 White House memorandum) states the goal of mitigating as much quantum risk as is feasible by 2035. NSA’s CNSA 2.0 then commits National Security Systems to be quantum-resistant by 2035, with Committee on National Security Systems Policy 15 (CNSSP 15) setting a 31 December 2031 milestone for mandatory CNSA 2.0 use (US National Security Agency, 2024).

For civilian federal systems, Executive Order 14412 (June 2026) sets earlier deadlines on High Value Assets and High Impact Systems: 31 December 2030 for key establishment and 31 December 2031 for signatures. Office of Management and Budget (OMB) Memorandum M-26-15 sets the migration schedule for non-national-security federal systems through 2035 (Office of Management and Budget, 2026; The White House, 2026). These timelines are load-bearing for the rest of this book. Part V is about meeting them.

The figure below shows the window that matters for any piece of long-lived data. The top row is the data’s confidentiality requirement. The bottom row is the cryptographic capability of the world around it. The overlap on the right is the HNDL exposure: the span during which the ciphertext is still sensitive and the adversary now has Shor.

Figure 1.1. HNDL exposure exists whenever data captured today must remain confidential past the CRQC arrival date Z. The 2035 marker is a migration-planning target, not a prediction of Z.

What survives, and where to find it

Shor does not break every public-key primitive. It breaks the ones whose security depends on the hardness of integer factorization or discrete logarithms. The hard problems behind the four families this book builds from scratch have no known quantum polynomial-time algorithm as of this writing.

Four families anchor the technical parts of this book.

Lattice-based schemes rest on structured-lattice assumptions. ML-KEM (FIPS 203, (National Institute of Standards and Technology, 2024)) is based on the Module Learning With Errors (MLWE) problem, and ML-DSA (FIPS 204, (National Institute of Standards and Technology, 2024b)) on MLWE together with a nonstandard variant of Module Short Integer Solution called SelfTargetMSIS. The hardness of MLWE itself rests on the presumed hardness of computational problems on module lattices, which is where the family gets its name. ML-KEM is the flagship key-encapsulation mechanism (KEM) and ML-DSA is one of the two signature flagships. Part II builds both from scratch.
Hash-based signatures rest on the one-wayness of hash functions rather than on collision resistance. FIPS 205 is explicit about the second half: even if collisions were feasible on the functions instantiating SLH-DSA’s internals, there is believed to be no adverse effect on its security. Collision resistance enters only for the digest, when a message is hashed before signing (National Institute of Standards and Technology, 2024c). SLH-DSA is the stateless hash-based signature flagship. Part III builds SLH-DSA from scratch.
Code-based schemes reduce to decoding problems for error-correcting codes. Classic McEliece hides structure in a Goppa-code family; HQC uses a quasi-cyclic code-based design and was selected by NIST in March 2025 as a backup KEM to ML-KEM (National Institute of Standards and Technology, 2025), with the final FIPS publication expected in 2027 (National Institute of Standards and Technology, 2025b). Part IV builds both from scratch, starting with the original McEliece construction from 1978.
Isogeny-based schemes reduce to finding an isogeny between two supersingular elliptic curves. SQIsign advanced to the third round of NIST’s Additional Digital Signatures process in May 2026 (National Institute of Standards and Technology, 2026) and is not yet a FIPS standard. It was not affected in the same way as SIDH or SIKE because its security does not rely on the torsion-point leakage Castryck and Decru exploited. Part IV walks a simplified SQIsign.

A planned third NIST signature standard, FN-DSA (Fast-Fourier lattice-based digital signature algorithm) derived from FALCON, is in development as FIPS 206 alongside ML-DSA (FIPS 204) and SLH-DSA (FIPS 205). NIST has described the FIPS 206 Initial Public Draft as forthcoming and awaiting approval. Final publication is expected later in the standard NIST review cycle (Perlner, 2025). The book treats ML-DSA and SLH-DSA first because they are already finalized.

Symmetric primitives survive Shor entirely and survive Grover when the relevant security parameter is sized for it. AES-256 is conservative for symmetric encryption. SHA-256 and SHA3-256 remain appropriate for preimage and MAC-style uses, with longer outputs (SHA-384, SHA3-384, or longer) chosen for collision-sensitive designs against the required NIST category. HMAC remains sound when instantiated with adequate keys and outputs. What does not survive is any protocol that wraps symmetric material inside a Shor-reducible public-key layer. In a TLS 1.3 handshake, for example, the symmetric authenticated encryption with associated data (AEAD) that protects the session (typically AES-GCM or ChaCha20-Poly1305) is fine. The vulnerability is the X25519 key exchange used to establish the shared secret from which the TLS traffic keys are derived. Replace the key exchange, keep the AEAD. Chapter 27 gives the hybrid construction, and Chapter 28 walks the fleet migration in detail.

One family the book does not build from scratch is multivariate quadratic. UOV has a long history. It, MAYO, and SNOVA advanced to the third round of NIST’s Additional Digital Signatures process in May 2026 (National Institute of Standards and Technology, 2026), together with SQIsign and five other schemes selected from the 14 second-round advancers NIST announced in October 2024 (National Institute of Standards and Technology, 2024d). Multivariate signatures can be very small, sometimes competitive with ECDSA, but typically at the cost of large public keys. That tradeoff and a difficult cryptanalytic history make conservative parameter selection harder than for lattices or hashes. Chapter 24 covers them and the additional-signatures on-ramp, which exists in part to address the kilobyte-scale signatures that ML-DSA and SLH-DSA produce. Those sizes cause real bandwidth pressure in TLS, QUIC, and certificate-heavy protocols.

NIST is also addressing the issue from the SLH-DSA side. SP 800-230 (April 2026 Initial Public Draft) adds parameter sets for limited-use signing keys, capped at $2^{24}$ signatures, intended for software-signing, firmware-signing, and digital-certificate scenarios that do not need an unlimited signing budget (Moody & Dang, 2026). Chapter 29 covers software and firmware signing in deployment terms.

Standardization runs ahead of deployment, and deployment is uneven. Hybrid key exchange (X25519 + ML-KEM) is the default in Chrome 131 and later, and runs across Cloudflare’s edge whenever the client also negotiates a hybrid group. Signatures are further behind. WebPKI certificates, SSH host keys, code-signing and firmware-signing systems, and blockchain signatures remain predominantly classical. Migrating the ones this book covers is the work of Part V (WebPKI, code and firmware signing) and Part VII (blockchain).

Exercises

Consider a TLS 1.3 connection recorded today that used X25519 for key exchange, ECDSA over P-256 for server authentication, and AES-256-GCM for application data. For each of the three primitives, state which quantum algorithm applies (Shor or Grover), what a future quantum attacker gains from it, and whether the primitive must be replaced or can stay as it is. Then explain, in two or three sentences, why recovering the server’s ECDSA signing key years later does not by itself decrypt the recorded session.
Write a counted variant of the trial-division routine, factor_trial_division_counted, returning the number of candidate divisions alongside the factor pair. Start from the block printed above and leave it unchanged. The counting is the exercise, not the search, and the chapter’s suite checks that the two agree. Print the count with the pair and confirm it for $3233 = 53 \times 61$ . Then, using the chapter’s RSA-2048 trial-division estimate, explain in two sentences why speeding up the classical implementation by forty orders of magnitude would still leave the attack infeasible. (Optional: state the worst-case count on a 2048-bit modulus as a power of ten, and, assuming one candidate division per nanosecond, compare it to the age of the universe in nanoseconds, about $4 \times 10^{26}$ ns.)
Pick one system or data class you rely on that must stay confidential or verifiable for many years: a document archive, a firmware-signing key, a long-lived TLS session log, or a blockchain account. Estimate $X$ , the number of years the data must stay protected, and $Y$ , the years your organization would need to migrate it. Then evaluate the Mosca inequality $X + Y > Z$ under two hypothetical values for $Z$ , the years until a CRQC arrives. Take one early and one late, drawn from a probabilistic forecast such as the Global Risk Institute survey (Mosca & Piani, 2026) rather than from a migration deadline. State which of $X$ , $Y$ , and $Z$ you know and which you are assuming, and say whether migration should begin now. If a value is unknown, say what you would measure to pin it down.
(Optional.) Read the abstract of Gidney and Ekerå (Gidney & Ekerå, 2021) and compare its headline RSA-2048 estimate with Gidney (Gidney, 2025). Record the physical-qubit count and the runtime each reports. Then explain in two sentences why the four-year gap between them is a space-time and error-correction-design comparison, not evidence that quantum hardware improved twentyfold. The point is to practice reading a resource-estimate paper at the abstract level without working through its internals.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 1. A separate track, for rebuilding rather than reading: the package exercises/ch01-quantum-threat has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch01 to grade your version against the suite that proves the reference one.

References

Acharya, R., et al. (2024). Quantum error correction below the surface code threshold. Nature, 638, 920–926. https://doi.org/10.1038/s41586-024-08449-y

Babbush, R., Zalcman, A., Gidney, C., Broughton, M., Khattar, T., Neven, H., Bergamaschi, T., Drake, J., & Boneh, D. (2026). Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations. PRX Quantum, 7(3), 031001. https://doi.org/10.1103/j3xf-bw18

Brassard, G., Høyer, P., & Tapp, A. (1998). Quantum Cryptanalysis of Hash and Claw-Free Functions. LATIN ’98: Theoretical Informatics, 1380, 163–169. https://doi.org/10.1007/bfb0054319

Gidney, C. (2025). How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv:2505.15917. https://arxiv.org/abs/2505.15917

Gidney, C., & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433. https://doi.org/10.22331/q-2021-04-15-433

Grassl, M., Langenberg, B., Roetteler, M., & Steinwandt, R. (2016). Applying Grover’s algorithm to AES: quantum resource estimates. Post-Quantum Cryptography – PQCrypto 2016. https://arxiv.org/abs/1512.04965

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 212–219. https://doi.org/10.1145/237814.237866

IBM Research. (2023). IBM Condor: 1,121-qubit superconducting quantum processor. IBM Quantum hardware announcement. https://www.ibm.com/quantum/blog/quantum-roadmap-2033

IBM Research. (2024). IBM Heron r2: 156-qubit superconducting quantum processor. IBM Quantum Developer Conference announcement. https://www.ibm.com/quantum/blog/qdc-2024

IBM Research. (2025). IBM Quantum Development Roadmap. IBM Quantum roadmap. https://www.ibm.com/roadmaps/quantum/

Jaques, S., Naehrig, M., Roetteler, M., & Virdia, F. (2020). Implementing Grover oracles for quantum key search on AES and LowMC. Advances in Cryptology – EUROCRYPT 2020. https://doi.org/10.1007/978-3-030-45724-2_10

Litinski, D. (2023). How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates. https://arxiv.org/abs/2306.08585

Moody, D., & Dang, Q. (2026). NIST SP 800-230 ipd: Additional SLH-DSA Parameter Sets for Limited-Signature Use Cases. National Institute of Standards and Technology. https://doi.org/10.6028/NIST.SP.800-230.ipd

Mosca, M. (2018). Cybersecurity in an era with quantum computers: will we be ready? IEEE Security & Privacy, 16(5), 38–41. https://doi.org/10.1109/MSP.2018.3761723

Mosca, M., & Piani, M. (2026). Quantum Threat Timeline Report 2025. Global Risk Institute. https://globalriskinstitute.org/publication/quantum-threat-timeline-report-2025b/

National Institute of Standards and Technology. (2016). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Call for Proposals, Section 4.A.5 (Security Strength Categories). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

National Institute of Standards and Technology. (2024a). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203

National Institute of Standards and Technology. (2024b). FIPS 204: Module-Lattice-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.204

National Institute of Standards and Technology. (2024c). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205

National Institute of Standards and Technology. (2024d). Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process: Round 2 Submissions. NIST Computer Security Resource Center, on-ramp round-2 announcement. https://csrc.nist.gov/news/2024/pqc-digital-signature-second-round-announcement

National Institute of Standards and Technology. (2025a). Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process (Internal Report NIST IR 8545). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8545

National Institute of Standards and Technology. (2025b). NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption. NIST news release. https://www.nist.gov/news-events/news/2025/03/nist-selects-hqc-fifth-algorithm-post-quantum-encryption

National Institute of Standards and Technology. (2026). Status Report on the Second Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process (Internal Report NIST IR 8610). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8610

Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. https://www.cambridge.org/highereducation/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE

Office of Management and Budget. (2026). OMB Memorandum M-26-15: Execution of the Migration to Post-Quantum Cryptography. Executive Office of the President, OMB; whitehouse.gov. https://www.whitehouse.gov/wp-content/uploads/2026/06/M-26-15-Execution-of-the-Migration-to-Post-Quantum-Cryptography.pdf

Perlner, R. (2025). FIPS 206 Status Update: Fast-Fourier Lattice-Based Digital Signature Standard (FN-DSA, Falcon). NIST Computer Security Resource Center status presentation. https://csrc.nist.gov/presentations/2025/fips-206-fn-dsa-falcon

Renz, A. (2026). Post-Quantum Risk in Deployed Zero-Knowledge Architectures: A Layered Analysis. Self-published technical report, Zenodo. https://doi.org/10.5281/zenodo.21425310

Rescorla, E. (2026). The Transport Layer Security (TLS) Protocol Version 1.3. RFC 9846. https://doi.org/10.17487/RFC9846

Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K. (2017). Quantum resource estimates for computing elliptic curve discrete logarithms. Advances in Cryptology – ASIACRYPT 2017. https://doi.org/10.1007/978-3-319-70697-9_9

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), 124–134. https://doi.org/10.1109/SFCS.1994.365700

The White House. (2026). Executive Order 14412: Securing the Nation Against Advanced Cryptographic Attacks. Presidential Executive Order; Federal Register 91 FR 38483 (25 June 2026), FR Doc. 2026-12909. https://www.whitehouse.gov/presidential-actions/2026/06/securing-the-nation-against-advanced-cryptographic-attacks/

UK National Cyber Security Centre. (2025). Timelines for migration to post-quantum cryptography. NCSC guidance. https://www.ncsc.gov.uk/guidance/pqc-migration-timelines

US National Security Agency. (2024). Commercial National Security Algorithm Suite 2.0 Frequently Asked Questions, Version 2.1. NSA Cybersecurity Advisory. https://media.defense.gov/2022/Sep/07/2003071836/-1/-1/0/CSI_CNSA_2.0_FAQ_.PDF

Webber, M., Elfving, V., Weidt, S., & Hensinger, W. K. (2022). The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime. AVS Quantum Science, 4(1). https://doi.org/10.1116/5.0073075

Webster, P., Berent, L., Chandra, O., Hockings, E. T., Baspin, N., Thomsen, F., Smith, S. C., & Cohen, L. Z. (2026). The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100,000 physical qubits using quantum LDPC codes. arXiv:2602.11457. https://arxiv.org/abs/2602.11457

Wood, G. (2025). Ethereum: A Secure Decentralised Generalised Transaction Ledger. Shanghai version efc5f9a, 2025-02-04. https://ethereum.github.io/yellowpaper/paper.pdf

Wuille, P., Nick, J., & Ruffing, T. (2020). BIP-340: Schnorr Signatures for secp256k1. Bitcoin Improvement Proposal. https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki

Wuille, P., Nick, J., & Towns, A. (2020). BIP-341: Taproot: SegWit version 1 spending rules. Bitcoin Improvement Proposal. https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki

Last updated: Sep 14, 2026