PDF LaTeX source Comments

Chapter 1The Quantum Threat

1.1Why this chapter matters#

Every other chapter in this book builds toward schemes labelled post-quantum. This chapter explains what that word is reacting to. Post-quantum cryptography exists because a sufficiently large quantum computer would break almost all of the public-key cryptography deployed today – the very algorithms protecting web traffic, software updates, and stored data right now. Understanding which problems fall, which survive, and why is the motivation for everything that follows.

1.2Learning goals#

After reading this chapter, you should be able to:

• name the hard problems that today’s public-key cryptography relies on;

• explain, at a high level, what Shor’s and Grover’s algorithms do;

• distinguish what a quantum computer breaks from what it merely weakens;

• read a quantum resource estimate, and say what it does and does not establish;

• explain “harvest now, decrypt later” and state Mosca’s inequality;

• place the published NIST standards and the main mathematical families in context;

• interpret the NIST security categories that name every parameter set in this book.

1.3What today’s cryptography rests on#

Classical public-key cryptography stands on two number-theoretic problems that are believed hard for ordinary computers:

• Integer factorization – given a large \(N = p\cdot q\), recover the primes \(p\) and \(q\). This is the foundation of RSA.

• Discrete logarithm – given \(g\) and \(g^x\) in a suitable group, recover \(x\). This underlies Diffie–Hellman key exchange and elliptic-curve schemes such as ECDSA and ECDH.

For a classical computer, the best known algorithms for both problems run in super-polynomial (sub-exponential or worse) time, so the parameters can be chosen to make an attack take longer than the age of the universe. That safety margin is exactly what a quantum computer removes.

1.4Shor’s algorithm: the break#

In 1994 Peter Shor showed that a quantum computer can factor integers and compute discrete logarithms in polynomial time [1]. The engine is period finding: both problems can be recast as finding the period of a cleverly chosen function, and a quantum computer extracts that period efficiently using the quantum Fourier transform – evaluating the function on a superposition of all inputs at once, then interfering the results so that the period stands out.

The consequence is stark: RSA, Diffie–Hellman, ECDSA, and ECDH are all broken by a large enough quantum computer, no matter how big the keys are. Doubling an RSA key only adds polynomial work for Shor’s algorithm – it does not restore security. There is no parameter choice that saves them.

1.5Grover’s algorithm: the weakening#

Symmetric cryptography (block ciphers like AES) and hash functions (like SHA-3) face a milder threat. Grover’s algorithm [2] speeds up generic search: finding a marked item among \(N\) possibilities takes about \(\sqrt{N}\) steps instead of \(N\). Against a symmetric key of \(b\) bits, this cuts the effective security to roughly \(b/2\) bits.

Crucially, this is a quadratic speedup, not an exponential one. For exhaustive key search, AES-256 therefore retains roughly \(128\) bits of generic quantum-search security. Hash properties must be treated separately: for an \(m\)-bit ideal hash, preimage and second-preimage search have a generic Grover-style cost of about \(2^{m/2}\), whereas collision search has different quantum algorithms and cost models. In the quantum-query model, the Brassard–Høyer–Tapp algorithm [3] finds collisions in about \(2^{m/3}\) queries; memory, circuit cost, and concrete security estimates require separate analysis. Symmetric primitives survive, but their parameters and security goals must be chosen carefully.

1.6How large a quantum computer?#

“Broken by a large enough quantum computer” is the right statement, and it is also an unsatisfying one: it says nothing about how large. The literature that answers this is called resource estimation, and reading one of its results correctly is a skill worth acquiring before any of the migration arguments in this book will carry weight.

A resource estimate is not a single number. Three quantities must be satisfied simultaneously, and a machine that fails any one of them cannot run the attack:

• Width – how many logical qubits the circuit needs at once.

• Depth – how many logical operations it executes in total, usually reported as a count of Toffoli or \(T\) gates, since those are the expensive non-Clifford operations.

• Wall-clock time – width and depth together with the physical cycle time determine how long the machine must run coherently under error correction. An attack that takes a decade is not an attack.

The gap between a logical qubit and a physical one is where almost all of the cost lives. A logical qubit is an error-corrected abstraction built from many noisy physical qubits; at present that overhead is roughly three orders of magnitude. Google’s 2025 demonstration that a surface-code memory can run below threshold – adding physical qubits makes the logical error rate fall rather than rise – is the result that makes the whole construction credible in principle [4], and quantum low-density-parity-check codes are an active line of work aimed at cutting the overhead further [5]. Neither changes the fact that published logical-qubit counts today are in the single or low double digits, against the roughly one thousand that the estimates below assume.

Two lessons matter more than any individual row.

The first is the direction of travel. The estimate for RSA-2048 fell from twenty million physical qubits to under one million in four years, and essentially none of that came from better hardware: it came from better circuits for modular arithmetic and from more efficient error correction. This is the reverse of the intuition most readers arrive with. The threat advances through the cryptography and the coding theory, which are cheap to improve, not only through the qubit count, which is expensive.

The second is that elliptic curves are the easier target. The instinct that a 256-bit key must be harder than a 2048-bit one is exactly wrong here: elliptic-curve discrete logarithms need a smaller quantum circuit than factoring a comparable-security RSA modulus [9]. Any system whose signatures are elliptic-curve – which is to say nearly every deployed signature scheme, and every blockchain in Chapter 28 – falls before RSA does, not after.

1.7Harvest now, decrypt later#

A natural objection is that large quantum computers do not yet exist, so why migrate today? The answer is harvest now, decrypt later. An adversary can record encrypted traffic today and decrypt it years later once a quantum computer is available. Any data that must remain confidential beyond the arrival of quantum computing is therefore already at risk.

