PDF Run this chapter's code LaTeX source Comments

Chapter 17Complete Implementation of ML-DSA (FIPS 204)

17.1Learning objectives#

The previous part of the book built up to FIPS 203, the real ML-KEM standard for encryption and key exchange. We now cross to the other half of public-key cryptography, digital signatures, and to the first of three signature standards: FIPS 204, ML-DSA, better known by its submission name Dilithium [1, 2].

After finishing this chapter, you should be able to:

1. explain what a signature scheme does and how it differs from a KEM;

2. follow the ML-DSA key generation flow and see that it reuses the module-lattice machinery of Kyber almost verbatim;

3. explain the two hard problems, Module-LWE and Module-SIS, and which part of the scheme each one protects;

4. follow the signing procedure phase by phase, and understand why it contains a rejection (“abort”) loop;

5. connect the rejection idea back to the role of noise studied in the LWE chapters.

17.2Review: how signing differs from ML-KEM#

ML-KEM answered the question how do two parties agree on a shared secret? A signature answers a different question: how does a verifier know that a message really came from the holder of a secret key, unchanged? The three algorithms mirror a KEM but serve this new goal:

• KeyGen \(\to\) a public verification key \(pk\) and a secret signing key \(sk\);

• Sign\((sk, M)\) \(\to\) a signature \(\sigma\) on a message \(M\);

• Verify\((pk, M, \sigma)\) \(\to\) accept or reject.

The security goal is unforgeability: even after seeing many valid signatures, nobody without \(sk\) can produce a valid signature on a new message. The remarkable fact is that ML-DSA achieves this on exactly the same ring \(R_q = \mathbb{Z}_q[x]/(x^{256}+1)\) and module structure we already built for Kyber. Only the modulus changes (\(q = 8380417\)), and the signing procedure is genuinely new.

17.3The two hard problems#

ML-DSA leans on two lattice problems in the module setting of Chapter 13.

• Module-LWE, already familiar: from \((A,\ \mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2)\) with short \(\mathbf{s}_1,\mathbf{s}_2\), recovering the secret is hard. This hides the signing key inside the public key.

• Module-SIS (Short Integer Solution): the module-lattice form of the SIS problem introduced in Section 11.7. Given a random \(A\), finding a short nonzero \(\mathbf{z}\) with \(A\mathbf{z}=\mathbf{0}\pmod q\) is hard. This blocks forgery: a forger would have to produce a short vector satisfying a public equation.

SIS is the mirror image of LWE. LWE hides a secret inside noise; SIS asks you to find a short solution to a random system. Both are hard for the same geometric reason – short vectors in a high-dimensional lattice are hard to find.

17.4The real input in FIPS 204#

Exactly as in FIPS 203, key generation does not begin by sampling a matrix. It begins with a single short seed: \[\xi \in \{0,1\}^{256}.\] Everything else – the public matrix, both secret vectors, and the internal PRF keys – is expanded deterministically from \(\xi\). Key generation is therefore a deterministic function \(\mathrm{KeyGen}(\xi)\), just like ML-KEM.

17.5Phase 1: expand the seed#

