Post-Quantum Cryptographic Algorithm by NIST

Module-Lattice-Based Key-Encapsulation Mechanism Standard explained in simple terms using o1

1. Introduction

1.1 Purpose and Scope

This standard describes ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism). A KEM is a cryptographic tool to help two people (or devices) agree on a shared secret key, even if they only have a public (and potentially insecure) channel to communicate over. The shared key can then be used in “symmetric” encryption, which is typically very fast.

• Why a new KEM? Traditional methods (like those in SP 800-56A/56B) depend on math problems that will eventually be breakable by powerful quantum computers. ML-KEM is designed to stay secure even if a future quantum computer is built.
• Where did ML-KEM come from? It is based on a scheme called CRYSTALS-KYBER, one of the algorithms chosen by NIST in their “Post-Quantum Cryptography” project.
• What does this document provide? All the details needed to implement ML-KEM so that your implementation can be tested and validated by NIST.

ML-KEM offers three different parameter sets (think of these as small, medium, and large security) so you can choose how fast it runs versus how secure it is.

1.2 Context

Quantum computers pose a threat to many current cryptographic systems. Once such computers are built, they can solve certain math problems (like factoring or discrete logarithms) much faster than classical computers. This jeopardizes the security of old key-exchange and signature systems. In response, NIST launched a process to select new “post-quantum” cryptographic algorithms. After an extensive review of many candidates, four were selected for standardization, including CRYSTALS-KYBER. ML-KEM is essentially a variant of CRYSTALS-KYBER.

2. Terms, Acronyms, and Notation

• Key-Encapsulation Mechanism (KEM): A set of three algorithms (KeyGen, Encaps, Decaps) to create a shared secret key over an insecure channel.
• Encapsulation Key: The “public” part of a KEM; you can give this to anyone who wants to send you secure messages.
• Decapsulation Key: The “private” part of a KEM; you must keep it secret.
• Shared Secret Key: A key that both parties end up with after running the KEM.
• NTT (Number-Theoretic Transform): A special math tool that makes certain operations (like polynomial multiplication) much faster.

Other terms define standard cryptographic ideas, like “hash function” and “pseudorandom.”

You’ll also see a variety of math symbols (e.g., Zq\mathbb{Z}_q, RqR_q) and short acronyms (e.g., AES, CBD, SHA).

3. Overview of the ML-KEM Scheme

3.1 KEM Basics

A KEM has three main pieces:

1. KeyGen: Generates the public/private key pair (encapsulation key and decapsulation key).
2. Encaps: Creates a shared secret key plus a ciphertext.
3. Decaps: Recovers that same shared secret key from the ciphertext, but only if you have the correct decapsulation key.

3.2 ML-KEM in More Detail

ML-KEM is built on ideas from the “Module Learning with Errors” problem (MLWE). In simpler terms, that means the security relies on problems believed to be extremely hard, especially for quantum computers.

• K-PKE: First, there’s a simpler “public key encryption” scheme named K-PKE (Kyber-like Public-Key Encryption) inside ML-KEM. But K-PKE by itself is not secure enough against advanced attacks—so it gets strengthened by something called the Fujisaki–Okamoto (FO) transform to produce ML-KEM.
• NTT: The Number-Theoretic Transform is a fast way to multiply large polynomials, used throughout ML-KEM to keep it efficient.
• Decapsulation Failures: If everything is done right, the chance that decapsulation fails (both sides end up with different keys) is astronomically small—on the order of one in 21402^{140} or even smaller, depending on the chosen parameters.

3.3 Implementation Requirements

1. Don’t use K-PKE alone. K-PKE is just an internal building block.
2. Controlled Access. Certain “internal” versions of the KEM algorithms are for testing only.
3. Shared Secret Key Usage. Once you get the shared secret key from ML-KEM, you can use it directly for symmetric cryptography or feed it into a standard key-derivation function.
4. Random Number Generation. You need a sufficiently strong random number generator (RNG).
5. Input Checking. The scheme expects you to check inputs thoroughly to avoid errors or attacks.
6. Destroy Intermediate Data. Anything that only lives temporarily (like random numbers or partial keys) should be erased from memory as soon as possible.

