51. Quantum Cryptography
51.1Quantum Threats to Cryptography
Inventory, precisely. Broken by Shor: RSA, Diffie–Hellman, elliptic-curve cryptography — the entire public-key infrastructure of the internet, TLS, code signing, cryptocurrencies' signatures. Degraded by Grover: symmetric ciphers and hashes — AES-128's effective security halves to 2⁶⁴ (fix: AES-256), SHA-256 preimage resistance similarly. Untouched (so far): lattice-based, hash-based, code-based, isogeny-adjacent schemes — post-quantum cryptography. The threat has a clock: "harvest now, decrypt later" means encrypted traffic recorded today is readable the day a CRQC (cryptographically relevant quantum computer) exists, so the migration deadline is now for data with long secrecy lifetimes — regardless of when the hardware arrives.
51.2Shor and RSA
RSA's security: factoring a 2048-bit modulus. Shor (Ch. 26): polynomial-time quantum factoring — the existence proof that public-key crypto's foundation is conditional on the (extended) Church–Turing thesis, which quantum computing falsifies. Resources, honestly: RSA-2048 ≈ 4,000–6,000 logical qubits, ~10⁹–10¹⁰ Toffoli-class gates, hours of runtime (Gidney–Ekerå 2019; Gidney 2025's improvements cut it further) — a machine of the 2030s at the earliest on current roadmaps (Starling-class is 100–200 logical qubits). The cryptographic community's response is not panic but migration: NIST standardized post-quantum schemes in 2024 (51.9), and browsers/protocols are already shipping them. Understand the resource arithmetic — it is how you evaluate every "RSA is dead next year" headline.
51.3Shor and Elliptic Curves
Elliptic-curve cryptography (ECC) — the modern default (ECDSA, ECDH, most of Web3) — dies the same death, by the same algorithm: Shor's discrete-log version applies to any abelian group where the group operation is efficiently computable quantumly, and elliptic-curve groups qualify with smaller resource requirements than RSA (256-bit ECC ≈ 2,300 logical qubits — cheaper than RSA-2048). Consequence for migration planning: ECC assets are, if anything, more urgent than RSA ones. Bitcoin's case study: ~4M BTC sit at addresses whose public keys are exposed (P2PK and reused-nonce patterns), quantum-vulnerable to theft the moment signatures can be forged — and the community's migration debate is live. The general lesson: inventory where public keys are exposed; that inventory, not qubit counts, drives your migration schedule.
51.4Grover and Symmetric Cryptography
Symmetric crypto survives, minus a square root. Grover gives a generic 2^(n/2) key search for n-bit keys (with oracle-cost caveats that make even that expensive quantumly — the QRAM problem again, in its most benign form) and BHT collision-finding gives 2^(n/3) for hash collisions (2^(n/2) → 2^(n/3) — Grover-class, weaker). Concrete guidance: AES-128 → marginal (2⁶⁴ effective, with parallelization caveats that make real attacks worse than theoretical); AES-256 → comfortable (2¹²⁸); SHA-256 → fine; SHA-384+ for long-term hash signatures. The engineering conclusion: symmetric crypto's quantum response is a key-length refresh, already standard practice — which is why the entire drama of "post-quantum" is about public-key cryptography, and why "quantum breaks all encryption" is wrong in both directions.
51.5Quantum Key Distribution
The positive application: use quantum mechanics itself to distribute symmetric keys with security guaranteed by physics — eavesdropping disturbs the quantum states and is detected. QKD is real deployed technology (commercial systems, metropolitan networks, satellite experiments — China's Micius did intercontinental QKD in 2017), and it complements rather than replaces PQC: it addresses key exchange only, requires physical quantum channels, and carries its own engineering constraints (51.8). The correct mental model: QKD is physics-as-security-audit — an information-theoretic guarantee with an honest threat model (the devices!), while PQC is mathematics-as-security-assumption with no physics required. Modern security architecture uses both where each fits; neither is a silver bullet, and anyone selling either as one is your first red flag.
51.6BB84
The founding protocol (Bennett–Brassard 1984), and the best 30-minute deep-dive in applied quantum information. Mechanics: Alice sends qubits in randomly chosen bases (Z or X); Bob measures in random bases; they publicly compare bases (keep the matches), sacrificing a fraction to estimate the error rate; high error ⇒ eavesdropper (or noise) ⇒ abort; otherwise error-correct and privacy-amplify into a shared secret key. The security argument is pure quantum mechanics: measuring in the wrong basis disturbs the state (Part II's observables, weaponized); no-cloning forbids copying in transit. Implement BB84 between two processes on your laptop (simulating channel noise and an intercept-resend attack) — the exercise covers measurement statistics, sifting, and security thresholds in one evening, and it is the most fun experiment in Part XIII.
51.7E91
Ekert's 1991 entanglement-based protocol: distribute entangled pairs; both parties measure in randomly chosen bases; security is certified by Bell-inequality violation itself — if the correlations exceed the classical bound, no eavesdropper (or untrusted device) can be fully determining outcomes. This is device-independent QKD: security even against hardware you didn't build — the deepest idea in the field and the direct application of Part II's nonlocal-correlations section. Practical status: DI-QKD demonstrated in labs (2022, multiple groups) at extremely low rates; entanglement-distribution infrastructure (quantum repeaters, Ch. 44's sibling problems) is the bottleneck. E91 matters to you as the conceptual bridge: Bell tests → certification → security — the same chain quantum networks research (Ch. 79) is industrializing.
51.8Limitations of QKD
The honest ledger. Range: photon loss in fiber caps point-to-point distance (~100–500 km); quantum repeaters (entanglement swapping + quantum memories) remain lab-scale — the field's hardest open engineering problem. Rate: keys at kbps–Mbps, fine for session keys, not for bulk encryption (which stays AES, keyed by QKD). Cost and infrastructure: dedicated fiber or free-space links; no routing through the classical internet. Device security: early QKD hardware had side channels (detector blinding attacks — real demonstrated breaks); DI-QKD fixes this in theory and is experimental in practice. Authentication: QKD needs an authenticated classical channel to start — so it presumes (a little) classical crypto. Verdict: QKD is a niche tool with perfect-clearance use cases, not an internet replacement — and knowing that distinction is consulting-grade knowledge.
51.9Post-Quantum Cryptography
The actual response, standardized: NIST's 2024 selections — ML-KEM (Kyber, lattice-based key encapsulation — the TLS workhorse), ML-DSA (Dilithium, lattice signatures), SLH-DSA (SPHINCS+, hash-based signatures, conservative fallback), plus the FN-DSA/Falcon track. Properties to understand: security rests on lattice problems believed hard for quantum computers too (no Shor structure to exploit), keys/signatures are larger (Kyber: ~1 KB vs ECDH's 32 bytes — protocol engineering follows), and the schemes are classical — deployable today, no quantum hardware needed anywhere. The 2024–25 deployment wave is real: Chrome/Firefox/OpenSSH/Signal shipped hybrid PQC. Note the intellectual honesty of the field: PQC hedges against unknown quantum and unknown classical attacks on lattices — nothing is proven, everything is informed caution.
51.10Migration from Classical Cryptography
The engineering program, live now, and the best job market in security. Steps: inventory (every use of RSA/ECC — TLS, code signing, VPNs, HSMs, embedded devices, blockchain), classify by exposure (harvest-now-decrypt-later data ⇒ urgent; ephemeral integrity signatures ⇒ later), prioritize by crypto-agility (how fast can each system swap algorithms — the property NIST and NSA's CNSA 2.0 both mandate), deploy hybrids (X25519+Kyber — classical plus PQC, security = max of the two), test performance (handshake sizes, latency on constrained devices), and plan a decade of maintained agility — not a one-time flag-flip. Standards timeline: CNSA 2.0 requires PQC for national-security systems by ~2030–2033; the CA/Browser Forum is migrating root CAs now. For an engineer in any country: this migration doesn't care about your hardware access — it is pure software, standards, and systems work, and it is hiring.