---
# System prepended metadata

title: FIPS 203 ML-KEM
tags: [PQC]

---

# FIPS 203 ML-KEM

## Module-Lattice-Based Key-Encapsulation Mechanism

A KEM is a cryptographic scheme that, under certain conditions, can be used to establish a **shared secret key** between two communicating parties. This shared key can then be used for *symmetric-key cryptography*

## Key Generation

![GoldenKeyBaliEastParadiseGIF](https://hackmd.io/_uploads/BytfPN8-xl.gif =10%x)

### K-PKE KeyGen()
- Takes no input, requires randomness
- Outputs an encryption key $ek_{PKE}$ and a decryption key $dk_{PKE}$
- The decryption key of **K-PKE.KeyGen** is a length-k vector $s$ of elements of $R_q$ i.e. $s \in R^k_q$
- $s$ is a set of secret variables, while the encryption key is a collection of "noisy" linear equations ($A, As + e$) in the secret variables $s$. The rows of the matrix $A$ form the equation coefficients.
- The secret $s$ and the "noise" $e$ are sampled from the centered binomial distribution$(CBD)$ using randomness expanded from a seed via $PRF$. Once $A$ and $s$ and $e$ are generated, the computation of the final part $t = As+e$ of the encryption key takes place.
---
**K-PKE KeyGen()**
*$Generates\: an\: encryption\: key\: and\: a\: corresponding\: decryption\: key$*
$\mathbf{Output:}$ encryption key $ek_{PKE} \in \mathbb{B}^{384k+32}$
$\mathbf{Output:}$ decryption key $dk_{PKE} \in \mathbb{B}^{384k}$
01: $d \leftarrow \mathbb{B}^{32}$ $\quad\qquad$**▷ $\mathbb{B}$ is the set {0, 1, ..., 255} of `uint8`, d is 32 random bytes**
02: $(\rho, \sigma) \leftarrow G(d)$ $\quad$**▷ G: SHA3-512 which outputs two 32-byte outputs**
03: $N \leftarrow 0$

04: $\mathbf{for}\:(i,\:j \leftarrow 0;\:i,\:j\:<\:k;\:i,\:j$++) $\quad$ **▷ Generate matric $\hat{A} \in (\mathbb{Z}^{256}_q)^{k*k}$**
05: $\quad \mathbf{\hat{A}}[i,\:j] \leftarrow SampleNTT(\rho\:||\:i\:||\:j)$
06: $\mathbf{end\:for}$

07: $\mathbf{for}\:(i \leftarrow 0 ;\: i < k; \: i$ ++) $\qquad\quad\qquad$ **▷ Generate $s \in (\mathbb{Z}^{256}_q)^k$**
08: $\quad \mathbf{s}[i] \leftarrow SamplePolyCBD_{\eta_1}(PRF_{\eta_1}(\sigma,\:N))$ 
09: $\quad N \leftarrow N + 1$
10: $\mathbf{end\:for}$

11: $\mathbf{for}\:(i \leftarrow 0 ;\: i < k; \: i$ ++) $\qquad\quad\qquad$ **▷ Generate $e \in (\mathbb{Z}^{256}_q)^k$**
12: $\quad \mathbf{e}[i] \leftarrow SamplePolyCBD_{\eta_1}(PRF_{\eta_1}(\sigma,\:N))$ 
13: $\quad N \leftarrow N + 1$
14: $\mathbf{end\:for}$

15: $\mathbf{\hat{s}} \leftarrow NTT(\mathbf{s})$ $\qquad\quad\quad$ **▷ Run k times NTT**
16: $\mathbf{\hat{e}} \leftarrow NTT(\mathbf{e})$ $\qquad\quad\quad$ **▷ Run k times NTT**
19: $\mathbf{\hat{t}} \leftarrow \mathbf{\hat{A}} \circ \mathbf{\hat{s}} + \mathbf{\hat{e}}$ $\quad\quad\quad$ **▷ Noisy linear system in NTT domain**

20: $ek_{PKE} \leftarrow ByteEncode_{12}(\hat{t}) || \rho$ $\quad$ **▷ Run $ByteEncode_{12}$ k times; include seed for $\hat{A}$**
21: $dk_{PKE} \leftarrow ByteEncode_{12}(\hat{s})  \:\qquad$ **▷ Run $ByteEncode_{12}$ k times**
22: $\mathbf{return} \:(ek_{PKE}, \: dk_{PKE})$

---


### ML-KEM.KeyGen()

- The core subroutine of **ML-KEM.KeyGen** is the key generation algorithm of **K-PKE**.
- The ML-KEM encapsulation key is simply the encryption key of K-PKE.
- The ML-KEM decapsulation key is comprised of the 
    - decryption key of K-PKE, 
    - the encapsulation key, 
    - a hash of the encapsulation key, 
    - and a pseudorandom 32-byte value.

---

**ML-KEM.KeyGen()**
$Generates \: an \: encapsulation \: key \: and \: a \: corresponding \: decapsulation \: key$
$\mathbf{Output:}$ Encapsulation key $ek \in \mathbb{B}^{384k+32}$
$\mathbf{Output:}$ Decapsulation key $dk \in \mathbb{B}^{768k+96}$
01: $\mathcal{z} \leftarrow \mathbb{B}^{32}$ $\qquad$ **▷ $\mathcal{z}$ is 32 random bytes**
02: $(ek_{PKE}, \: dk_{PKE}) \leftarrow$ **K-PKE.KeyGen()**
03: $ek \leftarrow ek_{PKE}$ $\qquad\qquad\qquad\qquad$ **▷ KEM encaps key is just the PKE encryption key**
04: $dk \leftarrow (dk_{PKE}||\: ek||\: H(ek)||\: \mathcal{z})$ $\quad$**▷ KEM decaps key includes PKE decryption key**
05: $\mathbf{return} (ek, \: dk)$

---

## Encapsulation/Encryption

![LoadingMoneyGIF](https://hackmd.io/_uploads/BkKJhHLZeg.gif =10%x)

### K-PKE.Encrypt($ek_{PKE}$, $m$, $r$)
- The encryption algorithm **K-PKE.Encrypt** takes an encryption key $ek_{PKE}$, a 32-byte plaintext $m$, and randomness $r$ as input and produces a single output: a ciphertext $c$.
- The **K-PKE.Encrypt** begins by extracting the vector $t$ and the seed from the encryption key. The seed is the expanded to re-generate the matric $A$, in the same manner as was done in **K-PKE.KeyGen**.

---

**K-PKE.Encrypt($ek_{PKE}$, $m$, $r$)**
*$Uses\: the\: encryption\: key\: to\: encrypt\: a\: plaintext\: message\: using\: the\: randomness$ $r$*
$\mathbf{Input:}$ encryption key $ek_{PKE} \in \mathbb{B}^{384k+32}$
$\mathbf{Input:}$ message $m \in \mathbb{B}^{32}$
$\mathbf{Input:}$ randomness $r \in \mathbb{B}^{32}$
$\mathbf{Output:}$ cipher text $c \in \mathbb{B}^{32(d_uk+d_v)}$
01: $N \leftarrow 0$
02: $\mathbf{\hat{t}} \leftarrow ByteDecode_{12}(ek_{PKE}[0:384k])$ $\:\:$**▷ Run $ByteDecode_{12} k$ times to decode $\hat{t}$**
03: $\rho \leftarrow ek_{PKE}[384k:384K+32] \quad\quad\quad$ **▷ Extract 32-byte seed from $ek_{PKE}$**

04: $\mathbf{for}\:(i,\:j \leftarrow 0;\:i,\:j<k;\:i,\:j$++) $\quad\qquad$**▷ re-generate matrix $\mathbf{\hat{A}} \in (\mathbb{Z}^{256}_{q})^k$**
05: $\quad \mathbf{\hat{A}}[i,\:j] \leftarrow SampleNTT(XOF(\rho,\:i,\:j))$
06: $\mathbf{end\:for}$

07: $\mathbf{for}\:(i \leftarrow 0;\:i<k;\:i$++) $\qquad\qquad\qquad$ **▷ Generate $\mathbf{r} \in (\mathbb{Z}^{256}_{q})^k$**
08: $\quad \mathbf{r}[i] \leftarrow SamplePolyCBD_{\eta1}(PRF_{\eta_1}(r,\:N))$
09: $\quad N \leftarrow N+1$
10: $\mathbf{end\:for}$

11: $\mathbf{for}\:(i \leftarrow 0;\:i<k;\:i$++) $\qquad\qquad\qquad$ **▷ Generate $\mathbf{e_1} \in (\mathbb{Z}^{256}_{q})^k$**
12: $\quad e_1[i] \leftarrow SamplePolyCBD_{\eta2}(PRF_{\eta_2}(r,\:N))$
13: $\quad N \leftarrow N+1$
14: $\mathbf{end\:for}$

15: $e_2 \leftarrow SamplePolyCBD_{\eta_2}(PRF_{\eta_2}(r,\:N))$ $\:$ **▷ Sample $e_2 \in \mathbb{Z}^{256}_{q}$ from CBD**

16: $\mathbf{\hat{r}} \leftarrow NTT(\mathbf{r})$ $\qquad\qquad\qquad\quad\:\:$ **▷ Run $NTT\:k$ times**
17: $\mathbf{u} \leftarrow NTT^{-1}(\mathbf{\hat{A}}^T \circ \mathbf{\hat{r}}) + \mathbf{e_1} \quad\quad$ **▷ Run $NTT^{-1}\:k$ times**

18: $\mu \leftarrow Decompress_1(ByteDecode_1(m))$
19: $v \leftarrow NTT^{-1}(\hat{t}^T \circ \hat{r}) + e_2 + \mu$ $\quad$ **▷ encode plaintext $m$ into polynomial $v$**

20: $c_1 \leftarrow ByteEncode_{d_u}(Compress_{d_u}(\mathbf{u}))$
21: $c_2 \leftarrow ByteEncode_{d_v}(Compress_{d_v}(v))$

22: $\mathbf{return} \: c \leftarrow (c_1 || c_2)$

---

### ML-KEM.Encaps($ek$)

- The encapsulation algorithm **ML-KEM.Encaps** of ML-KEM accepts an encapsulation key as input, requires randomness, and outputs a ciphertext and a shared key.
- The core subroutine of **ML-KEM.Encaps** is the encryption algorithm of K-PKE, which is used to encrypt a random value $m$ into a ciphertext $c$.
- A copy shared secret $\mathbf{K}$ and the randomness used during encryption are derived from $m$ and the encapsulation key $ek$ via hashing
- $H$ is applied to $ek$, and the result is concatenated with $m$ and then hashed using $G$.
- The algorithm completes by outputting the ciphertext $c$ and the shared secret $\mathbf{K}$

---

**ML-KEM.Encaps($ek$)**
$Uses \: the \: encapsulation \: key \: to \: generate \: a \: shared \: key \: and \: an \: associated \: ciphertext$
$\mathbf{Validated \: Input:}$ encapsulation key $ek \in \mathbb{B}^{384k+32}$
$\mathbf{Output:}$ shared key $K \in \mathbb{B}^{32}$
$\mathbf{Output:}$ ciphertext $c \in \mathbb{B}^{32(d_uk+d_v)}$
01: $m \leftarrow \mathbb{B}^{32}$ $\qquad\qquad\qquad\qquad$ **▷ $m$ is 32 random bytes**
02: $(K, \: r) \leftarrow G(m || H(ek))$ $\qquad$ **▷ derive shared secret key $K$ and randomness $r$**
03: $c \leftarrow$ **K-PKE.Encrypt**($ek,\:m,\:r)$ $\:$ **▷ encrypt $m$ using K-PKE with randomness $r$**
04: $\mathbf{return} (K, \: c)$

---

## Decapsulation\Decryption

🔐

### K-PKE.Decrypt($dk_{PKE}, \: c$)
- Takes a decryption key $dk_{PKE}$ and a ciphertext $c$ as input, requires **no randomness**, and outputs a plaintext $m$.
- Think of $\mathbf{u}$: ($\mathbf{A}^Tr + e_1$) as the coefficients of the equation and $v$ as the constant term.
- The decryption algorithm can thus use the decryption key to compute the true constant term $v^{'} = \mathbf{s}^Tu$ and then calculate $v - v^{'}$.
- The decrpytion algorithm ends by decoding the plaintext message $m$ from $v - v^{'}$ and outputting $m$.

---

**K-PKE.Decrypt($dk_{PKE}, \: c$)**
*$Uses \: the \: decryption \: key \: to \: decrypt \: a \: ciphertext.$*
$\mathbf{Input:}$ decryption key $df_{PKE} \in \mathbb{B}^{384k}$
$\mathbf{Input:}$ ciphertext $c \in \mathbb{B}^{32(d_uk+d_v)}$
$\mathbf{Output:}$ message $m \in \mathbb{B}^{32}$
01: $c_1 \leftarrow c[0:32d_uk]$
02: $c_2 \leftarrow c[32d_uk : 32(d_uk + d_v)]$

03: $\mathbf{u} \leftarrow Decompress_{d_u}(ByteDecode_{d_u}(c_1))$ $\qquad$ **▷ $u = A^T \circ r$**
04: $v \leftarrow Decompress_{d_v}(ByteDecode_{d_v}(c_2))$ $\qquad$ **▷ $v = t^T \circ r + \mu = s^T \circ A^T \circ r + \mu$**
05: $\mathbf{\hat{s}} \leftarrow ByteDecode_{12}(dk_{PKE})$

06: $w \leftarrow v - NTT^{-1}(\mathbf{\hat{s}}^T \circ NTT(\mathbf{u}))$ $\quad$ **▷ $w = v - v^{'} = (s^TA^Tr + \mu) - (s^TA^Tr) = \mu$**
07: $m \leftarrow ByteEncode_1(Compress_1(w))$
08: $\mathbf{return}\:\: m$

---

### ML-KEM.Decaps($c,\:dk$)

- The decapsulation algorithm **ML-KEM.Decaps** of ML-KEM accepts a decapsulation key and a ML-KEM ciphertext as input, doesn't use any randomness, and outputs a shared secret.
- Begins by parsing out the components of the decapsulation key $dk$ of ML-KEM.
- These components are:
    - encryption key
    - decryption key
    - a hash value $h$
    - a random value $\mathcal{z}$
- The decryption key is then used to decrypt the input ciphertext $c$ to get a plaintext $m^{'}$ and computes a candidate shared secret key $\mathbf{K^{'}}$
- $\mathbf{K^{'}}$ and the encryption randomness $r^{'}$ are computed by hashing $m^{'}$ and the encryption key of K-PKE, and a ciphertext $c^{'}$ is generated by encrypting $m^{'}$ using randomness $r^{'}$.
- Finally, decapsulation checks whether the resulting ciphertext $c^{'}$ matches the provided ciphertext $c$. If not, the algorithm performs an "implicit rejection":
    - the value of $K^{'}$ is changed to a hash of $c$ together with the random value $\mathcal{z}$ stored in the ML-KEM secret key.

---

**ML-KEM.Decaps($c,\:dk$)**
$Uses \: the \: decapsulation \: key \: to \: produce \: a \: shared \: key \: from \: a \: ciphertext$
$\mathbf{Validated \: Input:}$ ciphertext $c \in \mathbb{B}^{32(d_uk+d_v)}$
$\mathbf{Validated \: Input:}$ decapsulation key $dk \in \mathbb{B}^{768k+96}$
$\mathbf{Output:}$ shared key $\mathbf{K} \in \mathbb{B}^{32}$
01: $dk_{PKE} \leftarrow dk[0:384k]$ $\qquad\qquad\qquad\quad$ **▷ Extract the PKE decryption key**
02: $ek_{PKE} \leftarrow dk[384k:768k+32]$ $\qquad\quad$ **▷ Extract the PKE encryption key**
03: $h \leftarrow dk[768k+32 : 768K+64]$ $\qquad\quad$ **▷ Extract the hash of PKE encryption key**
04: $\mathcal{z} \leftarrow dk[768k+64 : 768K+96]$ $\qquad\quad$ **▷ Extract the implicit rejection value**

05: $m^{'} \leftarrow$ **K-PKE.Decrypt**($dk_{PKE}, c)$ $\quad$ **▷ decrypt ciphertext**

06: $(\mathbf{K^{'}}, r^{'}) \leftarrow G(m^{'}||h)$
07: $\bar{K} \leftarrow J(\mathcal{z}||c, 32)$

08: $c^{'} \leftarrow$ **K-PKE.Encrypt**($ek_{PKE}, m^{'}, r^{'})$ $\:$ **▷ re-encrypt using the derived randomness $r^{'}$**

09: $\mathbf{if} c \neq c^{'} \mathbf{then}$
10: $\quad K^{'} \leftarrow \bar{K}$ $\qquad\qquad\qquad\qquad$ **▷ if ciphertext do not match, "implicitly reject""**
11: $\mathbf{end \: if}$
12: $\mathbf{return} \:\: \mathbf{K^{'}}$

---


## Parameter Set
|      | $n$ | $q$ | $k$ | $\eta_1$ | $\eta_2$ | $d_1$ | $d_2$ | $required\:RGB\:strength$ |
| ---- | --- | --- | --- | -------- | -------- | ----- | ----- | - |
| ML-KEM-512 | 256 | 3329 | 2 | 3 | 2 | 10 | 4 | 128-bit |
| ML-KEM-768 | 256 | 3329 | 3 | 2 | 2 | 10 | 4 | 192-bit |
| ML-KEM-1024 | 256 | 3329 | 4 | 2 | 2 | 11 | 5 | 256-bit |
- where $q$ is $2^8 * 13 + 1$


## Reference

- National Institute of Standards and Technology (2024) Module-Lattice-Based Key-Encapsulation Mechanism Standard. (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 203.
https://doi.org/10.6028/NIST.FIPS.203
