Chapter 7: Quantum Cryptography and Post-Quantum Migration¶
Quantum computers threaten the mathematical foundations of RSA, ECC, and Diffie-Hellman. This chapter covers the specific quantum algorithms responsible, the NIST post-quantum standards published in 2024, and practical migration strategies.
The threat is asymmetric: quantum computers don’t break all cryptography, just the cryptography whose security rests on factoring or discrete logarithm problems. Symmetric ciphers and hash functions are weakened but not broken. Understanding this distinction is essential for scoping the migration effort — organizations that replace AES-256 with a lattice-based cipher have misread the threat model, while those that ignore the RSA and ECDH in their TLS certificates have underreacted.
7.1 Quantum Computing Threats¶
7.1.1 Shor’s Algorithm¶
Theorem 7.1 (Shor’s Algorithm, 1994)
A quantum computer can factor an \(n\)-bit integer in \(O(n^3)\) quantum gate operations and compute discrete logarithms in \(O(n^3)\) operations. Both run in polynomial time, breaking RSA, DH, ECDH, ECDSA, and DSA.
Shor’s algorithm works by reducing factoring to period-finding, then solving period-finding with a quantum Fourier transform. The period-finding step runs exponentially faster on a quantum computer than on a classical one because quantum superposition lets the circuit evaluate the function at all inputs simultaneously. This isn’t magic parallelism — measurement collapses the superposition, so the trick is designing the interference pattern so that the period (which divides into the factored answer) has high probability when measured. The algorithm requires a fault-tolerant quantum computer with roughly \(4{,}000\) logical qubits and millions of physical qubits to break RSA-2048; no such machine exists today, but the trajectory of error-correction research makes it a credible 10–15 year prospect.
| Algorithm | Broken by Shor | Recommended Replacement |
|---|---|---|
| RSA-2048 | Yes | ML-KEM / ML-DSA |
| ECDH (all curves) | Yes | ML-KEM (key exchange) |
| ECDSA / Ed25519 | Yes | ML-DSA / SLH-DSA |
| AES-128 | No (Grover: \(2^{64}\)) | AES-256 (sufficient) |
| AES-256 | No (Grover: \(2^{128}\)) | Unchanged |
| SHA-256 | No (Grover: \(2^{128}\)) | SHA-384 / SHA3-256 |
7.1.2 Grover’s Algorithm¶
Theorem 7.2 (Grover’s Algorithm, 1996)
A quantum computer can search an unstructured database of \(N\) items in \(O(\sqrt{N})\) quantum operations, vs. \(O(N)\) classically.
Impact on symmetric cryptography:
-
AES-128: brute force in \(O(2^{64})\) — double key length to AES-256
-
SHA-256: preimage resistance \(O(2^{128})\) — use SHA-256 or larger
-
HMAC: key length determines security — use HMAC with 256-bit keys
Grover’s algorithm is often described as “halving the bit security” of symmetric primitives, which is accurate but sometimes misunderstood. It doesn’t break AES-256 — \(2^{128}\) quantum oracle queries is still astronomically large. The practical implication is simply that any symmetric key or hash output that previously provided 128-bit classical security now provides 64-bit quantum security, which is too weak. AES-256 and SHA-256 already have the right key lengths for a post-quantum world; AES-128 and SHA-1 do not. No algorithm changes are required for symmetric cryptography, only parameter upgrades.
7.1.3 Harvest Now, Decrypt Later (HNDL)¶
HNDL Attack
Nation-state adversaries are recording encrypted traffic now, intending to decrypt it once cryptographically relevant quantum computers (CRQC) become available.
Timeline: Most estimates place CRQC at 5–15 years. Data with long secrecy requirements (state secrets, medical records, financial data) must be protected by PQC today.
Evidence: CISA, NSA, and NIST have confirmed this threat. NSA CNSA 2.0 (2022) mandates PQC transition for national security systems.
The HNDL threat is concrete, not theoretical. Traffic collection at internet exchange points and undersea cable landing stations is well within the capability of major intelligence agencies, and large-scale encrypted data archiving is operationally simple compared to the actual decryption problem. The implication for data classification is uncomfortable: any TLS session key negotiated with ECDH today is potentially stored somewhere and will be decryptable in a decade. This means the window for protecting sensitive data that must remain confidential for ten or more years has already closed for classical key exchange. Organizations with genuinely long-lived confidentiality requirements — law firms, healthcare systems, government contractors — should already be deploying hybrid PQC key exchange in their TLS stacks.
7.2 NIST Post-Quantum Cryptography Standards (2024)¶
7.2.1 ML-KEM: FIPS 203 (Key Encapsulation)¶
Based on CRYSTALS-Kyber, Module Learning With Errors (MLWE) problem:
Definition 7.1 (Learning With Errors (LWE))
Given many samples \((A_i, b_i)\) where \(A_i \leftarrow_\$ \mathbb{Z}_q^n\) and \(b_i = A_i^T s + e_i\) for secret \(s\) and small error \(e_i\), find \(s\). This is believed hard even for quantum computers.
The noise term \(e_i\) is what makes LWE hard. Without noise, solving the system is straightforward Gaussian elimination over \(\mathbb{Z}_q\). With small noise, the equations don’t have exact solutions and the best known classical or quantum algorithms require exponential time in \(n\). The “module” variant operates over polynomial rings rather than raw integer vectors, which allows more efficient key and ciphertext sizes while preserving the hardness reduction. The practical implication of LWE-based cryptography is that key sizes are much larger than classical schemes: ML-KEM-768 public keys are 1,184 bytes versus 32 bytes for X25519, which matters for constrained devices and protocol designs that assume short keys.
ML-KEM key encapsulation:
-
KeyGen: Generate polynomial ring matrices \((A, s, e)\); public key \(pk = (A, As + e)\)
-
Encaps:\((pk) \to (K, c)\): Encrypt random shared secret using public key
-
Decaps:\((sk, c) \to K\): Recover shared secret using secret key
| Parameter Set | Security | Public Key | Ciphertext |
|---|---|---|---|
| ML-KEM-512 | 128 bits (NIST Level 1) | 800 bytes | 768 bytes |
| ML-KEM-768 | 192 bits (NIST Level 3) | 1184 bytes | 1088 bytes |
| ML-KEM-1024 | 256 bits (NIST Level 5) | 1568 bytes | 1568 bytes |
import oqs
# Key Encapsulation with ML-KEM-768
kem_alg = 'ML-KEM-768'
with oqs.KeyEncapsulation(kem_alg) as recipient:
public_key = recipient.generate_keypair()
# Sender encapsulates shared secret
with oqs.KeyEncapsulation(kem_alg) as sender:
ciphertext, shared_secret_sender = sender.encap_secret(public_key)
# Recipient decapsulates
shared_secret_recipient = recipient.decap_secret(ciphertext)
assert shared_secret_sender == shared_secret_recipient
print(f"Shared secret: {shared_secret_sender.hex()}") # 32 bytes
7.2.2 ML-DSA: FIPS 204 (Digital Signatures)¶
Based on CRYSTALS-Dilithium, MLWE + MSIS (Module Short Integer Solution):
import oqs
sig_alg = 'ML-DSA-65' # 192-bit security
with oqs.Signature(sig_alg) as signer:
public_key = signer.generate_keypair()
message = b"Document requiring PQC signature"
signature = signer.sign(message) # ~3293 bytes for ML-DSA-65
with oqs.Signature(sig_alg) as verifier:
is_valid = verifier.verify(message, signature, public_key)
print(f"Signature valid: {is_valid}") # True
Signature size comparison:
| Algorithm | Signature Size | Security Level |
|---|---|---|
| ECDSA P-256 | 64 bytes | 128 bits (broken by quantum) |
| Ed25519 | 64 bytes | 128 bits (broken by quantum) |
| RSA-2048 PSS | 256 bytes | 112 bits (broken by quantum) |
| ML-DSA-44 | 2420 bytes | 128 bits (quantum resistant) |
| ML-DSA-65 | 3293 bytes | 192 bits (quantum resistant) |
| SLH-DSA-128s | 7856 bytes | 128 bits (hash-based) |
7.2.3 SLH-DSA: FIPS 205 (Hash-Based Signatures)¶
Definition 7.2 (SLH-DSA (SPHINCS+))
SLH-DSA builds signatures from hash functions only — no algebraic structure. Security relies solely on hash function properties (preimage resistance, collision resistance).
Construction: Hypertree of Merkle trees + FORS (Forest of Random Subsets). Stateless — no need to track used keys (unlike XMSS, LMS).
The natural use case is Root CA signatures and firmware signing where the strongest possible conservatism is warranted, since security depends only on the hash function, not on unproven lattice assumptions. If lattice cryptography turns out to have an unexpected weakness (as happened with multivariate schemes that NIST removed from consideration), SLH-DSA signatures remain valid because their security reduces solely to hash function collision resistance. The trade-off is size: a 7,856-byte signature is impractical for high-frequency signing (TLS certificates, code signing at scale) but acceptable for long-lived root CA certificates that are rarely re-signed. Organizations planning their PQC migration should plan to use ML-DSA for most signature applications and reserve SLH-DSA for the highest-value, lowest-frequency signatures.
7.3 Hybrid Cryptography for Migration¶
During the transition period, hybrid schemes combine classical and post-quantum components. If either component holds, the combined secret holds. This is the right default posture for most organizations right now: it provides immediate protection against HNDL attacks (because an attacker who archives traffic today can’t use a future quantum computer to recover the PQC component) while preserving protection against a hypothetical break in the lattice assumption (because the classical ECDH component still holds). Hybrid deployment doesn’t require abandoning existing PKI — it adds an additional key share to the TLS handshake alongside the existing ECDH share, which is backward compatible in TLS 1.3’s key share extension.
Definition 7.3 (Hybrid Key Exchange)
Combine classical (X25519) and PQC (ML-KEM-768) key shares:
Security holds if either the classical or PQC component is secure.
| Protocol | Hybrid Group | Status |
|---|---|---|
| TLS 1.3 | X25519 + ML-KEM-768 | Chrome 124+, Firefox (experimental) |
| SSH | curve25519 + ML-KEM-768 | OpenSSH 9.9+ |
| IKEv2 (IPsec) | ECDH + ML-KEM | RFC draft; limited support |
7.4 Quantum Key Distribution (QKD)¶
Definition 7.4 (BB84 Protocol)
The quantum channel sends qubits in one of four states: \(\{|0\rangle, |1\rangle, |+\rangle, |-\rangle\}\) (rectilinear and diagonal bases). Eavesdropping disturbs the quantum state (no-cloning theorem) and is therefore detectable.
The shared key is derived from matching-basis measurements; an error rate above threshold causes the protocol to abort.
| QKD Limitation | Notes |
|---|---|
| Distance: \(\sim 100\) km without repeater | Quantum repeaters in research |
| Requires dedicated fiber or free-space link | No internet-scale deployment |
| Expensive: \(>\$100\)K per link | Not cost-effective for most organizations |
| Authentication still needed | Requires classical authenticated channel |
Consensus: The NIST PQC standards are the practical path forward; QKD is niche (government point-to-point links).
QKD advocates point out that its security is information-theoretic rather than computational: no amount of computing power breaks BB84 because the eavesdropping detection is based on quantum mechanics, not hardness assumptions. This is true in principle. The practical objection is that the authentication layer required to run QKD still uses classical cryptography, so QKD’s theoretical purity is already compromised. More fundamentally, the distance and infrastructure constraints mean QKD will never scale to the internet: protecting a single 500-km link requires a chain of trusted repeater nodes, each of which is a classical attack surface. PQC, by contrast, runs over existing infrastructure with a software update.
7.5 Migration Strategy¶
-
Inventory: Discover all RSA/ECC usage (certificates, code signing, VPN, SSH)
-
Prioritize: Long-lived data first (HNDL risk); then authentication; then ephemeral
-
Hybrid deployment: Add ML-KEM alongside ECDH in TLS/SSH now (double protection)
-
Crypto agility: Refactor to algorithm-negotiation architecture
-
HSM updates: Firmware updates for ML-KEM/ML-DSA support
-
Certificate re-issuance: Plan for ML-DSA certificates as CA support grows
-
Timeline: NIST/NSA mandate: classical algorithm retirement by 2030–2035
Exercises¶
Exercise 7.1
Using the oqs Python library, implement a complete hybrid TLS-like key exchange: X25519 + ML-KEM-768. Derive a 256-bit session key using HKDF from the combined shared secrets.
Exercise 7.2
An organization stores encrypted medical records using RSA-2048 key wrapping. Estimate how many years of data are at risk from HNDL attacks if a CRQC emerges in 10 years. What is the immediate remediation?
Exercise 7.3
Compare the bandwidth impact of migrating TLS certificates from ECDSA P-256 to ML-DSA-65: calculate the increase in certificate size, the impact on TLS handshake size, and the latency overhead for a mobile user on a 50 Mbps connection.
Exercise 7.4
Explain why AES-256 is considered quantum-safe while RSA-2048 is not. Specifically, why does Grover’s algorithm require \(2^{128}\) queries to break AES-256 but Shor’s algorithm can break RSA-2048 efficiently?
Exercise 7.5 (NSA CNSA 2.0 Compliance)
The NSA CNSA 2.0 Suite requires PQC for all National Security Systems by 2030. List the specific algorithm transitions required for: (a) key agreement in classified VPNs, (b) software signing for weapons systems, (c) encrypted storage in classified networks. Map each to FIPS standards.