CRYSTALS-Kyber (ML-KEM)

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. 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
• Python Implementation
• Limitations
• 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). This 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). These are 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. These parameters are chosen so polynomial multiplication runs efficiently via the Number Theoretic Transform, and so the security margin against lattice-reduction attacks stays 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.

Python Implementation

This mirrors the visualizer’s own toy parameters described above (n=4, k=2, q=97): the same module-vector matrix arithmetic, the same cancellation-then-rounding decryption, just genuinely computed in Python rather than JavaScript:

import random

n, k, q = 4, 2, 97

def poly_mul(a, b):
    """Multiplication mod (x^n + 1): wrapping past degree n flips the sign."""
    result = [0] * n
    for i in range(n):
        for j in range(n):
            idx, sign = (i + j, 1) if i + j < n else (i + j - n, -1)
            result[idx] = (result[idx] + sign * a[i] * b[j]) % q
    return result

def poly_add(a, b):
    return [(x + y) % q for x, y in zip(a, b)]

def poly_sub(a, b):
    return [(x - y) % q for x, y in zip(a, b)]

def small_poly():
    return [random.choice([-1, 0, 0, 1]) for _ in range(n)]

def small_vec():
    return [small_poly() for _ in range(k)]

def mat_vec_mul(A, v):
    result = [[0] * n for _ in range(k)]
    for i in range(k):
        for j in range(k):
            result[i] = poly_add(result[i], poly_mul(A[i][j], v[j]))
    return result

def mat_T_vec_mul(A, v):
    result = [[0] * n for _ in range(k)]
    for j in range(k):
        for i in range(k):
            result[j] = poly_add(result[j], poly_mul(A[i][j], v[i]))
    return result

def vec_dot(a, b):
    result = [0] * n
    for i in range(k):
        result = poly_add(result, poly_mul(a[i], b[i]))
    return result

def encode(bits):
    return [(q // 2) if bit else 0 for bit in bits]

def decode(poly):
    bits = []
    for c in poly:
        c %= q
        bits.append(0 if min(c, q - c) < abs(c - q // 2) else 1)
    return bits

def keygen():
    A = [[[random.randrange(q) for _ in range(n)] for _ in range(k)] for _ in range(k)]
    s = small_vec()
    e = small_vec()
    t = [poly_add(x, y) for x, y in zip(mat_vec_mul(A, s), e)]
    return (A, t), s

def encrypt(public_key, bits):
    A, t = public_key
    r, e1, e2 = small_vec(), small_vec(), small_poly()
    u = [poly_add(x, y) for x, y in zip(mat_T_vec_mul(A, r), e1)]
    v = poly_add(poly_add(vec_dot(t, r), e2), encode(bits))
    return u, v

def decrypt(secret_s, ciphertext):
    u, v = ciphertext
    return decode(poly_sub(v, vec_dot(secret_s, u)))

if __name__ == "__main__":
    public_key, secret_key = keygen()
    bits = [1, 0, 1, 1]

    ciphertext = encrypt(public_key, bits)
    recovered = decrypt(secret_key, ciphertext)

    print(f"Original bits:  {bits}")
    print(f"Recovered bits: {recovered}")
    assert recovered == bits

Every run generates a fresh random matrix and fresh noise, exactly like real Kyber, so there’s no single fixed ciphertext to check against. Instead, I ran 200 independent trials of this exact code, fresh keys and fresh random bits each time, and every single one recovered the original bits exactly, confirming the noise-cancellation math holds up across the randomness, not just for one lucky draw.

Limitations

This mirrors the visualizer’s toy parameters exactly, not real Kyber’s production-scale ones:

• n=4, k=2, q=97 instead of n=256, k=2-4, q=3329. At this scale the underlying lattice problem is trivially solvable; the code demonstrates the noise-cancellation mechanism, not anything resembling real security.
• No Number Theoretic Transform. poly_mul is the schoolbook O(n²) algorithm described in the FAQ below; real Kyber’s speed comes specifically from computing the same product in O(n log n) via the NTT, which this code doesn’t implement.
• Encrypts a chosen bit string, not a KEM’d shared secret. Real Kyber is a key encapsulation mechanism: it agrees on a random secret rather than transmitting arbitrary chosen bits, exactly as the FAQ below distinguishes.
• Uses Python’s random, not a CSPRNG. Real lattice cryptography needs cryptographically secure, carefully-distributed noise sampling; random.choice here is for demonstration only.
• Never use this, or hand-rolled lattice cryptography of any kind, in production. Real applications should use a vetted library’s ML-KEM implementation.

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, and Kyber-1024 ≈ AES-256. NIST reaches these by adjusting k=2, 3, 4 while keeping the same efficient n=256 ring. This is 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. That’s 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. That makes 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