← Back to Blog Research

FIPS 203 Walkthrough: ML-KEM Standard in Plain English

11 min read

When NIST published FIPS 203 on August 13, 2024, it ended a seven-year competition that started in late 2016. The document is 51 pages of dense math notation. Most engineers will never read it. They will pull a library off the shelf, call mlkem_encapsulate(), and trust the result. That trust depends on the library matching the document precisely.

This walkthrough takes the public, official text of FIPS 203 (the NIST Federal Information Processing Standard for Module-Lattice-Based Key-Encapsulation Mechanism, ML-KEM) and translates each section into plain English. Think of FIPS 203 as the building code for a new kind of door lock, the kind that does not break when a quantum computer arrives. The code tells locksmiths exactly how to mill the pins so every lock made anywhere on earth opens with the same key.

Section 1: Introduction and Why ML-KEM Exists

Section 1 sets the stage. ML-KEM is a key-encapsulation mechanism, not an encryption algorithm in the conventional sense. A KEM does one job: two parties end up with the same secret key, even though they have never spoken before. After that, a separate symmetric cipher (AES, ChaCha20) handles the actual data.

The introduction explains that ML-KEM is built on the Module Learning With Errors (MLWE) problem. Think of MLWE as the standardized version of an obstacle course. The course has been studied since 2010, and despite world-class cryptographers trying to find shortcuts, none have been found that work on a quantum computer.

Section 1 also names the algorithm's heritage. ML-KEM is the renamed, slightly modified version of CRYSTALS-Kyber, the third-round NIST PQC competition winner. The renaming was not cosmetic. NIST tightened the parameters and changed how randomness flows through the key generation step. Implementations of pre-standard Kyber will not interoperate with FIPS 203.

For more background on this transition, see our overview of NIST PQC standards timeline and ML-KEM explained.

Section 2: Notation and Mathematical Conventions

Section 2 is where the document gets dense fast. It defines polynomial rings, byte encoding rules, and how integers map to bytes. Think of this section as the legend on a map. None of it is interesting on its own, but every later section relies on these symbols.

The key conventions to remember are:

ML-KEM works in the polynomial ring R_q where q = 3329 and the polynomial has 256 coefficients
Coefficients are stored modulo q, fitting in 12 bits each
Byte order is little-endian throughout

These choices were not arbitrary. The prime 3329 was selected because it permits efficient Number Theoretic Transform (NTT) operations, which speed up polynomial multiplication. Section 2 also defines the BitsToBytes and BytesToBits functions, which appear in nearly every later algorithm.

If the section feels theoretical, remember the analogy: this is like a recipe defining what "one cup" means before listing ingredients. Skip it and the recipe still kind of works, but you will burn the soufflé.

Section 3: Cryptographic Functions Used Inside ML-KEM

Section 3 lists the building blocks ML-KEM borrows from elsewhere. ML-KEM does not invent its own hash functions. It uses SHA-3 and SHAKE family primitives defined in FIPS 202.

The functions used are:

SHAKE128, used as an extendable output function for sampling
SHAKE256, used for key derivation and message hashing
SHA3-256 and SHA3-512, used as fixed-output hashes

This separation matters because it means a FIPS 203 implementation can call the operating system's existing FIPS 202 module rather than rolling its own SHA-3. For more on the relationship between these standards, our NIST FIPS guide maps out the family tree.

Section 4: Auxiliary Algorithms

Section 4 contains the helpers that everything else depends on. These are the boring engine parts: bytes-to-bits conversion, polynomial encoding, sampling functions, and the Number Theoretic Transform.

The auxiliary algorithms are:

BitsToBytes and BytesToBits (4.2.1)
ByteEncode_d and ByteDecode_d, packing polynomial coefficients into bytes at d bits each (4.2.1)
SampleNTT, the rejection sampling routine that generates uniform polynomials in NTT form from a SHAKE128 stream (4.2.2)
SamplePolyCBD_eta, the centered binomial distribution sampler that produces small "noise" polynomials (4.2.2)
NTT and NTT_inverse, fast polynomial multiplication via the Number Theoretic Transform (4.3)

