Notebook 00a — Why post-quantum cryptography?

Today’s encryption would unravel the day a sufficiently large quantum computer exists. This book is about one of the replacements — ML-KEM — and what it takes to build it from scratch.

The quantum threat in one slide

• Shor’s algorithm (1994): on a sufficiently large quantum computer, solves integer factorization and discrete logarithm in polynomial time. That is exactly what RSA, Diffie-Hellman, and elliptic-curve crypto rely on. So Shor, if run at scale, breaks nearly all current public-key crypto.

• Grover’s algorithm: quadratic speedup for unstructured search. This weakens symmetric crypto (AES-128 → ~64-bit quantum security) but doesn’t break it — doubling key size is enough (AES-256 stays strong).

• The upshot: symmetric and hash primitives are mostly fine (with bigger keys); asymmetric crypto must be replaced entirely.

import matplotlib.pyplot as plt
primitives = [
    ("AES-128",      "symmetric",  "doubles to 64-bit PQ", "keep (use AES-256)"),
    ("AES-256",      "symmetric",  "128-bit PQ",           "keep"),
    ("SHA-256",      "hash",       "128-bit PQ",           "keep"),
    ("RSA-2048",     "asymmetric", "broken by Shor",       "REPLACE"),
    ("ECDH (P-256)", "asymmetric", "broken by Shor",       "REPLACE"),
    ("ECDSA",        "asymmetric", "broken by Shor",       "REPLACE"),
]
fig, ax = plt.subplots(figsize=(9, 3.5))
for i, (name, kind, q_impact, action) in enumerate(primitives):
    color = "#e74c3c" if "REPLACE" in action else "#27ae60"
    ax.barh(i, 1, color=color, alpha=0.7)
    ax.text(0.02, i, f"{name:14}  —  {q_impact}", va="center", fontsize=10, family="monospace")
    ax.text(1.02, i, action, va="center", fontsize=10, family="monospace")
ax.set_yticks([]); ax.set_xticks([]); ax.set_xlim(0, 1.7)
ax.set_title("Post-quantum impact by primitive type", fontsize=12)
ax.invert_yaxis()
plt.tight_layout(); plt.show()

“Harvest now, decrypt later”

An adversary can record encrypted traffic today (even if they can’t read it) and decrypt it years later when quantum computers mature. Data with long confidentiality horizons — government secrets, medical records, personal chats, IP — is already at risk. This is why PQC migration can’t wait for Q-Day.

Where we are (2024–2026)

• 2016: NIST opens the PQC standardization competition.

• 2022: four finalists selected (Kyber as the primary KEM; Dilithium, Falcon, SPHINCS+ for signatures).

• 2024 August: NIST publishes FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), FIPS 205 (SLH-DSA).

• 2024 onward: deployed in production by Apple iMessage (PQ3), Signal (PQXDH), Chrome (X25519Kyber768), Cloudflare, AWS KMS.

• Q-Day: no one knows. Estimates range from “10 years” to “never at scale.” The migration is happening regardless, because of harvest-now-decrypt-later.

What this book covers

We implement ML-KEM — the key encapsulation mechanism chosen by NIST as the main post-quantum replacement for Diffie-Hellman-style key exchange. It is one piece of the puzzle: digital signatures (ML-DSA, SLH-DSA) are covered briefly in Part 3.

Before you proceed

If you already know what RSA does, what a KEM is, and are comfortable with modular arithmetic, skip Part 1 and go straight to 01_lattice_intro. Otherwise, continue with 00b_classical_crypto_recap.