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. This is 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, and your progress syncs across the web and the CoddyKit app. The Cryptology Academy course includes 4 lessons in total.
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.
Learn Cryptology Academy with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 67
- Lessons
- 261
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. 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. The Cryptology Academy course includes 4 lessons in total.
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, so you can start here or from the beginning and move at your own pace. This is lesson 2 of 4.
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