Signatures create a different risk. A future quantum adversary may forge new signatures, including signatures on malicious firmware or certificates, and may undermine long-term verification. Whether a historically verified signature remains useful depends on its timestamp, archival evidence, and trust model; it is not a case of “record now, decrypt later.” Both risks argue for migration before the threat materializes.

Mosca’s inequality#

The argument can be made precise. Let \(x\) be the number of years a secret must remain secure (its shelf life), \(y\) the number of years the migration itself will take, and \(z\) the number of years until a cryptographically relevant quantum computer exists. Michele Mosca’s observation [10] is that there is a problem whenever \[x + y \;>\; z .\]

The reasoning is a deadline calculation. Migration finishes at year \(y\); a secret created today must survive until year \(x\); so if \(x + y\) exceeds \(z\), some secret is still live at the moment the attacker acquires the capability. Note what the inequality does not require: no term needs to be known accurately, and \(z\) in particular is unknowable. It is enough that \(x + y\) be large, because then the inequality is violated for a wide range of plausible \(z\).

The inequality is also what makes the blockchain case in Chapter 28 so much sharper than the rest of this book’s: there, \(x\) is not fifty years but unbounded, because a public key committed to an immutable ledger is exposed for as long as the ledger exists.

1.8The response: post-quantum standards#

Because Shor’s algorithm targets the specific structure of factoring and discrete logarithms, the defense is to build public-key cryptography on entirely different hard problems – ones with no known efficient quantum algorithm. After a multi-year public competition, NIST selected the first post-quantum schemes:

• FIPS 203 – ML-KEM (Kyber): key encapsulation, based on module lattices [11];

• FIPS 204 – ML-DSA (Dilithium): signatures, based on module lattices [12];

• FIPS 205 – SLH-DSA (SPHINCS⁺): signatures, based only on hash functions [13];

• a future FN-DSA standard based on Falcon is tracked separately; any implementation discussion must name the exact draft or specification version it follows.

Post-quantum cryptography is commonly organized into five broad mathematical families of hard problems, each offering a different route to quantum-resistant public-key cryptography [14]. This is a teaching classification, not a claim that the families are cryptographically independent.

• Lattice-based – short vectors and noisy linear systems in high-dimensional lattices [15, 16]. The workhorse of the standards, balancing speed and size; the main subject of this book.

• Hash-based – security reduced to nothing but a hash function; the most conservative choice, resting on the longest-understood assumption (Chapter 21).

• Code-based – decoding random-looking linear codes; the oldest family, with a decades-long track record (Chapter 22).

• Multivariate – solving systems of multivariate quadratic equations over a finite field [17]; very compact signatures and large keys, with a turbulent cryptanalytic history (Chapter 24).

• Isogeny-based – walking between elliptic curves along secret isogenies; the smallest keys of all, but the youngest and least settled family (Chapter 25).

The NIST standards are concrete implementations of the first two families: three are lattice schemes and one is hash-based. The code-based, multivariate, and isogeny families have no FIPS standard yet, but each offers active candidates and, crucially, a structurally different hedge should a future attack ever undermine lattices. Table 1.3 places every standard in its family.

NIST security categories#

Every parameter set in this book carries a number — ML-KEM-768, ML-DSA-65, SLH-DSA-192s — and behind each sits a NIST security category. The categories are worth understanding once, here, because they explain a convention that otherwise looks arbitrary.

The difficulty NIST faced is the one Section 1.6 and the Grover discussion above have already exposed: “bits of quantum security” is not a well-defined quantity. It depends on the attack model, on whether quantum memory is free, on circuit depth limits, and on which property of the primitive is under attack. Rather than quote a number that would not survive scrutiny, NIST defined each category by reference to a classical primitive whose cost is well understood, and required a candidate to be at least as hard to break as that reference:

Two consequences follow. First, categories are comparable across families: a Category 3 lattice scheme and a Category 3 hash-based scheme make the same claim, which is exactly what a reader choosing between the chapters of this book needs. Second, the categories say nothing about confidence in the underlying assumption. SLH-DSA-128s and ML-KEM-512 both sit at Category 1, but one rests on a hash function and the other on module lattices, and no category number captures that difference. Choosing a scheme means choosing a category and a family.

A category assignment is a claim, and claims can be contested. The Category 1 assignment of ML-KEM-512 in particular has been publicly disputed: the underlying lattice attack-cost estimates carry tens of bits of stated uncertainty [18], and the calculation NIST offered in support of the assignment has been challenged on the grounds that it combined computation and memory-access costs incorrectly [19]. The dispute is about that one parameter set, not about the category system; deployments have largely standardized on ML-KEM-768 and above, which sidesteps it.

1.9Summary#

• Today’s public-key cryptography (RSA, Diffie–Hellman, ECC) rests on factoring and discrete logarithms.

• Shor’s algorithm solves both in polynomial time on a quantum computer, breaking these schemes at any key size.

• Grover’s algorithm gives a quadratic generic-search speedup; key search, hash preimages, and hash collisions need separate security analyses.

• Resource estimates bound width, depth, and runtime together; the published figure for RSA-2048 fell from 20 million physical qubits to under 1 million in four years, driven by better circuits and error correction rather than better hardware — and elliptic curves are the cheaper target, not the harder one.

• Confidentiality has a “harvest now, decrypt later” risk; signature migration concerns future forgery and long-term verification. Mosca’s inequality \(x + y > z\) turns both into a deadline that does not require knowing \(z\).

• The rest of the book surveys five broad mathematical families – lattice, hash, code, multivariate, and isogeny – with FIPS 203–205 as published NIST standards at this snapshot, and every parameter set labelled by a NIST security category defined against AES key search or hash collision search.

The remaining chapters start from the ground up: the mathematical objects – finite fields, vectors, polynomials, and lattices – on which these new hard problems are built.

References