ML-KEM (FIPS 203): CRYSTALS-Kyber Standardized

ML-KEM (Module-Lattice-based Key Encapsulation Mechanism), standardized as FIPS 203 in August 2024, is the post-quantum replacement for Diffie-Hellman and RSA key exchange. It encapsulates a symmetric key under a public key, producing a shared secret that both parties can use for symmetric encryption. ML-KEM is derived from CRYSTALS-Kyber with minor modifications for cleaner specification.

ML-KEM defines three parameter sets. ML-KEM-512 targets approximately 128-bit classical and 100-bit post-quantum security with a public key of 800 bytes and ciphertext of 768 bytes. ML-KEM-768 targets 192-bit classical security (public key 1184 bytes, ciphertext 1088 bytes). ML-KEM-1024 targets 256-bit classical security (public key 1568 bytes, ciphertext 1568 bytes). NIST recommends ML-KEM-768 for most applications.

ML-KEM key generation works as follows: sample a random matrix A from a seed using SHAKE-128, sample small secret vector s and error vector e, compute t = As + e mod q. The public key is (seed, t) and the private key is s along with the public key hash. The use of a seed rather than storing A saves significant memory and bandwidth.

To encapsulate, the sender generates a random message m and derives both a symmetric key K and randomness r via SHA-3. The ciphertext consists of two parts: u = Ar + e1 mod q and v = t^T r + e2 + encode(m) mod q. The shared secret K is derived from the hash of m. The randomness is deterministically derived from m, binding the ciphertext to the key.

Decapsulation recovers m by computing v - s^T u and decoding, then re-derives K from m. The Fujisaki-Okamoto transform adds a crucial step: re-encrypt using the recovered m and check that the ciphertext matches. If it does not match, return a pseudorandom value derived from a hash of the private key and ciphertext. This prevents chosen-ciphertext attacks by making decapsulation deterministic and verifiable.

ML-KEM achieves IND-CCA2 security in the quantum random oracle model (QROM), proven under the Module-LWE assumption. The QROM is important because post-quantum adversaries can query hash functions in superposition. The security proof by Hofheinz, Hovelmanns, and Kiltz (the HHK framework) provides tight reductions from Module-LWE to ML-KEM security in the QROM.

ML-KEM dramatically outperforms RSA for key exchange at equivalent security levels. ML-KEM-768 key generation takes about 16 microseconds on a modern CPU, encapsulation 20 microseconds, decapsulation 18 microseconds. RSA-2048 key generation takes seconds. ML-KEM public keys (1184 bytes) are larger than ECDH (32-64 bytes) but much smaller than RSA-2048 (256 bytes for just the key, but longer in practice).

During the transition period, hybrid key exchange combines ML-KEM with a classical algorithm (typically X25519 or P-256 ECDH). The shared secret is the hash of both KEM outputs: K = Hash(K_classical || K_pqc). This ensures that security cannot be worse than either component. Hybrid TLS is specified in IETF draft-ietf-tls-hybrid-design and supported in BoringSSL, OpenSSL 3.x, and Rustls.

The IETF has defined X25519ML-KEM-768 as the hybrid key share for TLS 1.3 (draft-ietf-tls-hybrid-design). Chrome added support in version 124 (April 2024), Firefox in version 132 (2024). Cloudflare deployed ML-KEM in its TLS termination infrastructure. This rapid adoption means hundreds of millions of TLS connections per day now include post-quantum key exchange.

Due to the error terms in LWE, there is a tiny probability that decapsulation fails even without an adversary. For ML-KEM-512, the failure probability is approximately 2^{-139}; for ML-KEM-768, it is 2^{-164}. These rates are far below any practical concern (for comparison, hardware errors are far more frequent) and do not affect security but must be accounted for in the specification.

ML-KEM is implemented in numerous open-source libraries. The reference implementation from the Kyber team is in the public domain. PQClean provides a cleaned, portable C implementation. liboqs (Open Quantum Safe project) integrates ML-KEM into a library wrapper. AWS-LC (Amazon's fork of BoringSSL) includes ML-KEM for AWS TLS endpoints. The NIST FIPS 203 standard includes detailed pseudocode for all operations.

ML-KEM (FIPS 203) is the NIST-standardized post-quantum KEM based on Module-LWE. Three parameter sets (512/768/1024) provide 128/192/256-bit classical security. Key generation produces a compact public key from a random seed; encapsulation derives a shared secret; decapsulation uses the FO transform for CCA2 security. ML-KEM is significantly faster than RSA and is already deployed in Chrome, Firefox, and Cloudflare TLS.