Notebook 09 — What we built

Notebook 09 — What we built#

Across nine notebooks we built toy LWE, broke it at small parameters, learned why the polynomial ring Z_q[x]/(x^n+1) plus NTT makes ML-KEM fast, and implemented FIPS 203 ML-KEM (512/768/1024) with passing roundtrip and size tests.

The one-paragraph test#

Try writing, without looking back, a five-sentence explanation of ML-KEM that covers:

  • What problem is hard (LWE / Module-LWE)

  • Why the ring structure helps (NTT, compact keys)

  • What K-PKE does (encrypt to a public (A, t = A s + e))

  • Why the FO transform is there (upgrade from CPA to CCA security)

  • What a shared secret is derived from (a hash of the encapsulated message)

If you can’t cover one of those, that’s the notebook to re-read.

Gaps vs. production#

  • Constant-time arithmetic: real implementations avoid secret-dependent branches and memory access. Ours uses Python ints and numpy which are not constant-time.

  • Side-channel resistance: countermeasures against cache timing, power, EM side channels. Out of scope here.

  • NIST Known-Answer Tests (KATs): we did not verify bit-for-bit equivalence with FIPS 203 test vectors (different byte-packing subtleties could make us incompatible on the wire). Our tests show self-consistency, not interoperability.

  • Safe memory clearing: Python has no portable way to zero memory reliably after use.

  • Audited dependencies: we rely on hashlib (OK) and numpy (for speed only).

Further reading#

  • FIPS 203 — ML-KEM Standard (NIST, 2024). The authoritative spec.

  • Regev 2005 — On Lattices, Learning With Errors, Random Linear Codes, and Cryptography (STOC’05). The original LWE paper.

  • Peikert 2016 — A Decade of Lattice Cryptography. Comprehensive survey.

  • LWE Estimator (Albrecht, Player, Scott) — github.com/malb/lattice-estimator. The community-standard tool for assessing concrete LWE hardness.

  • kyber-py (Giacon) — a clean reference Python implementation of Kyber/ML-KEM if you want to compare.

Where to go next#

  • ML-DSA (Dilithium, FIPS 204) — lattice-based signatures using the same Module-LWE/SIS foundation.

  • SLH-DSA (SPHINCS+, FIPS 205) — stateless hash-based signatures. Different math: uses only hash functions; much larger signatures but minimal assumptions.

  • BIKE / HQC / Classic McEliece — code-based KEMs. NIST’s alternate track.

  • Hybrid in practice — read draft-ietf-tls-hybrid-design and watch the upcoming TLS 1.3 hybrid rollout (Chrome has deployed X25519+Kyber since 2023).

Hands-on capstone: pq-messenger — a Signal-style end-to-end encrypted CLI that uses the pqc_edu ML-KEM you just built, in a hybrid X25519 + ML-KEM-768 X3DH handshake plus a full Double Ratchet (symmetric chain + DH rotation, since v0.2). Two real OS processes, a shared file queue, every byte visible.