Demystifying ML-KEM: How NIST's Post-Quantum Key Exchange Works

ML-KEM is the key-establishment algorithm NIST standardized in August 2024 as FIPS 203. It replaces the job that RSA key transport and elliptic-curve Diffie-Hellman do today: letting two parties agree on a secret key over a network that an attacker can read. Unlike those algorithms, ML-KEM is designed so that a large quantum computer running Shor's algorithm gains no meaningful advantage against it.

This guide explains what ML-KEM is, why it is believed to be quantum-resistant, what its three parameter sets look like in practice, and what engineers need to know before it reaches their systems.

Why RSA and elliptic curves are the problem

RSA security rests on the difficulty of factoring a large integer. Elliptic-curve and finite-field Diffie-Hellman rest on the difficulty of the discrete logarithm problem. On classical computers both are hard. In 1994 Peter Shor showed that a sufficiently large, error-corrected quantum computer could solve both in polynomial time. No such machine exists today, but key exchange is special: traffic recorded now can be decrypted later, which is why the migration starts before the hardware exists (see Harvest Now, Decrypt Later).

Symmetric cryptography is affected far less. Grover's algorithm gives only a quadratic speedup, so AES-256 and SHA-384 remain comfortable. The urgent work is in public-key cryptography.

The idea behind lattice cryptography

ML-KEM is built on the Module Learning With Errors (MLWE) problem. Intuitively: you are given many linear equations over a small integer ring, but every equation has a little random noise added. Without the noise, solving for the secret is easy linear algebra. With the noise, recovering the secret appears to be hard, and no known quantum algorithm changes that. The problem is closely related to finding short vectors in high-dimensional lattices, which has been studied for decades.

The "module" part means the arithmetic is done on small fixed-size polynomials arranged in a matrix. This is what makes ML-KEM fast: the core operation is polynomial multiplication, which maps well onto modern CPUs.

Key encapsulation instead of key exchange

ML-KEM is a key encapsulation mechanism (KEM), which has a slightly different shape than Diffie-Hellman:

1. The server runs KeyGen and publishes an encapsulation (public) key. It keeps the decapsulation (private) key.
2. The client runs Encaps with that public key. This produces a random 32-byte shared secret plus a ciphertext.
3. The client sends the ciphertext to the server.
4. The server runs Decaps with its private key and recovers the same 32-byte shared secret.

Both sides now hold the same secret, which is fed into a key-derivation function to produce session keys. Because the client's contribution is a single ciphertext rather than a public key of its own, protocol designers talk about KEMs rather than "key exchange," even though TLS uses them in the same slot.

ML-KEM internally applies a Fujisaki-Okamoto-style transform so that decapsulation is safe against chosen-ciphertext attacks. In practice this means you should always use a vetted library rather than the raw algorithm.

Parameter sets and sizes

FIPS 203 defines three parameter sets. The sizes below are the numbers that matter when you plan for bandwidth and packet limits:

For comparison, an X25519 public key is 32 bytes. ML-KEM-768 is the common default for general internet use. ML-KEM-1024 is typically chosen where policy demands the highest category, such as some government systems.

What changes for engineers

Bigger handshakes. A TLS ClientHello that carries an ML-KEM-768 key share grows by roughly 1.2 KB. That can push it past a single packet, and some older middleboxes and load balancers mishandled fragmented ClientHello messages during early deployments. Test through every network device on your path.

Speed is not the issue. ML-KEM operations are typically as fast as, or faster than, X25519 in optimized implementations. The cost is size, not CPU.

Hybrid first. Most real deployments pair ML-KEM with a classical algorithm such as X25519 so that security holds if either one is broken. The details are covered in Hybrid TLS with X25519 and ML-KEM-768.

Implementation quality matters. Lattice algorithms have subtle side-channel risks (timing and power). Use maintained libraries such as OpenSSL 3.5+, BoringSSL, AWS-LC, or the standard libraries of recent Go and Java releases, rather than writing your own.

Where ML-KEM does not help

ML-KEM only covers key establishment. It does not sign anything. Certificates, code signing and document signatures need the signature standards ML-DSA and SLH-DSA, covered in Post-Quantum Digital Signatures. It also does nothing for weak passwords, leaked keys or misconfigured servers.

Practical next steps

• Find out which of your TLS endpoints, VPNs and message queues negotiate RSA or ECDH key exchange today (see Building a Cryptographic Inventory).
• Check whether your TLS libraries and CDN already offer hybrid ML-KEM groups, and enable them in a staging environment first.
• Keep algorithm identifiers configurable rather than hardcoded, so the next change is a configuration update (crypto-agility patterns).