# FIPS-204 ML-DSA

**Module-Lattice-Based Digital Signature Standard**

- The signing, verifying, and key generation functions can be split into "external" and "internal" components to simplify APIs and Cryptographic Algorithm Validation Program (CAVP) testing.
- The external components generate randomness and perform various checks before calling their internal counterparts.
- The internal components are deterministic and can assume that the external components did not encounter error conditions.

## Key Generation

### External ML-DSA.KeyGen()

- The key generation takes no input and outputs a public key and a private key, which are both encoded as byte strings.
- The algorithm uses an **approved** RBG to generate a 256-bit(32-byte) random seed $\xi$ that is given as input to **ML-DSA.KeyGen_internal**, which produces the public and private keys.

---

**ML-DSA.KeyGen()**
$Generates \: a \: public-private \: key \: pair$
$\mathbf{Output:}$ Public key $pk \in \mathbb{B}^{32+32*(bitlen(q-1)-d)}$
$\qquad\qquad\:$ Private key $sk \in \mathbb{B}^{32+32+64+32*((l+k)*bitlen(2\eta)+dk)}$
01: $\xi \leftarrow \mathbb{B}^{32}$ $\qquad\qquad\qquad\qquad$ **▷ Choose random seed**
02: $\mathbf{if}\:\: \xi = NULL \:\: \mathbf{then}$
03: $\mathbf{return} \: \perp$ $\qquad\qquad\qquad\quad$ **▷ Return an error indication if RBG failed**
04: $\mathbf{end \: if}$
05: $\mathbf{return}$ **ML-DSA.KeyGen_internal($\xi$)**

---

### Internal ML-DSA.KeyGen_internal($\xi$)

- The internal key generation takes a 32-byte random reed as input and outputs a public key and a private key that are both encoded as byte strings.
- The seed $\xi$ is expanded as needed using an XOF denoted by $H$ to produce other random values.
- The core cryptographic operation computes the public value:
- $\mathbf{t = As_1 + s_2}$
- The vector $\mathbf{t}$ together with the matrix $\mathbf{A}$ may be considered an expanded form of the public key.

---

