Lattices.io — Mathematical Lattices & Post-Quantum Cryptography

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 the smallest prime of the form $$512k + 1$$ , which makes the Number Theoretic Transform (NTT) maximally efficient for $$n = 256$$ . 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:

ML-KEM-512 (k=2)

~128 bits of security (NIST Level 1). Smallest keys.

Public key: 800 bytes
Secret key: 1,632 bytes
Ciphertext: 768 bytes

Suitable for constrained environments where bandwidth matters most.

ML-KEM-768 (k=3)

~192 bits of security (NIST Level 3). Recommended default.

Public key: 1,184 bytes
Secret key: 2,400 bytes
Ciphertext: 1,088 bytes

Google Chrome uses this (with X25519 hybrid) for all HTTPS connections.

ML-KEM-1024 (k=4)

~256 bits of security (NIST Level 5). Maximum security.

Public key: 1,568 bytes
Secret key: 3,168 bytes
Ciphertext: 1,568 bytes

Used where long-term data secrecy matters (classified, financial).

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:

ML-KEM Key Generation

1. Generate a random 32-byte seed $\rho$ and expand it deterministically into a matrix $A \in R_q^{k \times k}$ using SHAKE-128. This matrix is public — anyone can expand it from the seed.

2. Sample a secret vector $s \in R_q^k$ with small coefficients (drawn from the centered binomial distribution — each coefficient is between $-\eta$ and $+\eta$ , where $\eta = 2$ or 3).

3. Sample a small error vector $e \in R_q^k$ similarly.

4. Compute $$t = As + e$$ . This is the Module-LWE sample — a noisy linear function of the secret.

Public key: $(\rho, t)$ — 1,184 bytes for ML-KEM-768.
Secret key: $$s$$ — kept private.

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.

ML-KEM Encapsulation

1. Sample a random 32-byte message $$m$$ . Hash it together with the public key hash to derive deterministic randomness.

2. Sample a small secret $$r$$ and errors $$e_1, e_2$$ .

3. Compute:
$u = A^\top r + e_1$ (analogous to the public key step, transposed)
$v = t^\top r + e_2 + \mathrm{encode}(m)$

4. The ciphertext is $$(u, v)$$ , compressed to save bytes.
The shared secret is derived from $$m$$ and the public key hash.

The sender sends the ciphertext and uses the shared secret to encrypt application data (via AES-GCM or similar).

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.

ML-KEM Decapsulation — Why It Works

The recipient computes $v - s^\top u$ :

$v - s^\top u = (t^\top r + e_2 + m') - s^\top(A^\top r + e_1)$

$= (As+e)^\top r + e_2 + m' - s^\top A^\top r - s^\top e_1$

$= e^\top r + e_2 - s^\top e_1 + m'$

The term $e^\top r + e_2 - s^\top e_1$ is small (all the vectors involved have tiny coefficients). Rounding this to the nearest multiple of $$q/2$$ recovers $$m$$ exactly, as long as the noise doesn't exceed $$q/4$$ — which the parameter choices guarantee with overwhelming probability.

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

Centered binomial distribution

Kyber avoids discrete Gaussian sampling — which is slow and notoriously hard to implement in constant time — and instead uses the centered binomial distribution $B_\eta$ : sample $2\eta$ random bits, compute their alternating sum. This is fast, simple, and statistically close enough to Gaussian for security.

Constant-time implementation

Side-channel attacks read secret information from timing variations and power consumption. Kyber is designed so all operations run in constant time regardless of secret values: NTT operations have data-independent access patterns; the FO re-encryption check uses constant-time comparison; rejection uses implicit rejection (no branch on secret data).

Performance (AVX2, x86-64)

ML-KEM-768 on modern hardware:
KeyGen: ~14 μs
Encapsulate: ~18 μs
Decapsulate: ~17 μs

For comparison, X25519 key agreement: ~120 μs. Kyber is ~7× faster, despite being post-quantum secure and having larger keys.

Deployment status

Google Chrome has deployed X25519+Kyber hybrid key exchange for all TLS connections since late 2023. Cloudflare, AWS, and Signal have all deployed PQC key exchange. OpenSSL 3.x and BoringSSL include ML-KEM. The migration from classical to post-quantum key exchange is already underway at internet scale.