Notebook 11 — Deployment, FAQ, glossary

Notebook 11 — Deployment, FAQ, glossary#

Where PQC is actually running in 2026, common misconceptions, and a vocabulary reference.

Part A — Real-world deployment status (2026)#

Web / TLS#

  • Chrome, Edge: hybrid X25519Kyber768 (draft-tls-westerbaan) enabled by default since Chrome 124 (April 2024). Now also sees X25519MLKEM768 (FIPS 203 version) rolling out in 2025.

  • Cloudflare: edge TLS 1.3 with X25519MLKEM768 available since late 2024. Roughly ~15% of connections use PQ hybrid today.

  • AWS KMS, Amazon s2n-tls, Google ALTS: all have hybrid deployments; internal Google traffic has been PQ-hybrid for several years.

Messaging#

  • Apple iMessage PQ3 (Feb 2024): first widely deployed PQ key agreement in a consumer product. Uses a KEM (their own construction, evolving to ML-KEM).

  • Signal PQXDH (Sep 2023): post-quantum extended triple Diffie-Hellman, uses hybrid CRYSTALS-Kyber.

  • WhatsApp, Telegram: announced migration plans, status varies.

Firmware / code signing#

  • Microsoft, Google Android: rolling out ML-DSA for certificate authorities and firmware signing.

  • FIDO2 / WebAuthn: PQ extensions being standardized (2025).

Part B — Migration strategy#

Hybrid first, PQ-only later. Every production deployment in 2024–2026 is hybrid: classical (X25519 or ECDSA) + post-quantum (ML-KEM or ML-DSA) in parallel. The shared secret or signature is valid only if both halves are. This buys:

  • Safety against surprise cryptanalysis on the new PQ schemes.

  • Backward compatibility — if the peer doesn’t understand PQ, negotiate down to classical.

Crypto agility. Applications that hard-code RSA/ECDSA are painful to migrate. The lesson: wrap key/signature types behind an algorithm identifier so swapping is a config change, not a code rewrite.

Harvest-now-decrypt-later (HNDL) priority list:

  1. Long-horizon confidential data (medical records, legal docs, government). Migrate now.

  2. Short-lived session keys for ephemeral traffic (web browsing). Less urgent.

  3. Identity and signing keys (certificates): plan a 5–10 year transition.

Part C — FAQ and common misconceptions#

Q: “Grover’s algorithm breaks AES.”
A: No. Grover gives a quadratic speedup. AES-128 drops from 128-bit security to roughly 64-bit quantum security; AES-256 keeps ~128-bit quantum security. Double the key and move on. Symmetric crypto is fine.

Q: “PQC is slow and huge.”
A: Mixed. ML-KEM-768 does encapsulation in ~50 μs in optimized C — faster than RSA-2048. Ciphertext is 1088 bytes (vs 32 for X25519) — noticeably larger but not painful. ML-DSA signatures are ~3 KB vs 64 B for ECDSA — that’s the real size cost. SPHINCS+ signatures can be 40 KB — that’s expensive and why people prefer ML-DSA when possible.

Q: “Quantum computers are 30 years away, why rush?”
A: Three reasons: (1) nobody knows — timelines are guesses. (2) Harvest-now-decrypt-later means attacks on today’s data can happen at Q-Day. (3) Migrations at internet scale take 5–10 years even when we know what to do. Starting in 2024 gives us a buffer.

Q: “If quantum breaks RSA, won’t it also break ML-KEM eventually?”
A: Possibly. Lattice-based cryptography has had ~30 years of study; no polynomial quantum or classical attack has been found, and there are worst-case-to-average-case reductions (solving LWE on average is at least as hard as solving lattice problems in the worst case — an unusually strong guarantee). That said, “no attack yet” is not “no attack forever.” This is why we use hybrid deployments and also standardize SLH-DSA as a backup based only on hash-function security.

Q: “Should I replace my symmetric encryption too?”
A: No. Keep AES-GCM / ChaCha20-Poly1305. Just make sure your asymmetric key establishment is post-quantum.