**ML-DSA.KeyGen_internal($\xi$)**
$Generates \: a \: public-private \: key \: pair \: from \: a \: seed$
$\mathbf{Input:}$ Seed $\xi \in \mathbb{B}^{32}$
$\mathbf{Output:}$ Public key $pk \in \mathbb{B}^{32+32*(bitlen(q-1)-d)}$
$\qquad\qquad\:$ Private key $sk \in \mathbb{B}^{32+32+64+32*((l+k)*bitlen(2\eta)+dk)}$
01: $(\rho,\rho^{'}, K) \in \mathbb{B}^{32}×\mathbb{B}^{64}×\mathbb{B}^{32} \leftarrow H(\xi||IntToBytes(k,1)||IntToBytes(l.1),128)$
02: **▷ Expand seed**
03: $\mathbf{\hat{A}} \leftarrow ExpandA(\rho)$ $\qquad$ **▷ A is generated and stored in NTT representation as $\mathbf{\hat{A}}$**
04: $(\mathbf{s_1},\mathbf{s_2}) \leftarrow ExpandS(\rho^{'})$
05: $\mathbf{t} \leftarrow NTT^{-1}(\mathbf{\hat{A}} \circ NTT(s_1)) + s_2$ $\qquad\qquad$ **▷ Compute $\mathbf{t = As_1 + s_2}$**
06: $(\mathbf{t_1}, \mathbf{t_0}) \leftarrow Power2Round(\mathbf{t})$ $\qquad\qquad\qquad$ **▷ Compress $\mathbf{t}$**
07: $pk \leftarrow pkEncode(\rho, \mathbf{t_1})$
08: $tr \leftarrow H(pk,\:64)$
09: $sk \leftarrow skEncode(\rho,\: K,\: tr,\: \mathbf{s_1},\: \mathbf{s_2},\: \mathbf{t_0})$ $\qquad$ **▷ $K$ and $tr$ are for use in signing**
10: $\mathbf{return}$ ($sk$, $pk$)

---

## Signature

### External ML-DSA.Sign($sk$, $M$, $ctx$)

- The signing algorithm takes a private key, a message, and a context string as input.
- It outputs a signature that is encoded as a byte string.
- The algorithm uses an **approved** RBG to generate a 256-bit(32-byte) random seed $rnd$.
- If the deterministic variant is desired, then $rnd$ is set to the fixed zero string $\{0\}^{32}$
- The value $rnd$, the private key, and the encoded message are input to **ML-DSA.Sign_internal**, which produces the signature.

---

**ML-DSA.Sign($sk$, $M$, $ctx$)**
$Generates \: an$ **ML-DSA** $signature.$
$\mathbf{Input:}$ Private key $sk \in \mathbb{B}^{32+32+64+32*((l+k)*bitlen(2\eta)+dk)}$, message $M \in \{0,1\}^*$, context string $ctx$ (a byte string of 255 or fewer bytes).
$\mathbf{Output:}$ Signature $\sigma \in \mathbb{B}^{\lambda/4+l*32*(1+bitlen(\gamma_1-1))+\omega+k}.$
01: $\mathbf{if}$ |$ctx$| $>255$ $\mathbf{then}$
02: $\quad$ $\mathbf{return}$ $\perp$ $\qquad\qquad$ **▷ Return an error indication if the context string is too long**
03: $\mathbf{end \:\: if}$

04: $rnd \leftarrow \mathbb{B}^{32}$ $\:\:\:\:\qquad$ **▷ for the optional deterministic variant, substiture $rnd \leftarrow \{0\}^{32}$**

06: $\mathbf{if}$ $rnd$ $=NULL$ $\mathbf{then}$
07: $\quad$ $\mathbf{return}$ $\perp$ $\qquad\qquad$ **▷ Return an error indication if random bit generation failed**
08: $\mathbf{end \:\: if}$

09: $M^{'} \leftarrow BytesToBits(IntToBytes(0,1)\:||\:IntToBytes(|ctx|,1)\:||\:ctx)\:||\:M$
10: $\sigma \leftarrow$ **ML-DSA.Sign_internal($sk$, $M^{'}$, $rnd$)**
11: $\mathbf{return}$ $\:\sigma$

---

### Internal ML-DSA.Sign_internal($sk$, $M^{'}$, $rnd$)

- Outputs a signature encoded as a byte string.
- It takes a private key $sk$ encoded as a byte string, a formatted message $M^{'}$ encoded as a bit string, and a 32-byte string $rnd$ as input.
- There are 2 ways that a signing algorithm can use **ML-DSA.Sign_internal**: "hedged" and "deterministic". The default "hedged" variants of **ML-DSA.Sign** and **HashML-DSA.Sign** use a fresh random value for $rnd$, while the optional deterministic variants use the constant byte string $\{0\}^{32}$.
- The signer first extracts the following from the private key:
- the public random seed $\rho$
- the 32-byte private random seed $K$
- the 64-byte hash of the public key $tr$
- the secret polynomial vectors $\mathbf{s_1}$ and $\mathbf{s_2}$
- the polynomial vector $\mathbf{t_0}$ encoding the $d$ least significant bits of each coefficient of the uncompressed public-key polynomial $\mathbf{t}$
- $\rho$ is then expanded to the same matrix $\mathbf{A}$ as in key generation.
- **The main part of the signing algorithm** consists of a rejection sampling loop in which each iteration of the loop either **produces a valid signature or an invalid signature** whose release would leak information about the private key.
- The loop is repeated until a valid signature is produced, which can then be encoded as a byte string and output.
- The signer first produces a "commitment" $\mathbf{w}_1$ and then pseudorandomly derives a "challenge" $c$ from $\mathbf{w}_1$ and the message representative $\mu$.
- Finally, the signer computes a response $\mathbf{z} = \mathbf{y}+c\mathbf{s}_1$.
- If the check pass, the signer can compute the hint polynomial $\mathbf{h}$, which allow the verifier to reconstruct $\mathbf{w}_1$.
- The signer will then output the final signature, which is a byte encoding of the commitment hash $\tilde{c}$, the response $\mathbf{z}$, and the hint $\mathbf{h}$.

---

**ML-DSA.Sign_internal($sk$, $M^{'}$, $rnd$)**
$Deterministic \: algorithm \: to \: generate \: a \: signature \: for \: a \: formatted \: message \: M^{'}.$
$\mathbf{Input:}$ Private key $sk \in \mathbb{B}^{32+32+64+32*((l+k)*bitlen(2\eta)+dk)}$, formatted messgage $M^{'}\in \{0,1\}^{*}$, and per message randomness or dummy variable $rnd \in \mathbb{B}^{32}$
$\mathbf{Output:}$ Signature $\sigma \in \mathbb{B}^{\lambda/4+l*32*(1+bitlen(\gamma_1-1))+\omega+k}$
01: $(\rho, K, tr, \mathbf{s_1}, \mathbf{s_2}, \mathbf{t_0}) \leftarrow skDecode(sk)$
02: $\mathbf{\hat{s_1}} \leftarrow NTT(\mathbf{s_1})$
03: $\mathbf{\hat{s_2}} \leftarrow NTT(\mathbf{s_2})$
04: $\mathbf{\hat{t_0}} \leftarrow NTT(\mathbf{t_0})$
05: $\mathbf{\hat{A}} \leftarrow ExpandA(\rho)$ $\quad$ **▷ $\mathbf{A}$ is generated and stored in NTT representation as $\mathbf{\hat{A}}$**
06: $\mu \leftarrow H(BytesToBits(tr)\:||\:M^{'},\:64)$ $\qquad$ **▷ message representative**
07: $\rho^{''} \leftarrow H(K\:||\:rnd\:||\:\mu,\:64)$ $\qquad\qquad\qquad$ **▷ compute private random seed**
08: $\kappa \leftarrow 0$ $\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ **▷ initialize counter $\kappa$**
09: $(\mathbf{z},\mathbf{h}) \leftarrow \perp$
10: $\mathbf{while}$ $(\mathbf{z},\mathbf{h}) = \perp$ $\mathbf{do}$ $\qquad\qquad\qquad\qquad$ **▷ rejection sampling loop**
11: $\quad \mathbf{y} \in R^l_q \leftarrow ExpandMask(\rho^{''}, \kappa)$
12: $\quad \mathbf{w} \leftarrow NTT^{-1}(\mathbf{\hat{A}} \circ NTT(\mathbf{y}))$ $\quad\qquad\quad$ **▷ $w = Ay$**
13: $\quad \mathbf{w_1} \leftarrow HighBits(\mathbf{w})$ $\qquad\qquad\qquad\quad$ **▷ signer's commitment**
14: $\quad \tilde{c} \leftarrow H(\mu \: ||\: w1Encode(\mathbf{w_1})\:,\: \lambda/4)$ $\qquad$ **▷ commitment hash**
15: $\quad c \in R_q \leftarrow SampleInBall(\tilde{c})$ $\qquad\qquad$ **▷ verifier's challenge**
16: $\quad \hat{c} \leftarrow NTT(c)$
17: $\quad \langle\langle c\mathbf{s_1} \rangle\rangle \leftarrow NTT^{-1}(\hat{c} \circ \mathbf{\hat{s_1}})$
18: $\quad \langle\langle c\mathbf{s_2} \rangle\rangle \leftarrow NTT^{-1}(\hat{c} \circ \mathbf{\hat{s_2}})$
19: $\quad \mathbf{z} \leftarrow \mathbf{y} + \langle\langle c\mathbf{s_1} \rangle\rangle$ $\qquad\qquad\qquad\qquad\quad$ **▷ Signer's response: $\mathbf{z} = \mathbf{y}+c\mathbf{s_1}$**
20: $\quad r_0 \leftarrow LowBits(\mathbf{w}- \langle\langle c\mathbf{s_2} \rangle\rangle)$
21: $\quad \mathbf{if}$ $||\mathbf{z}||_{\infty} \ge \gamma_1 - \beta$ $\mathbf{or}$ $||r_0||_{\infty} \ge \gamma_2 - \beta\:$ $\mathbf{then}$ $(\mathbf{z}, \mathbf{h}) \leftarrow \perp$ **▷ validity checks**
22: $\quad \mathbf{else}$
23: $\quad\quad \langle \langle c \mathbf{t_0} \rangle\rangle \leftarrow NTT^{-1}(\hat{c} \circ \mathbf{\hat{t_0}})$
24: $\quad\quad \mathbf{h} \leftarrow MakeHint(-\langle\langle c\mathbf{t_0} \rangle\rangle, \mathbf{w} - \langle\langle c\mathbf{s_2} \rangle\rangle + \langle\langle c\mathbf{t_0} \rangle\rangle)$ $\qquad$ **▷ Signer's hint**
25: $\quad\quad \mathbf{if} \: ||\langle\langle c\mathbf{t_0} \rangle\rangle ||_{\infty} \ge \gamma_2$ $\mathbf{or}$ the number of 1's in $\mathbf{h} > \omega$, $\mathbf{then} \:(\mathbf{z, h}) \leftarrow \perp$
26: $\quad\quad \mathbf{end \: if}$
27: $\quad \mathbf{end \: if}$
28: $\quad \kappa \leftarrow \kappa + l$
29: $\mathbf{end \: while}$
30: $\sigma \leftarrow sigEncode(\tilde{c},\mathbf{z}\:mod^{\pm}\:q,\:\mathbf{h})$
31: $\mathbf{return}\:\: \sigma$

---

## Verify

### External ML-DSA.Verify($pk$, $M$, $\sigma$, $ctx$)

- The verification algorithm takes a public key, a message, a signature, and a context string as input.
- Outputs a Boolean value that is true if the signature is valid
- The verification is accomplished by calling **ML-DSA.Verify_internal** with the public key, the encoded message, and the signature.

---

**ML-DSA.Verify($pk$, $M$, $\sigma$, $ctx$)**
$Verifies \: a \: signature \: \sigma \: for \: a \: message \: M$
$\mathbf{Input:}$ Public key $pk \in \mathbb{B}^{32+32*(bitlen(q-1)-d)}$, message $M \in \{0,1\}^{*}$, signature $\sigma \in \mathbb{B}^{\lambda/4+l*32*(1+bitlen(\gamma_1-1))+\omega+k}$, context string $ctx$ (a byte string of 255 or fewer)
$\mathbf{Output:}$ Boolean
01: $\mathbf{if}$ $|ctx| > 255$ $\mathbf{then}$
02: $\quad \mathbf{return}\: \perp$
03: $\mathbf{end\:if}$
04: $M^{'} \leftarrow ByteToBits(IntToBytes(0,\:1)\:||\:IntToBytes(|ctx|,\:1)\:||\:ctx)\:||\:M$
05: $\mathbf{return}$ **ML-DSA.Verify_internal($pk, M^{'}, \sigma$)**

---

### Internal ML-DSA.Verify_internal($pk$, $M^{'}$, $\sigma$)

- Takes a public key $pk$ encoded as a byte string, a message $m$ encode as a bit string, and a signature $\sigma$ encoded as a byte string as input.
- No randomness is requires for **ML-DSA.Verify_internal**.
- The verifier attempts to reconstruct the signer's commitment ($\mathbf{w_1}$) from the public key $pk$ and the signature $\sigma$.
- $\mathbf{w_1}$ is computed by rounding $\mathbf{w = Ay}$
- In **ML-DSA.Verify_internal**, the reconstructed value of $w_1$ is called $w_1^{'}$ since it may have been computed in a different way if the signature is invalid.
- The $w_1^{'}$ is computed through the following process:
1. Derive the challenge polynomial $c$ from the signer's commitment hash $\tilde{c}$, as similarly is done in **ML-DSA.Sign_internal**
2. Use the signer's response $\mathbf{z}$ to compute
- $\mathbf{w}^{'}_{Approx}=\mathbf{Az}-c\mathbf{t_1}*2^d$
- Assuming the signature was computed correctly, it follows that
- $\mathbf{w}=\mathbf{Ay}=\mathbf{Az}-c\mathbf{t}+c\mathbf{s_2} \approx\mathbf{w}^{'}_{Approx}=\mathbf{Az}-c\mathbf{t_1}*2^d$
- because $c$ and $\mathbf{s_2}$ have small coefficients, and $\mathbf{t_1}*2^d \approx \mathbf{t}$
3. Use the signer's hint $\mathbf{h}$ to obtain $\mathbf{w_1}^{'}$ from $\mathbf{w_1}^{'}_{Approx}$.
- Finally, the verifier chechs that the signer's response $\mathbf{z}$ and the signer's hint $\mathbf{h}$ are valid and that the reconstructed $\mathbf{w_1}^{'}$ is consistent with the signer's commitment hash $\tilde{c}$.
- More precisely, the verifier checks that
1. all of the coefficients of $\mathbf{z}$ are sufficiently small in range ($-(\gamma_1-\beta$), $\gamma_1-\beta$)),
2. $\mathbf{h}$ contains no mroe than $\omega$ nonzero coefficients,
3. $\tilde{c}$ matches the hash $\tilde{c}^{'}$ of the message representative $\mu$ concatenated with $\mathbf{w_1}^{'}$.

---

**ML-DSA.Verify_internal($pk$, $M^{'}$, $\sigma$)**
$Internal \: function \: to \: verify \: a \: signature \: \sigma \: for \: a \: formatted \: message \: M^{'}$
$\mathbf{Input:}$ Public key $pk \in \mathbb{B}^{32+32*(bitlen(q-1)-d)}$, message $M^{'} \in \{0,1\}^{*}$
$\mathbf{Input:}$ Signature $\sigma \in \mathbb{B}^{\lambda/4+l*32*(1+bitlen(\gamma_1-1))+\omega+k}$
$\mathbf{Output:}$ Boolean
01: $(\rho, \mathbf{t_1}) \leftarrow pkDecode(pk)$
02: $(\tilde{c}, \mathbf{z, h}) \leftarrow sigDecode(\sigma)$ $\quad$ **▷ signer's commitment hash $\tilde{c}$, response $\mathbf{z}$, and hint $\mathbf{h}$**
03: $\mathbf{if\:h}=\perp\:\mathbf{then\:return} \: false \:\mathbf{end\:if}$
04: $\mathbf{\hat{A}} \leftarrow ExpandA(\rho)$ $\qquad$ **▷ $\mathbf{A}$ is generated and stored in NTT representation as $\mathbf{\hat{A}}$**
05: $tr \leftarrow H(pk,64)$
06: $\mu \leftarrow (H(BytesToBits(tr)\:||\:M^{'},\:64))$
07: $c \in R_q \leftarrow SampleInBall(\tilde{c})$ $\qquad\qquad\qquad$ **▷ compute verifier's challenge from $\tilde{c}$**
08: $\mathbf{w}^{'}_{Approx} \leftarrow NTT^{-1}(\mathbf{\hat{A}} \circ NTT(\mathbf{z}) - NTT(c) \circ NTT(\mathbf{t_1}*2^d))$ <br>$\:\quad$ **▷ $\mathbf{w}^{'}_{Approx}=\mathbf{Az}-c\mathbf{t_1}*2^d$**
09: $\mathbf{w}^1 \leftarrow UseHint(\mathbf{h, w}^{'}_{Approx})$ $\qquad\qquad$ **▷ reconstruction of signer's commitment**
10: $\tilde{c}^{'} \leftarrow H(\mu\:||\:w1Encode(\mathbf{w}^{'}_1), \lambda/4)$ $\qquad\qquad\qquad\:\:$ **▷ hash it; this should match $\tilde{c}$**
11: $\mathbf{return}\:[[\:||\mathbf{z}||_{\infty}<\gamma_1-\beta]] \:\mathbf{and}\:[[\tilde{c}=\tilde{c}^{'}]]$

---

## Parameter Set

**$q$ - modulus**: $2^{23} - 2^{13} + 1 = 8380417$