Think of these like the stations on an assembly line. Section 4 is where the standardization is most fragile. If two implementations sample bytes differently, they produce different keys from the same seed. That is why FIPS 203 specifies sampling at the bit level.

Sections 5: K-PKE, the Underlying Public-Key Encryption

Before defining ML-KEM directly, Section 5 defines K-PKE, an internal public-key encryption scheme that ML-KEM transforms into a KEM. K-PKE is IND-CPA secure (resistant to a passive eavesdropper) but not IND-CCA secure (it cannot resist an attacker who can submit chosen ciphertexts).

Section 5 has three subsections:

K-PKE.KeyGen (5.1) generates a public/secret key pair from 32 bytes of randomness
K-PKE.Encrypt (5.2) encrypts a 32-byte message under a public key, producing a ciphertext
K-PKE.Decrypt (5.3) decrypts a ciphertext using the secret key

Imagine K-PKE as the rough draft of a contract. It does the basic job, but it can be tampered with by a sophisticated attacker. The next section is where ML-KEM hardens it into a final, attacker-resistant version.

Section 6: ML-KEM Key Generation

Section 6 specifies ML-KEM.KeyGen, the public-facing key generation routine. This function takes 64 bytes of randomness (32 for the K-PKE seed, 32 for an "implicit rejection" value) and returns:

An encapsulation key ek (the public key)
A decapsulation key dk (the secret key, larger than ek because it includes a hash of ek and the implicit rejection value)

The decapsulation key contains the K-PKE secret, the K-PKE public key, a hash of the public key, and a 32-byte rejection seed. That bundle is what enables the implicit-rejection trick used during decapsulation.

ML-KEM.KeyGen is deterministic given its 64-byte seed. Two calls with the same seed produce the same key pair. This determinism is essential for known-answer tests and for hardware security modules that need reproducible behavior.

Section 7: ML-KEM Encapsulation

Section 7 defines ML-KEM.Encaps. The caller has the recipient's public key. The function takes 32 bytes of randomness, performs three internal steps, and returns:

A 32-byte shared secret K
A ciphertext c that the caller sends to the recipient

Inside, the function:

Hashes the message with SHA3-256 to derive intermediate values
Calls K-PKE.Encrypt with derived randomness
Hashes the ciphertext together with intermediate values to produce K

This is the Fujisaki-Okamoto transform. It is what upgrades K-PKE from IND-CPA to IND-CCA2. The transform binds the shared secret to the ciphertext so an attacker cannot manipulate the ciphertext without making the shared secret unrecoverable.

Section 8: ML-KEM Decapsulation

Section 8 specifies ML-KEM.Decaps. The recipient has the decapsulation key and a ciphertext. The function returns a 32-byte shared secret K.

The crucial trick is implicit rejection. The function decrypts the ciphertext to recover a candidate message, re-encrypts that message, and compares the result to the input ciphertext. If they match, it returns the legitimate shared secret. If they do not match, it returns a pseudorandom value derived from the rejection seed and the ciphertext.

Critically, the function does not branch based on success or failure. It computes both paths and uses constant-time selection at the end. This prevents an attacker from learning whether a ciphertext was valid by measuring timing.

The implicit-rejection design replaces older "explicit reject" schemes that returned an error on bad ciphertext. Explicit rejection leaked information through error states.

Annex A: Parameter Sets

Annex A defines the three concrete parameter sets:

ML-KEM-512 (NIST security category 1, similar to AES-128)
ML-KEM-768 (NIST security category 3, similar to AES-192)
ML-KEM-1024 (NIST security category 5, similar to AES-256)

The numbers refer to the dimension of the underlying module lattice. Each parameter set lists q, n, k, eta_1, eta_2, d_u, d_v values. ML-KEM-768 is the recommended default for most applications, balancing security and bandwidth.

The encapsulation key sizes are 800, 1184, and 1568 bytes respectively. Decapsulation keys are 1632, 2400, and 3168 bytes. Ciphertexts are 768, 1088, and 1568 bytes.

