3.1 Kyber / ML-KEM

Every time you connect to a website over HTTPS, your browser and the server run a key exchange protocol to agree on a shared secret without revealing it to anyone listening on the network. Today, most deployments use X25519 (Diffie-Hellman over Curve 25519). That will be broken by a quantum computer running Shor’s algorithm.

ML-KEM (FIPS 203, formerly CRYSTALS-Kyber) is its post-quantum replacement. It’s a Key Encapsulation Mechanism: one party generates a key pair, the other “encapsulates” a random shared secret inside a ciphertext using the public key, and the first party “decapsulates” to recover the same shared secret. The result: two parties agree on a random secret, and an eavesdropper learns nothing.

The Mathematical Setting

Kyber operates in the polynomial ring $R_q = \mathbb{Z}_{3329}[x]/(x^{256}+1)$. Elements of this ring are polynomials with 256 coefficients, each an integer from 0 to 3328. Arithmetic is polynomial arithmetic modulo both $3329$ (for coefficients) and $x^{256}+1$ (to keep degree below 256).

Why $q = 3329$? It’s a small prime with $q \equiv 1 \pmod{256}$ (since $3328 = 2^8 \cdot 13$), so $\mathbb{Z}_q$ has primitive 256th roots of unity but no 512th ones. That is enough for an incomplete Number Theoretic Transform (NTT) for $n = 256$: seven NTT layers split $x^{256}+1$ into 128 quadratic factors, and multiplication finishes with cheap products of degree-1 polynomials modulo those quadratics. The NTT turns polynomial multiplication from an $O(n^2)$ operation into an $O(n \log n)$ one — critical for performance.

Parameter Sets

Kyber comes in three sizes, trading off security for key/ciphertext size. The module rank $k$ controls how many ring elements are in the key vectors:

Step 1: Key Generation

The recipient generates a key pair. The public key is an LWE instance; the secret key is the hidden secret. Here’s what happens, explained plainly:

Step 2: Encapsulation

The sender (who only has the public key) wants to generate a shared secret and send an encrypted version of it. The process looks like a second LWE sample, but with the roles of the matrix transposed.

Step 3: Decapsulation

The recipient uses their secret key to recover the shared secret from the ciphertext. The math works because the LWE noise terms are small enough to cancel out during decryption.

Security: The FO Transform

The scheme above (Kyber.PKE) is only secure against passive eavesdroppers. An attacker who can send chosen ciphertexts and observe whether decryption succeeds or fails could potentially extract the secret key. To prevent this, Kyber applies the Fujisaki-Okamoto (FO) transform — a standard compiler that converts a passively secure scheme into one that’s secure against active attackers (called CCA2 security).

The key idea: during decapsulation, the recipient re-runs encapsulation using the recovered message and checks that the result matches the received ciphertext. If it doesn’t match (someone tampered with the ciphertext), a pseudorandom value derived from the secret key and the ciphertext is returned instead. This “implicit rejection” prevents attackers from learning whether decryption succeeded, closing the chosen-ciphertext attack vector.

Implementation Choices

Kyber Key Generation — Step by Step

Here is the full key generation procedure at the level of concrete arithmetic, using ML-KEM-768 ($k=3$) as the running example. Every step maps directly to lines in the FIPS 203 specification.

Step 1 — Generate the seed. Sample 32 uniformly random bytes $d$ from the OS CSPRNG. Derive two 32-byte seeds by hashing: $(\rho, \sigma) = G(d)$ where $G = \text{SHA3-512}$.$\rho$ is the public seed for expanding $A$; $\sigma$ is the private seed for sampling secrets.

Step 2 — Expand the matrix. Generate $A \in R_q^{k \times k}$ by calling SHAKE-128 with input $\rho \| i \| j$ for each entry $A[i][j]$. Each entry is a polynomial in $R_q$ with 256 uniformly random coefficients in $[0, q-1]$. $A$ is generated directly in NTT domain, so no forward NTT is needed. The seed $\rho$ is public — anyone can re-derive $A$ from it.

Step 3 — Sample the secret and error vectors. Using $\sigma$ as a PRF key and a counter, sample:

Each polynomial’s coefficients are drawn from the centered binomial distribution $B_\eta$ with $\eta = 2$. To sample one coefficient: draw 4 bits $(a_0, a_1, b_0, b_1)$ and return $(a_0 + a_1) - (b_0 + b_1) \in \{-2,-1,0,1,2\}$. This avoids the need for Gaussian sampling (which is slow and hard to implement in constant time).

Step 4 — Compute the public key polynomial. Apply the NTT to $s$ and $e$, then compute:

where $\hat{s}, \hat{e}$ are the NTT representations of $s, e$. The product $A \cdot \hat{s}$ is a matrix-vector multiplication done coefficient-wise in NTT domain — $k^2 = 9$ pointwise polynomial multiplications for ML-KEM-768, each consisting of 128 small degree-1 base-case products (the NTT is incomplete).

Result. The public key is $(\rho, t)$. Unlike the ciphertext, $t$ is not compressed: each coefficient is stored in 12 bits, so $t$ takes $384k$ bytes and the public key is $384k + 32$ = 1,184 bytes. The secret key retains $s$ in NTT form plus a copy of the public key, its hash $H(\text{pk})$, and a random 32-byte value $z$ used for implicit rejection.

