Chapter 20 — Quantum and post-quantum security: foundational cases
Lesson map
Lesson 20 published. Map, example, EX039.
flowchart TD
N0["Learning outcomes"]
N1["20.1 Shor and resource estimates"]
N2["20.2 Broken candidates"]
N3["20.3 Implementation flaws"]
N4["20.4 Early deployment"]
N5["20.6 Practical activity"]
N6["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6
N6 --> EX["Worked example"]
EX --> Q["Exercise EX039"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["20.1 Shor and resource estimates"]
N2["20.2 Broken candidates"]
N3["20.3 Implementation flaws"]
N4["20.4 Early deployment"]
N5["20.6 Practical activity"]
N6["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6 --> Q["EX039"]
[Learning outcomes]
|
v
[20.1 Shor and resource estimates]
|
v
[20.2 Broken candidates]
|
v
[20.3 Implementation flaws]
|
v
[20.4 Early deployment]
|
v
[20.6 Practical activity]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX039]
Learning outcomes
You will (1) summarise public cases that shaped post-quantum practice; (2) explain what each case teaches about evidence and assumptions; (3) relate the cases to hybrid deployment; and (4) apply their lessons to HCU decisions.
20.1 Shor and resource estimates
Shor's 1994 algorithm (journal version 1997) showed that factoring and discrete logarithms are efficiently solvable on a quantum computer. For decades, the question was resources. Gidney and Ekerå (2021) estimated 20 million noisy qubits running for eight hours to factor RSA-2048; Gidney (2025) lowered this to under a million noisy qubits in under a week, under stated assumptions about error rates and connectivity. The lesson: resource estimates fall as algorithms and error correction improve, so plans must not depend on today's estimate staying fixed.
HCU's plan therefore uses a range of arrival dates rather than one figure.
20.2 Broken candidates
The NIST process eliminated candidates publicly. Rainbow, a multivariate signature, was broken by Beullens (2022) with a key-recovery attack running "over a weekend on a laptop". SIKE, an isogeny-based KEM, was broken by Castryck and Decru (2022) with a classical attack. Both had survived years of analysis. The lesson: new schemes carry the risk of classical breaks, which is a main argument for hybrid deployment — combining a post-quantum and a traditional algorithm so that an attacker must break both.
Neither break needed a quantum computer.
20.3 Implementation flaws
KyberSlash (Bernstein et al., 2024) showed that several implementations of Kyber leaked secret information through timing of division operations, even though the mathematics was sound. The lesson: a correct standard is not a correct implementation; use vetted libraries and keep them updated.
For HCU the lesson became a procurement question: which library and version does each appliance use, and how quickly does the vendor ship fixes? A vendor that cannot answer is a risk regardless of which algorithm it claims to support.
20.4 Early deployment
Google's Chrome team announced hybrid post-quantum key exchange in 2023 (Chromium Blog), and some servers and middleboxes failed on the larger ClientHello. The lesson: deployment exposes ecosystem bugs that no specification review finds; staged rollout and monitoring are essential.
Most failures came from software that had assumed handshake messages would stay small. Browsers rolled out gradually, measured failures and worked with server operators to fix them. HCU follows the same pattern on a smaller scale with its pilot branches.
20.5 Worked example
HCU's vendor proposes enabling pure ML-KEM on branch VPNs immediately. Applying the cases: SIKE shows that a new scheme can fail suddenly, so a hybrid with ECDH is the prudent transition design; KyberSlash shows that the vendor's implementation version matters, so HCU asks which library and version the appliance uses; the Chrome experience shows that one branch with a legacy device might break, so HCU starts with three pilot branches.
Each pilot branch is monitored for fallback and handshake failures before any wider rollout is approved.
20.6 Practical activity
Write a half-page lesson card for one of the four cases: what happened, primary source, what it changed in practice, and one question it raises for HCU.
A good card is short enough to read in a minute and links to the primary source, not a summary of it. The practical change should be specific, such as the move to hybrid designs or stricter timing tests. Your question for HCU should be one the team could actually answer, for example which of its vendors' products still use a vulnerable library version.
20.7 Common errors and limits
- Concluding from SIKE that all PQC is fragile; ML-KEM rests on a different, well-studied problem family.
- Treating resource estimates as predictions of dates.
- Assuming a final standard implies safe implementations.
SIKE and Rainbow were broken through their own structures; ML-KEM's lattice problems have a long research history and have resisted analysis. That is evidence, not proof, which is why hybrids are used during transition. Resource estimates show what an algorithm would need, not when someone will build it. Implementations need separate review and testing, as KyberSlash showed for a sound design.
Exercises
- EX039 — Case to control. Map each of the four cases to one control HCU should adopt. Rubric: 3 = four plausible, distinct mappings.
- EX040 — Estimate trend. Explain why falling resource estimates should change the y (migration time) planning in Mosca's inequality, not just z. Rubric: 3 = argues for starting earlier and building agility.
Synthesis
Falling resource estimates, broken candidates, implementation flaws and deployment bugs each teach a control: plan for uncertainty, deploy hybrids, use vetted libraries and roll out in stages.
Continue studying — chapter 20 of 40
← Chapter 19 (draft) · Course chapter index · Chapter 21 (draft) →