Annex B: Test Vectors

Annex B was added to provide known-answer tests. NIST also publishes a more extensive test suite via the Cryptographic Algorithm Validation Program (CAVP) and the Automated Cryptographic Validation Protocol (ACVP). Implementations seeking FIPS validation must pass both.

For broader background on lattice-based schemes, see lattice-based cryptography explained.

How QNSQY Implements FIPS 203

QNSQY's ML-KEM implementation passes the official NIST ACVP test vectors and is run inside a Rust-based pipeline that uses the same standardized SHA-3 module. We deploy ML-KEM in hybrid encryption mode alongside X25519, so a flaw in either algorithm does not compromise the session.

We default to ML-KEM-768 for everyday use and offer ML-KEM-1024 for users in regulated industries. The Free tier ships with ML-KEM-512 hybrid because that satisfies category 1, which exceeds typical TLS 1.3 strength against classical adversaries while adding quantum resistance.

Mapping the Document to Code

Reading FIPS 203 in isolation is harder than reading it next to a reference implementation. The document numbers algorithms and section. Code maps each numbered algorithm to a function. The naming convention used in the document matches the public reference implementation maintained by the CRYSTALS team and the version vendored by major Rust and Go libraries.

For each section, the typical mapping is:

Section 4 functions become helper functions in a util or arith module
Section 5 K-PKE functions become a private kpke submodule
Section 6, 7, 8 ML-KEM functions become the public keygen, encaps, decaps functions
Annex A parameter sets become compile-time constants

The ACVP test harness drives all functions with predetermined seeds and verifies byte-for-byte output. Any implementation that passes ACVP is, by definition, conformant.

Why Domain Separation Matters

The document repeatedly emphasizes domain separation between hash function calls. SHAKE128 is used for matrix expansion. SHAKE256 is used for randomness derivation and the final symmetric key. SHA3-256 and SHA3-512 are used for fixed-size hashing.

If two of these calls produced overlapping outputs from the same input, an attacker could feed the output of one stage into another and break the security argument. The fix is domain-separation prefixes: a unique byte appended to the input before hashing, distinguishing each use.

For implementations migrating from pre-standard Kyber to FIPS 203 ML-KEM, the domain-separation byte changes are the most common source of incompatibility. Always test against published ACVP vectors after migration.

FAQ

Does FIPS 203 replace ECDH and RSA?

Not yet. FIPS 203 standardizes ML-KEM, but NIST encourages hybrid deployment alongside ECDH for now. CNSA 2.0, published by NSA, gives a deadline of 2035 for full migration. See our 2035 NSA CNSA deadline plan for the timeline.

Why three parameter sets?

Different security categories address different threat models. Category 1 (ML-KEM-512) covers most consumer and enterprise use. Category 3 (ML-KEM-768) is the recommended general-purpose default. Category 5 (ML-KEM-1024) is reserved for top-secret data.

Is ML-KEM the same as CRYSTALS-Kyber?

Almost. NIST tightened the seed expansion for key generation and made several specification clarifications. Implementations of "Kyber-768" and "ML-KEM-768" are not interoperable.

When did FIPS 203 become mandatory?

The standard became effective on August 13, 2024. Federal agencies are expected to begin transition planning, with full mandatory use tied to the broader CNSA 2.0 schedule.

What is the practical key and ciphertext size penalty over X25519?

X25519 public keys are 32 bytes. ML-KEM-768 encapsulation keys are 1184 bytes. The trade is roughly 1 KB extra per key exchange in return for quantum resistance.

Sources

FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard, NIST, August 13, 2024
FIPS 202, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, NIST, August 5, 2015
NIST IR 8413, Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, NIST, July 2022
CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation, Round 3 submission, CRYSTALS team, 2020
Cryptographic Algorithm Validation Program (CAVP) - ACVP Test Vectors for ML-KEM, NIST CSRC

Protect Your Data Before Q-Day Arrives

QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.

Try QNSQY