Q: “Why is ML-KEM’s public key 800 bytes but ECDH’s is 32?”
A: Lattice KEMs encode a k×n vector of coefficients in Z_q. For ML-KEM-512: k=2, n=256, each coefficient 12 bits → 2·256·12/8 = 768 bytes, plus a 32-byte seed. ECDH sends a single curve point (32 bytes). This is a structural cost of lattice schemes — no known way to get dramatically smaller.

Part D — Glossary (quick reference)#

Term

Meaning

BDD

Bounded Distance Decoding. CVP when the target is guaranteed close to the lattice. LWE reduces to BDD.

CBD

Centered Binomial Distribution. ML-KEM’s way of sampling small noise.

CVP

Closest Vector Problem. Given a target, find the nearest lattice point.

Encapsulation / Decapsulation

KEM operations. Encaps produces (K, ct); Decaps recovers K from ct and the private key.

FIPS 203 / 204 / 205

NIST standards for ML-KEM, ML-DSA, SLH-DSA.

FO transform

Fujisaki-Okamoto. Turns an IND-CPA PKE into an IND-CCA2 KEM.

Grover’s algorithm

Quantum search. Quadratic speedup — halves effective symmetric security.

Hybrid

Running two KEMs (or signatures) in parallel — e.g., X25519 + ML-KEM.

IND-CCA2

Indistinguishability under adaptive chosen-ciphertext attack. The target for KEMs.

IND-CPA

Indistinguishability under chosen-plaintext attack. What K-PKE inside ML-KEM achieves alone.

KAT

Known Answer Test. NIST-published test vectors for byte-exact compliance.

KEM

Key Encapsulation Mechanism. Public-key protocol producing a shared secret.

K-PKE

The IND-CPA public-key encryption scheme inside ML-KEM.

Lattice

{B·z : z in Z^d} — discrete regular grid of points in space.

LWE

Learning With Errors. Given noisy linear samples (a, <a,s> + e), find s.

ML-DSA

Module-Lattice Digital Signature Algorithm. FIPS 204. Dilithium rebranded.

ML-KEM

Module-Lattice KEM. FIPS 203. Kyber rebranded.

Module-LWE (MLWE)

LWE over vectors of polynomials. ML-KEM’s hardness assumption.

NTT

Number-Theoretic Transform. FFT over Z_q; makes polynomial multiplication O(n log n).

PKE

Public-Key Encryption. Encrypt with public key, decrypt with private.

PRF

Pseudo-Random Function. Keyed, output indistinguishable from random.

PRNG

Pseudo-Random Number Generator.

PQC

Post-Quantum Cryptography. Schemes conjectured safe against quantum computers.

Q-Day

The day a cryptographically relevant quantum computer exists. Date unknown.

Ring-LWE (RLWE)

LWE over a single polynomial ring. Predecessor to MLWE.

R_q

Z_q[x] / (x^n + 1). The polynomial ring used by ML-KEM (q=3329, n=256).

Shor’s algorithm

Quantum polynomial-time solution to factoring and discrete log. Breaks RSA/ECC.

SIS

Short Integer Solution. Sibling hardness assumption to LWE — used by ML-DSA.

SLH-DSA

Stateless Hash-Based DSA. FIPS 205. SPHINCS+ rebranded.

SVP

Shortest Vector Problem. Find the shortest nonzero vector in a lattice.

XOF

Extendable-Output Function. Hash with variable-length output. SHAKE-128/256.

Further reading#

  • FIPS 203 — the ML-KEM standard (NIST 2024). The authoritative source.

  • Peikert, A Decade of Lattice Cryptography (2016) — survey-level.

  • Albrecht, Player, Scott, On the concrete hardness of Learning With Errors — the LWE estimator.

  • Bernstein & Lange, Post-quantum cryptography (Nature Reviews, 2017) — friendly overview.

  • PQCrypto conference — annual academic venue.

  • pq-crystals.org — Kyber/Dilithium team’s site with reference code.

  • NIST PQC project page — archive of all candidates, attacks, comments.

Thank you for reading#

You went from “what is a lattice?” to a working ML-KEM implementation, with tests, benchmarks, and a hybrid key exchange. You now have an operational understanding of the crypto that will replace Diffie-Hellman on the internet in the next few years.

If you found bugs, typos, or unclear explanations, please open an issue at github.com/hulryung/ml-kem-notebooks.