4. Auxiliary Algorithms

These are supporting algorithms and definitions used behind the scenes:

• Hash Functions: SHA3-256\text{SHA3-256} and SHA3-512\text{SHA3-512}, plus SHAKE128\text{SHAKE128} and SHAKE256\text{SHAKE256}.
• Compression/Decompression: Some steps compress numbers so they take fewer bits, then decompress them as needed.
• Sampling: ML-KEM picks random polynomials in a particular way—often using something called a “Centered Binomial Distribution” (CBD).
• NTT and Its Inverse: Detailed steps for computing the forward and inverse transform so that polynomial multiplication is fast.

5. The K-PKE Component Scheme

K-PKE is a simpler public-key encryption scheme at the heart of ML-KEM. It has:

1. KeyGen: Generates an encryption key (public) and a decryption key (private).
2. Encrypt: Takes a message and the public key, uses randomness, and produces a ciphertext.
3. Decrypt: Uses the private key to recover the original message.

Important: K-PKE by itself is not enough to guarantee strong protection (it is not IND-CCA2 secure). It must be combined with extra steps (the FO transform), which is exactly what ML-KEM does.

6. Main Internal Algorithms

Here, the document defines three internal (deterministic) algorithms that help build ML-KEM:

1. ML-KEM.KeyGen_internal: Given two random seeds, it recomputes the full pair of keys for ML-KEM.
2. ML-KEM.Encaps_internal: Given a public key and a random seed, it returns a ciphertext and a shared key.
3. ML-KEM.Decaps_internal: Given the private key and a ciphertext, it returns a shared key.

They are called “internal” because they are not meant to be called by external applications directly (except for testing or certain special checks).

7. The ML-KEM Key-Encapsulation Mechanism

Here are the official ML-KEM algorithms that people actually call in real systems:

1. ML-KEM.KeyGen
2. ML-KEM.Encaps (Encapsulation)
3. ML-KEM.Decaps (Decapsulation)

Input Checking

• The standard requires you to check the lengths and certain properties of keys and ciphertexts before using them, to prevent malfunctions or attacks.
• If the checks fail, the algorithm should reject the input rather than continuing.

8. Parameter Sets

ML-KEM has three parameter sets:

1. ML-KEM-512 (smallest; security category ~1)
2. ML-KEM-768 (medium; security category ~3)
3. ML-KEM-1024 (largest; security category ~5)

Each set fixes numbers like kk, η1\eta_1, and so forth, which determine how large the underlying math objects are and how strong the scheme is. Generally, larger parameters mean better security but slower performance.

• Which should I pick? NIST recommends ML-KEM-768 as a default: it balances security (believed to be quite high) against computational efficiency. If that’s too big or you need even higher security, you can switch to one of the other sets.

Putting It All Together

• Goal: Allow two parties, who have no pre-shared secret, to safely agree on a shared secret key that can be used for encryption or other cryptographic needs—and remain secure against future quantum computers.
• Steps: Alice (key owner) runs ML-KEM.KeyGen to create (public) encapsulation key and (private) decapsulation key. Bob obtains the public key and runs ML-KEM.Encaps to produce a ciphertext + a shared secret key. Alice receives the ciphertext, runs ML-KEM.Decaps, and (if all goes well) ends up with the same shared secret key.

They can now use that shared secret key for symmetric encryption.

Why is this important? Because quantum computers will break older cryptography that depends on factoring or discrete logs, but ML-KEM (and other post-quantum algorithms) use different mathematical problems—ones that are expected to resist both classical and quantum attacks.

Final Takeaways

1. ML-KEM is a quantum-resistant method of setting up shared keys.
2. It is built on top of a lattice-based problem (MLWE) and includes an extra transform that strengthens its security level.
3. It has strict requirements for how keys and ciphertexts are generated, checked, and used.
4. There are three main parameter sets for different levels of security and performance.
5. Proper randomness and input checking are essential for security.

This standard ensures a consistent way to implement ML-KEM so that it will interoperate securely across different systems and be validated by NIST.