Encapsulation and Decapsulation — Detailed Steps

Encapsulation and decapsulation are mirror operations. The sender uses the public key to encrypt a random 32-byte value; the receiver uses the secret key to recover it. Here is the complete arithmetic.

Kyber in TLS — Hybrid Key Exchange

Kyber is not deployed alone in TLS. The standard approach is a hybrid key exchange: run both X25519 (classical) and ML-KEM-768 (post-quantum) in the same handshake, then combine their shared secrets cryptographically. This gives security against both a classical attacker today and a quantum attacker in the future.

The IETF standard for this is X25519MLKEM768 (RFC 10024, August 2026, built on the RFC 9954 hybrid design framework). See the hybrid TLS guide for deployment. The TLS 1.3 key share extension carries both an X25519 public key (32 bytes) and an ML-KEM-768 public key (1,184 bytes). The server responds with both shares. Each side independently derives two shared secrets and concatenates them (ML-KEM first) as the input to the TLS 1.3 key schedule:

The concatenation-then-HKDF approach ensures that if either component is secure, the combined secret is secure. An attacker who breaks X25519 (e.g., with a quantum computer) still cannot break ML-KEM-768; an attacker who breaks ML-KEM-768 (e.g., due to an unforeseen classical attack) still cannot break X25519.

In Chrome’s implementation (behind a flag in Chrome 116, on by default for desktop since Chrome 124), the combined key share adds roughly 1.2 KB to the TLS ClientHello. Benchmarks show this adds less than 1 ms of latency on a typical connection — dominated by network round-trip time, not by the cryptography.

Cloudflare’s servers support X25519MLKEM768 across their infrastructure, and AWS offers hybrid post-quantum TLS on service endpoints such as KMS, ACM and Secrets Manager. OpenSSL 3.5 includes ML-KEM-512, ML-KEM-768, and ML-KEM-1024 as named groups in the default build.

Code Example — Using ML-KEM in Practice

The following pseudocode shows the API surface of ML-KEM-768 as exposed by two real production libraries: liboqs (C, via Open Quantum Safe project) and pqcrypto (Rust). These are the libraries you would actually call in a production system today.

#include <oqs/oqs.h>

// Key generation
OQS_KEM *kem = OQS_KEM_new(OQS_KEM_alg_ml_kem_768);

uint8_t *pk = malloc(kem->length_public_key);   // 1184 bytes
uint8_t *sk = malloc(kem->length_secret_key);   // 2400 bytes
OQS_KEM_keypair(kem, pk, sk);

// Encapsulation (sender side)
uint8_t *ct        = malloc(kem->length_ciphertext);    // 1088 bytes
uint8_t *ss_sender = malloc(kem->length_shared_secret); // 32 bytes
OQS_KEM_encaps(kem, ct, ss_sender, pk);

// Decapsulation (receiver side)
uint8_t *ss_recv = malloc(kem->length_shared_secret);   // 32 bytes
OQS_KEM_decaps(kem, ss_recv, ct, sk);

// ss_sender == ss_recv: use as AES-256-GCM key
assert(memcmp(ss_sender, ss_recv, 32) == 0);

OQS_KEM_free(kem);

use pqcrypto_mlkem::mlkem768;
use pqcrypto_traits::kem::{PublicKey, SecretKey, SharedSecret, Ciphertext};

// Key generation
let (pk, sk) = mlkem768::keypair();
// pk: 1184 bytes, sk: 2400 bytes

// Encapsulation (sender)
let (ss_sender, ct) = mlkem768::encapsulate(&pk);
// ct: 1088 bytes, ss_sender: 32 bytes

// Decapsulation (receiver)
let ss_recv = mlkem768::decapsulate(&ct, &sk);
// ss_recv: 32 bytes

assert_eq!(ss_sender.as_bytes(), ss_recv.as_bytes());
// Now use ss_sender as a key for AES-256-GCM or ChaCha20-Poly1305

For hybrid TLS with Go (using the standard library’s experimental PQ support):

// Go 1.24+ includes X25519MLKEM768 in crypto/tls
// It is enabled automatically when CurvePreferences is not set.

cfg := &tls.Config{
    // X25519MLKEM768 is negotiated first when the client supports it.
    // No explicit configuration needed in Go 1.24+.
    MinVersion: tls.VersionTLS13,
}

// To verify which key exchange was used:
conn.ConnectionState().TLSUnique // or inspect via crypto/tls internals
// Chrome DevTools > Security panel shows "X25519MLKEM768" when negotiated.

Key library references for production use:

• liboqs (C/C++/Python/Go/Rust/Java wrappers): https://github.com/open-quantum-safe/liboqs
• pqcrypto (Rust, safe bindings to reference implementations): https://crates.io/crates/pqcrypto-mlkem
• FIPS 203 (the normative specification): https://doi.org/10.6028/NIST.FIPS.203
• BoringSSL (Google’s fork of OpenSSL, includes ML-KEM natively): https://boringssl.googlesource.com/boringssl
• OpenSSL 3.5+ includes ML-KEM as first-class named groups in the default build.