The seed is hashed by \(H\) (built on SHAKE-256) and split into three parts: \[(\rho,\ \rho',\ K) = H(\xi).\] Their roles are:

• \(\rho\) – public, expands into the matrix \(A\) (it will be stored in the public key);

• \(\rho'\) – secret, seeds the sampling of \(\mathbf{s}_1\) and \(\mathbf{s}_2\);

• \(K\) – secret, a PRF key used later to derive per-signature randomness.

17.6Phase 2: generate the matrix#

As in Kyber, the matrix is never stored; it is regenerated on demand from its seed: \[A = \text{E}{\small\text{XPAND}}\text{A}(\rho) \in R_q^{k\times \ell}.\] The dimensions \((k,\ell)\) are what distinguish the three security levels.

17.7Phase 3: sample the secret vectors#

The two short secrets are expanded from \(\rho'\): \[(\mathbf{s}_1,\ \mathbf{s}_2) = \text{E}{\small\text{XPAND}}\text{S}(\rho'),\qquad \mathbf{s}_1\in R_q^\ell,\ \mathbf{s}_2\in R_q^k,\] with coefficients in the small range \([-\eta,\eta]\). These play the role of the LWE secret and error.

17.8Phase 4: compute and split the public value#

The public value is the familiar Module-LWE equation: \[\mathbf{t} = A\mathbf{s}_1 + \mathbf{s}_2.\] To shrink the public key, \(\mathbf{t}\) is split into a high part \(\mathbf{t}_1\) (published) and a low part \(\mathbf{t}_0\) (kept in the secret key): \[\mathbf{t} = \mathbf{t}_1\cdot 2^{d} + \mathbf{t}_0.\] The public key is \((\rho, \mathbf{t}_1)\); the secret key bundles \((\rho, K, \mathbf{t}_0, \mathbf{s}_1, \mathbf{s}_2)\) together with a hash \(tr = H(pk)\) used during signing.

17.9Interlude: the Fiat–Shamir transform#

Before diving into ML-DSA’s signing, it is worth isolating the general technique it uses, because it is a basic building block that appears far beyond this one scheme.

An identification scheme lets a prover convince a verifier that it knows a secret \(s\) (whose public image is \(t\)), without revealing \(s\). It is a three-move conversation: the prover sends a commitment \(w\); the verifier replies with a random challenge \(c\); the prover sends a response \(z\) that only someone knowing \(s\) could produce, and the verifier checks a relation among \((w,c,z,t)\). If the response is properly randomized, the transcript reveals nothing about \(s\).

The Fiat–Shamir transform [3] turns this interactive protocol into a signature by removing the verifier. Instead of waiting for a random challenge, the prover computes the challenge itself as a hash of the commitment together with the message: \[c = H(w \,\|\, m).\] Because \(H\) behaves like an unpredictable random function, the prover cannot steer \(c\) to its advantage; and because \(c\) depends on \(m\), the whole transcript is bound to that message – it is a signature on \(m\).

17.10The signing idea: commitment, challenge, response#

Signing instantiates exactly that identification transcript, with the module-lattice objects playing the roles of commitment, challenge, and response:

1. Commit. Sample a random short masking vector \(\mathbf{y}\) and form \(\mathbf{w} = A\mathbf{y}\).

2. Challenge. First form the message representative \(\mu=H(tr\,\|\,M')\), where \(M'\) includes any context or pre-hash formatting. Then compute \(\tilde c=H(\mu\,\|\,\mathbf{w}_1)\) with \(\mathbf{w}_1=\text{H}{\small\text{IGH}}\text{B}{\small\text{ITS}}(\mathbf{w})\), and derive \(c=\text{S}{\small\text{AMPLE}}\text{I}{\small\text{N}}\text{B}{\small\text{ALL}}(\tilde c)\).

3. Respond. Reply with \(\mathbf{z} = \mathbf{y} + c\,\mathbf{s}_1\).

A verifier can then recompute \(A\mathbf{z} - c\,\mathbf{t}\) and check it matches \(\mathbf{w}\) in the high bits, because \[A\mathbf{z} - c\,\mathbf{t} = A(\mathbf{y}+c\,\mathbf{s}_1) - c(A\mathbf{s}_1+\mathbf{s}_2) = A\mathbf{y} - c\,\mathbf{s}_2 \approx \mathbf{w}.\] The leftover \(c\,\mathbf{s}_2\) is small, and the HighBits rounding absorbs it. Replacing the interactive verifier by the hash \(H\) is precisely the Fiat–Shamir transform: the hash acts as an unpredictable, unmanipulable challenger.

17.11Why signing must sometimes abort#

The response \(\mathbf{z} = \mathbf{y} + c\,\mathbf{s}_1\) carries the secret \(\mathbf{s}_1\) directly. If the mask \(\mathbf{y}\) is not large enough to swamp \(c\,\mathbf{s}_1\), then \(\mathbf{z}\) leaks information – across many signatures the mask averages out and the secret emerges. This is the LWE lesson in a new costume: the mask must completely hide the secret.

ML-DSA’s answer is rejection sampling, also called Fiat–Shamir with aborts. After forming \(\mathbf{z}\), the signer checks whether it lands in a safe region where its distribution is independent of \(\mathbf{s}_1\). If not, it discards everything, draws a fresh \(\mathbf{y}\), and retries. Only a leak-free \(\mathbf{z}\) is ever released.

17.12Signing and verification#

Bringing the phases together gives the signing algorithm. Two bounds mark the safe region: \(\|\mathbf{z}\|_\infty\) must stay below \(\gamma_1-\beta\), and the low bits of \(\mathbf{w}-c\mathbf{s}_2\) must stay below \(\gamma_2-\beta\). A hint \(\mathbf{h}\) compensates for the omitted \(\mathbf{t}_0\).

Verification recomputes the commitment from public data and checks the challenge hash matches, while also confirming \(\mathbf{z}\) is genuinely short – the short-vector check is what confronts a forger with Module-SIS.

Because \(A\mathbf{z} - c\,\mathbf{t} = A\mathbf{y} - c\mathbf{s}_2\) agrees with \(\mathbf{w}=A\mathbf{y}\) in its high bits, and the hint repairs the gap left by publishing only \(\mathbf{t}_1\), both sides hash to the same challenge exactly when the signature is genuine.

17.13Why a forger is stuck#

An attacker without \(sk\) may freely choose \(\mathbf{z}\) and \(c\), but to pass verification they must satisfy \(c = H(\mu\,\|\,\text{H}{\small\text{IGH}}\text{B}{\small\text{ITS}}(A\mathbf{z}-c\mathbf{t}))\) and keep \(\mathbf{z}\) short. Because \(H\) behaves like a random function, its output cannot be steered; the only route is to find a genuinely short \(\mathbf{z}\) consistent with the equation – a Module-SIS instance. And they cannot instead learn \(\mathbf{s}_1\) from public data, because that is Module-LWE. The two hard problems shut both doors at once.

17.14SageMath experiment#

The core cancellation is easy to verify in miniature. Using small parameters, sample a key, form a masked response, and confirm the verification identity holds before any signature is even released.

# Toy sizes; real ML-DSA uses n=256, q=8380417.
from random import Random
from sage.all import GF, Matrix, PolynomialRing, vector

q = 8380417
R.<x> = PolynomialRing(GF(q))
Rq = R.quotient(x^8 + 1)  # toy ring
rng = Random("mldsa-cancellation")

def small_poly():
    return Rq([rng.choice([-1, 0, 1]) for _ in range(8)])

def uniform_poly():
    return Rq([rng.randrange(q) for _ in range(8)])

A = Matrix(Rq, 2, 2, [uniform_poly() for _ in range(4)])
s1 = vector(Rq, [small_poly(), small_poly()])
s2 = vector(Rq, [small_poly(), small_poly()])
t = A * s1 + s2
y = vector(Rq, [uniform_poly(), uniform_poly()])
c = small_poly()
# For a mask y and challenge c, check the verifier's identity:
#   A*z - c*t  ==  A*y - c*s2   (should hold exactly)
z = y + c*s1
assert A*z - c*t == A*y - c*s2

Then repeat with several masks and count how often \(\|\mathbf{z}\|_\infty\) exceeds the bound: this is exactly the rejection rate, and it shows why a signature takes a small, variable number of attempts.

17.15A complete SageMath implementation#

The cancellation check above is a fragment. The companion file sage/fips204_mldsa.sage is the whole standard: all forty-nine numbered algorithms of FIPS 204, each as its own function annotated with its algorithm number, for ML-DSA-44, 65, and 87. That includes the parts this chapter has treated as black boxes – ExpandA, ExpandS, ExpandMask, SampleInBall, Power2Round, Decompose, MakeHint, UseHint – as well as the bit packing, the hint encoding, the pre-hash variants HashML-DSA, and Montgomery reduction.

Run it in a browser: key generation, signing and verification at ML-DSA-44, 65 and 87. See appliedpqc.io/playground.html — nothing to install.

As in FIPS 203 the algebra is carried by Sage. Here, though, the standard is careful to distinguish the ring \(R_q\) from the ring \(R\) of integer polynomials with a restricted coefficient range, and so is the code: quantities reduced modulo \(q\) (the secrets \(\mathbf{s}_1,\mathbf{s}_2\), the mask \(\mathbf{y}\), the response \(\mathbf{z}\)) live in the Sage quotient ring \(R_q = \mathbb{F}_{8380417}[X]/(X^{256}+1)\), while \(\mathbf{t}_1\), \(\mathbf{w}_1\), \(\mathbf{r}_0\), and the hint \(\mathbf{h}\) stay integer lists. The NTT domain \(T_q\) is the direct product \((\mathbb{Z}_q)^{256}\), so MultiplyNTT (Algorithm 45) is literally a coordinatewise product.

The rejection loop of Algorithm 21 then reads almost exactly as the standard writes it:

kappa = 0
while True:
    y  = self.ExpandMask(rhopp, kappa)
    yh = [NTT(Rq(p)) for p in y]
    w  = [NTTInverse(a) for a in MatrixVectorNTT(Ah, yh)]
    w1 = HighBitsVec(w, self.gamma2)

    ctilde = H(mu + self.w1Encode(w1), self.lam // 4)
    c      = self.SampleInBall(ctilde)
    ch     = NTT(Rq(c))

    cs1  = [NTTInverse(MultiplyNTT(ch, a)) for a in s1h]
    cs2  = [NTTInverse(MultiplyNTT(ch, a)) for a in s2h]
    z    = [Rq(y[i]) + cs1[i] for i in range(self.ell)]
    wcs2 = [w[i] - cs2[i] for i in range(self.k)]
    r0   = LowBitsVec(wcs2, self.gamma2)

    kappa += self.ell
    if inf_norm_vec(z) >= self.gamma1 - self.beta:      # unsafe: retry
        continue
    if inf_norm_ints(r0) >= self.gamma2 - self.beta:
        continue

    ct0 = [NTTInverse(MultiplyNTT(ch, a)) for a in t0h]
    h   = MakeHintVec([-p for p in ct0],
                      [wcs2[i] + ct0[i] for i in range(self.k)],
                      self.gamma2)
    if inf_norm_vec(ct0) >= self.gamma2:
        continue
    if sum(sum(p) for p in h) > self.omega:
        continue

    return self.sigEncode(ctilde, [centered(zi) for zi in z], h)

Every continue is one of the discarded attempts of Figure 17.3; counting them over many signatures reproduces the “repetitions” row of the parameter table, roughly four for ML-DSA-44. Note also that \(\kappa\) advances before the checks, so each retry draws a genuinely fresh mask.

Checking the transform against the algebra.#

The function verify_ntt_is_a_ring_isomorphism() at the end of sage/fips204_mldsa.sage – a namesake of the ML-KEM check of Chapter 16, but over a different ring – uses Sage to confirm that \(\mathrm{NTT}^{-1}\) inverts \(\mathrm{NTT}\); that the \(j\)-th NTT coefficient is the evaluation \(w(\zeta^{2\,\mathrm{BitRev8}(j)+1})\), which is what makes \(T_q\) a direct product; and that MultiplyNTT transports multiplication in \(R_q\) as Sage computes it. It also checks that MontgomeryReduce really returns \(a\cdot 2^{-32} \bmod q\).

Validation.#

The implementation is checked against NIST’s ACVP vectors [4] for FIPS 204 – key generation, signature generation, and signature verification – and reproduces them byte for byte. The signature-generation vectors are the demanding ones, because they cover every combination the standard permits: deterministic and hedged signing, the pure and pre-hash message encodings across all twelve approved pre-hash functions, the external and internal signing interfaces, and the external-\(\mu\) mode in which the message representative is computed in a separate cryptographic module. Run make kat from the latex/ directory.

17.16Pitfalls#

Pitfall 1: thinking the mask can be reused or made small.#

The mask \(\mathbf{y}\) must be fresh every attempt and large enough to hide \(c\,\mathbf{s}_1\). Reusing a mask, or shrinking it to avoid rejections, leaks the secret. This is the whole reason for the abort loop.

Pitfall 2: thinking the abort loop is a timing leak about the secret.#

The number of iterations depends on the mask, which is fresh randomness, not on the secret in an exploitable way. FIPS 204 derives the mask seed from \(K\,\|\,rnd\,\|\,\mu\): choosing a zero \(rnd\) gives deterministic signing, while a fresh \(rnd\) supports randomized or hedged signing.

Pitfall 3: thinking \(A\) is stored in the key.#

As in ML-KEM, \(A\) is regenerated from \(\rho\) every time. The public key is only \((\rho,\mathbf{t}_1)\).

17.17Parameter sets#

17.18Summary#

ML-DSA reuses the module-lattice world of Kyber and adds one genuinely new ingredient, Fiat–Shamir with aborts:

• key generation is a deterministic expansion from one seed \(\xi\), exactly like FIPS 203;

• a signature is a commitment–challenge–response transcript made non-interactive by hashing;

• the response \(\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1\) carries the secret, so it is released only when rejection sampling confirms it hides the secret completely;

• unforgeability rests on Module-LWE (hiding the key) and Module-SIS (blocking short-vector forgeries).

The next chapter stays with lattices but takes a very different route to a signature: FN-DSA (Falcon), which abandons Fiat–Shamir for a hash-and-sign construction over NTRU lattices and, in exchange, produces the most compact signatures of the three standards.

References