CRYSTALS-Kyber: Lattice-Based KEM
Walk through Module-LWE key encapsulation and parameter sets.
CRYSTALS-Kyber: Lattice-Based KEM is a free Cryptology Academy lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Cryptology Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why Kyber?
CRYSTALS-Kyber (renamed ML-KEM by NIST in FIPS 203) is a Key Encapsulation Mechanism (KEM) based on Module-LWE. It replaces RSA and ECDH for key exchange, providing quantum resistance at practical performance levels.
KEM vs Key Agreement
A KEM encapsulates a shared secret: the sender generates a random key K, encrypts it with the recipient's public key (encapsulate), producing a ciphertext C. The recipient decapsulates C with their private key to recover K. No interactive key exchange needed.
Module-LWE Basis
Kyber uses Module-LWE over the ring R_q = Z_q[x]/(x^256+1) with q=3329. Dimension k=2 (Kyber-512), k=3 (Kyber-768), k=4 (Kyber-1024). Security level: ~128, ~192, ~256 bits respectively. k=3 (Kyber-768) is the recommended default.
Key Generation
Generate matrix A ∈ R_q^{k×k} from seed ρ (expandable). Sample secret s and noise e from a centered binomial distribution (small coefficients). Public key: (ρ, t=As+e). Private key: s. The noise e is small but prevents recovery of s from the public key.
Encapsulation
To send a shared secret to the holder of public key (ρ, t): sample r, e1, e2 from noise distribution. Compute u = A^T r + e1, v = t^T r + e2 + round(q/2)*m where m is a random 256-bit message. Shared secret K = KDF(m). Ciphertext = (u, v).
Decapsulation
With private key s: compute m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). The noise terms cancel approximately, leaving m'≈m. Compute K = KDF(m'). Decapsulation failure probability: < 2^{-139}.
Key and Ciphertext Sizes
Kyber-768: public key 1184 bytes, private key 2400 bytes, ciphertext 1088 bytes, shared secret 32 bytes. Compare to ECDH-P256: 65 bytes public key, 32 bytes ciphertext. Kyber is ~15x larger but quantum-safe. Still fast: encap+decap < 1 ms on modern CPUs.
NTT Optimization
Polynomial multiplication in R_q = Z_q[x]/(x^256+1) uses Number Theoretic Transform (NTT) — the modular arithmetic analog of FFT. NTT reduces polynomial multiplication from O(n^2) to O(n log n). q=3329 chosen to have good NTT properties for n=256.
Hybrid Key Exchange
During PQC migration, use hybrid key exchange: combine ECDH and Kyber. Shared secret = KDF(ECDH_output || Kyber_output). Security requires breaking both: classical adversaries break neither; quantum adversaries break ECDH but not Kyber. TLS 1.3 drafts (IETF RFC 8446) support hybrid KEMs.
Side-Channel Considerations
Kyber decapsulation is not constant-time in naive implementations — the rejection sampling step leaks timing. Reference implementation uses constant-time NTT and compressed ciphertext comparison. Use the NIST submission's reference code or audited library implementations.
Deployment Status
NIST published FIPS 203 (ML-KEM) in August 2024. Chrome added Kyber support in TLS 1.3 in 2023. Cloudflare, Google, and AWS are deploying hybrid ECDH+Kyber. OpenSSL 3.x added ML-KEM support. LibSSH and WireGuard implementations are in progress.
Quick Check
What NIST standard document standardizes CRYSTALS-Kyber?
Recap
Kyber (ML-KEM) is a Module-LWE based KEM replacing ECDH. Key sizes ~1 KB; fast NTT arithmetic; quantum-resistant. Deploy as hybrid with ECDH during migration. Standardized as FIPS 203. Next: CRYSTALS-Dilithium and Falcon signature schemes.
Frequently asked questions
Is the “CRYSTALS-Kyber: Lattice-Based KEM” lesson free?
Yes — the full text of “CRYSTALS-Kyber: Lattice-Based KEM” is free to read here on the web, and the Cryptology Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Cryptology Academy course, upgrade to CoddyKit PRO.
What will I learn in “CRYSTALS-Kyber: Lattice-Based KEM”?
Walk through Module-LWE key encapsulation and parameter sets. You practise Cryptology Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Cryptology Academy?
No prior experience is required. Cryptology Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “CRYSTALS-Kyber: Lattice-Based KEM” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Cryptology Academy lesson?
Yes. Every Cryptology Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Shor's & Grover's Algorithms Explained
- CRYSTALS-Kyber: Lattice-Based KEM
- CRYSTALS-Dilithium & Falcon Signatures
- Migration to PQC: Hybrid Approaches