# 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