CRYSTALS-Kyber (ML-KEM)

Introduction

In 2024, NIST finalized ML-KEM (Module-Lattice-Based Key Encapsulation Mechanism, FIPS 203) as the primary standard for post-quantum key exchange — built directly from CRYSTALS-Kyber, the algorithm that won NIST’s multi-year PQC competition. Where FrodoKEM deliberately avoids algebraic structure to stay conservative, Kyber embraces it: it works over a polynomial ring, which lets one “multiplication” implicitly perform hundreds of scalar multiplications through convolution. That structure is what makes Kyber fast enough to be a practical drop-in replacement for RSA and ECDH key exchange in TLS, SSH, and beyond — and it’s already shipping by default in Chrome, Firefox, and OpenSSH.

Table of Contents

• Ring-LWE and Module-LWE
• Key Generation
• Encryption and Decryption
• A Worked Example
• Why It’s Called “Module” and Not Just “Ring”
• Kyber vs. FrodoKEM
• FAQ
• References

Ring-LWE and Module-LWE

Plain LWE (used by FrodoKEM) works with matrices of individual integers. Ring-LWE replaces each integer with a polynomial in a ring like ℤ_q[x]/(xⁿ+1), and replaces integer multiplication with polynomial multiplication modulo xⁿ+1 — a single ring multiplication does the work of an entire n×n integer matrix multiplication, but can be computed in O(n log n) time using the Number Theoretic Transform instead of O(n²). Kyber goes one step further and uses Module-LWE: instead of one big polynomial ring element, the secret and public key are short vectors of ring elements (a “module” over the ring), which gives extra flexibility to scale security levels (Kyber-512/768/1024) just by changing the vector length k, without changing the ring dimension n.

Key Generation

1. Generate a public k×k matrix A of polynomials in ℤ_q[x]/(xⁿ+1), with coefficients uniformly random mod q.
2. Sample a small secret vector s of k polynomials (coefficients drawn from a narrow distribution centered at 0).
3. Sample a small error vector e of k polynomials, same distribution.
4. Compute the public key: t = A·s + e (mod q) — a vector of k noisy polynomials.
5. The private key is s.

Encryption and Decryption

To encrypt message bits (encoded as a polynomial with coefficients 0 or q/2):

1. Sample a small vector r and small errors e1 (vector) and e2 (single polynomial) — the encryptor’s own secret randomness.
2. Compute u = Aᵀ·r + e1 (mod q).
3. Compute v = t·r + e2 + encode(bits) (mod q) — a dot product of two polynomial vectors, yielding a single polynomial.
4. The ciphertext is (u, v).

To decrypt, using secret s:

recovered = v − s·u (mod q)

Expanding: v − s·u = (t·r + e2 + encode) − s·(Aᵀ·r + e1). Since t = A·s + e, the bulk term t·r = (A·s + e)·r matches s·(Aᵀ·r) exactly (transposing and reordering a matrix-vector product over a commutative ring leaves the products unchanged), so it cancels completely — leaving only e·r − s·e1 + e2 + encode(bits). All three noise terms are small polynomials; the encoded bits are 0 or q/2. Rounding each coefficient to the nearer of {0, q/2} strips the noise and recovers the bits.

Interactive Visualizer

Real Kyber uses ring degree n=256 with q=3329, and module rank k=2, 3, or 4 depending on security level — parameters chosen so polynomial multiplication runs efficiently via the Number Theoretic Transform and the security margin against lattice-reduction attacks is large. The visualizer above runs the identical structure — a public matrix of ring elements, module-vector arithmetic, and the same cancellation-then-rounding decryption — at n=4, k=2, q=97, small enough to read every coefficient directly.

A Worked Example

Using the visualizer’s toy parameters:

1. A random 2×2 matrix A of degree-4 polynomials and small secret/error vectors s, e produce the public key t = A·s + e mod 97.
2. To send 4 bits, the sender samples its own small r, e1, e2, computes u = Aᵀ·r + e1 and v = t·r + e2 + encode(bits).
3. The recipient computes v − s·u mod 97 and rounds each of the 4 coefficients to the nearer of 0 or 48 (⌊97/2⌋).
4. Because the accumulated noise from four small-coefficient polynomial multiplications stays under the rounding threshold, the bits return exactly.

Why It’s Called “Module” and Not Just “Ring”

A pure Ring-LWE scheme would use a single polynomial as the secret (k=1) — fast, but with fewer knobs to tune security independently of the ring dimension. Kyber’s module structure (k independent polynomials bundled into a vector) lets NIST offer three security levels (Kyber-512 ≈ AES-128, Kyber-768 ≈ AES-192, Kyber-1024 ≈ AES-256) by adjusting k=2, 3, 4 while keeping the same efficient n=256 ring — exactly analogous to how the visualizer’s k=2 module builds on the same n=4 ring arithmetic used underneath.

Kyber vs. FrodoKEM

Both rest on the hardness of noisy linear algebra; Kyber trades a small, unproven structural assumption for an order-of-magnitude performance and bandwidth win, which is why it became the default.

FAQ

What does “ML-KEM” stand for, and how does it relate to Kyber?

ML-KEM (Module-Lattice-Based Key Encapsulation Mechanism) is the official NIST FIPS 203 name for the standardized algorithm derived from CRYSTALS-Kyber. “Kyber” is still the common name for the underlying design from the NIST competition.

Is Kyber a full public-key encryption scheme like RSA?

It’s specifically a KEM — designed to securely agree on a random shared secret (used afterward as a symmetric key), not to directly encrypt arbitrary messages the way RSA-OAEP does. The visualizer encrypts a chosen bit string instead of a random key purely to make the mechanism visible.

Why does Kyber need a Number Theoretic Transform?

Multiplying two degree-256 polynomials the schoolbook way costs O(n²) ≈ 65,000 multiplications; the NTT (a finite-field analog of the FFT) reduces this to O(n log n) ≈ 2,000, which is what makes Kyber fast enough for routine TLS handshakes at internet scale.

Has Kyber already been deployed?

Yes — Chrome, Firefox, and Cloudflare have deployed hybrid Kyber+X25519 key exchange in TLS 1.3 since 2023-2024, and OpenSSH added ML-KEM support, making it one of the fastest-adopted cryptographic standards in recent history, driven by the urgency of the “harvest now, decrypt later” quantum threat.

References

1. Bos, J., Ducas, L., Kiltz, E., et al. “CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM.” IEEE EuroS&P, 2018.

2. NIST. “Module-Lattice-Based Key-Encapsulation Mechanism Standard.” FIPS 203, 2024.

3. CRYSTALS Team. “Kyber.” Available at: https://pq-crystals.org/kyber/

4. NIST. “Post-Quantum Cryptography Standardization.” Available at: https://csrc.nist.gov/projects/post-quantum-cryptography