Chapter 12: ML-DSA (FIPS 204) from scratch
ML-DSA can be read as a Schnorr identification scheme (Chapter 33) moved to the Module-LWE setting from Chapter 9, compiled into a signature by the Fiat-Shamir transform, and made safe to publish by rejection sampling (Fiat & Shamir, 1987; National Institute of Standards and Technology, 2024; Schnorr, 1991). It standardizes the CRYSTALS-Dilithium scheme (Ducas et al., 2018). The secret is a short module vector ; the public key is a Module-LWE sample . A signature proves knowledge of by answering a challenge with the response , where is a fresh random mask.
The response would leak if published directly, because its distribution depends on the secret. Lyubashevsky’s fix is to reject any that falls outside a fixed box and restart with a fresh mask, so the distribution of every that is actually output is independent of (Lyubashevsky, 2009, 2012). That rejection step is the “with aborts” in Fiat-Shamir with aborts.
The chapter builds the whole construction at the ML-DSA-65 parameter set specified in FIPS 204 (National Institute of Standards and Technology, 2024), and its output matches the NIST ACVP test vectors byte-for-byte. That second claim is an implementation result rather than anything the standard reports: tests/ch12/test_vectors.py checks it at all three parameter sets against fixtures vendored from NIST’s ACVP-Server repository. Where ML-KEM (Chapter 11) rests on Module-LWE alone, ML-DSA rests on two assumptions: Module-LWE protects the secret key, and Module-SIS protects against forgery. Chapter 13 builds the lattice cryptanalysis behind the first of those two, working the primal and dual attacks on Module-LWE and the block-size-to-category estimator against ML-KEM’s instances. The same machinery prices the Module-LWE half of this chapter’s table.
Signatures as Fiat-Shamir with aborts
Section titled “Signatures as Fiat-Shamir with aborts”The public key is a single Module-LWE sample. KeyGen draws a short secret and a short error , expands a public matrix from a seed, and publishes . Recovering from is the Module-LWE problem from Chapter 9 (Langlois & Stehlé, 2015). So far this is the ML-KEM key equation with the roles renamed.
The signature is an identification proof turned non-interactive. The signer commits to a fresh mask by publishing the high bits of , derives a challenge by hashing the commitment together with the message (the Fiat-Shamir step), and responds with . A verifier who knows can check the response: , which has the same high bits as when is small. Matching high bits recomputes the same challenge, and the proof closes.
Two problems stand between that sketch and a secure signature, and the ML-DSA machinery exists to solve them.
First, leaks the secret. Over a prime-order group, Schnorr hides the secret by drawing the mask uniformly modulo the group order, so the response is uniform regardless of the secret (Schnorr, 1991). A lattice has no such uniform mask: is drawn from a bounded box, and is a shifted box whose position depends on . Rejection sampling removes the dependence. The signer draws uniformly from , computes , and outputs it only when every coefficient lands in the smaller box , where bounds the infinity norm of . Inside that smaller box the distribution of is exactly uniform and carries no information about (Lyubashevsky, 2012). A response outside the box is discarded and the signer restarts with a fresh mask. The number of restarts is public; the discarded values are secret.
Second, publishing in full makes the public key large, so ML-DSA drops the low bits of every coefficient and ships only the top part . That truncation breaks the clean check , because the verifier now knows only , not . The signer repairs the gap with a one-bit-per-coefficient hint that tells the verifier how the missing low part shifts the high bits of the recomputed commitment. The hint is the MakeHint / UseHint mechanism, and it is what most distinguishes ML-DSA’s algebra from ML-KEM’s.
The rest of the chapter builds these pieces: the rounding and hint algebra, the samplers that draw , , , , and , the full NTT, and the KeyGen, Sign, and Verify assembly. Forgery without the secret means producing a short and a matching that satisfy the verification equation, which the scheme’s analysis states as SelfTargetMSIS, a Module-SIS-shaped problem over the lattice defined by that also involves the hash function (Ducas et al., 2018, sec. 4.1; National Institute of Standards and Technology, 2024, sec. 3.2). The two assumptions are separate: Module-LWE hides the key, Module-SIS blocks the forgery.
A concrete ML-DSA-65 parameter and seed derivation
Section titled “A concrete ML-DSA-65 parameter and seed derivation”FIPS 204 fixes three parameter sets over one ring. The ring constants and are the same in all three. What varies is the module shape and the bounds that ride on it (National Institute of Standards and Technology, 2024).
| Parameter | ML-DSA-44 | ML-DSA-65 | ML-DSA-87 |
|---|---|---|---|
| , dimensions of | |||
| , secret coefficient bound | |||
| , nonzero coefficients in | |||
| , mask bound | |||
| , low-order window | |||
| , hint budget | |||
| , collision strength of | |||
| , box margin | |||
| Public key, bytes | |||
| Secret key, bytes | |||
| Signature, bytes | |||
| Claimed NIST category | 2 | 3 | 5 |
This chapter builds the middle set throughout. Every byte length in the table is fixed by the parameter set rather than chosen. The block below computes all three of ML-DSA-65’s from the packing widths that FIPS 204 §7.2 gives its encoders, and reproduces that column’s three byte-size entries exactly.
A concrete instantiation at NIST ACVP key-generation test case fixes the seed and reproduces the exact byte lengths. This block derives the three sub-seeds that KeyGen splits out of the master seed; it does not run a full key generation, which the construction below builds up to.
import hashlib
# ML-DSA-65 parameters (FIPS 204 Table 1; n is the ring degree, from Section 2.4.1).n, q, d = 256, 8380417, 13k, l, eta = 6, 5, 4gamma_1, omega, lam = 1 << 19, 55, 192
# Bit widths that drive the packed lengths (FIPS 204 Section 7.2 encoders).t1_bits = (q - 1).bit_length() - d # 23 - 13 = 10eta_bits = (2 * eta).bit_length() # bitlen(8) = 4gamma1_bits = (2 * gamma_1 - 1).bit_length() # 20
# Derived byte lengths (FIPS 204 Table 2), computed rather than hard-coded.c_tilde_len = lam // 4pk_len = 32 + 32 * t1_bits * ksk_len = 32 + 32 + 64 + 32 * eta_bits * (k + l) + 32 * d * ksig_len = c_tilde_len + 32 * gamma1_bits * l + omega + k
# NIST ACVP ML-DSA-65 keyGen test case tcId = 26 seed.xi = bytes.fromhex( "A991FD42B071D49C48AE3E75C647459E0DAAD1E1BA356A04801912D3294BCFF8")
# The KeyGen seed expansion: H(xi || k || l) split into (rho, rho', K).raw = hashlib.shake_256(xi + bytes([k]) + bytes([l])).digest(128)rho, rho_prime, K = raw[:32], raw[32:96], raw[96:128]
print("pk_len =", pk_len)print("sk_len =", sk_len)print("sig_len =", sig_len)print("c_tilde_len =", c_tilde_len)print("rho[:8] =", rho[:8].hex())print("rho'[:8] =", rho_prime[:8].hex())print("K[:8] =", K[:8].hex())# ==> pk_len = 1952# ==> sk_len = 4032# ==> sig_len = 3309# ==> c_tilde_len = 48# ==> rho[:8] = 36db0b5dce98bd19# ==> rho'[:8] = 3a443ee0b259e6e5# ==> K[:8] = 33824e8fa472beadEvery Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch12/, one file per block. Appendix C covers the clone and the environment they run on.
The key generator takes the -byte seed and applies to the concatenation , squeezing bytes. The single bytes and are a domain separator equal to the module dimensions. FIPS 204 added them in the final standard, so a key generated under the earlier public draft differs (National Institute of Standards and Technology, 2024). The first bytes become the matrix seed , the next bytes the noise seed , and the last bytes the signing seed . The seed becomes the first bytes of the public key verbatim, so the derived here matches the leading bytes of the ACVP public key for this test case. KeyGen and the sign and verify paths are checked against the NIST vectors by pytest tests/ch12/test_vectors.py. The fixtures live at tests/ch12/vectors/ml_dsa_{44,65,87}_acvp.json, vendored from the NIST ACVP-Server repository with the source commit pinned in each file.
The ML-DSA math preliminaries
Section titled “The ML-DSA math preliminaries”Six objects recur: the ring and its full NTT, the Module-LWE and Module-SIS problems, Power2Round for public-key compression, Decompose for the high-bit commitment, the hint identity that ties MakeHint to UseHint, and the norm bounds that drive rejection.
The ring at . The ring is . The modulus is prime (National Institute of Standards and Technology, 2024). Unlike ML-KEM’s , this satisfies : is divisible by , so has a primitive -th root of unity, and FIPS 204 fixes as the one ML-DSA uses. The polynomial therefore factors into distinct linear terms over ,
so the NTT is a full transform: a polynomial maps to independent scalars, and the ring product becomes coefficient-wise multiplication. This is the structural difference from ML-KEM, whose admits only a primitive -th root and leaves the ring split into quadratic factors that need a base-case multiply. ML-DSA’s larger buys the simpler transform.
Module-LWE and Module-SIS. Chapter 9 introduced Module-LWE as the problem between Ring-LWE and flat LWE (Langlois & Stehlé, 2015). ML-DSA’s key equation is a Module-LWE sample at dimensions : the secret and error are short, is uniform, and the public value is . Recovering the secret is Module-LWE.
Forgery is the dual problem. A forger who does not know must produce a short and a challenge satisfying the verification relation, which amounts to finding a short nonzero solution to a homogeneous linear system over built from and . Finding short solutions to such a system is a Module-SIS (Short Integer Solution) problem, whose worst-case hardness traces to Ajtai’s reduction for the unstructured case and to the module-lattice reductions of Langlois and Stehlé for the structured one (Ajtai, 1996; Langlois & Stehlé, 2015). The two assumption families are independent, and ML-DSA needs both. The three parameter sets scale both problems by the module dimensions while the ring stays fixed.
Power2Round: dropping the low bits of the public key. Power2Round splits a coefficient into a high part and a low part around a power of two (Algorithm 35 in National Institute of Standards and Technology, 2024). Writing for the centered residue in , it returns with . Applied coefficient-wise to , it produces (shipped in the public key) and (kept in the secret key). At the public key stores bits per coefficient instead of , which is where most of the public key’s size reduction comes from. The centered residue is the reduction with representatives in rather than . It is the norm-minimizing representative and the one every ML-DSA bound is stated against.
Decompose and the high-bit commitment. Decompose is the same split around a different modulus (Algorithm 36 in National Institute of Standards and Technology, 2024). It returns with and , except at the top boundary , where it sets and so that stays in . and are the two outputs. The signer commits to of the mask product . The window is chosen so the high part takes few enough values to hash compactly. At ML-DSA-65, , so each high coefficient is one of values and packs into bits.
The hint identity. The verifier recomputes an approximation to but is off by the truncation term , which it cannot compute because the public key does not carry . FIPS 204 §6.1 is explicit that dropping those bits is a performance optimization rather than a security one, and that the low-order bits can be reconstructed from a small number of signatures and need not be regarded as secret (National Institute of Standards and Technology, 2024). MakeHint records, one bit per coefficient, whether adding a perturbation changes the high bits of ; UseHint applies that bit to recover the corrected high bits (Algorithms 39 and 40 in National Institute of Standards and Technology, 2024). The governing identity is
The bound is why a single bit suffices: within the window, adding can move the high part by at most , so one bit of “did the high part change, and in which direction” is complete information, with the direction read from the sign of . Sign enforces by rejection so this bound always holds on the term the hint corrects. The identity is verified over random pairs in the rounding code block below and pinned by tests/ch12/test_mldsa_rounding.py.
Norm bounds and rejection. ML-DSA works with the infinity norm on centered representatives. The challenge has exactly coefficients equal to and the rest zero, so (each output coefficient is a signed sum of at most secret coefficients, each bounded by ). This is the box margin. The signer accepts only when , so the shifted box stays inside regardless of the secret. It accepts only when , so the low part of cannot cross a high-bit boundary. At ML-DSA-65, . Those two rejection tests are the abort condition, and the expected number of restarts follows from the fraction of the box they cut off (Ducas et al., 2018; Lyubashevsky, 2012).
Step-by-step construction
Section titled “Step-by-step construction”The construction walks from the byte-level primitives outward to KeyGen, Sign, and Verify. The inline blocks use numpy and hashlib only so they run standalone. The full implementation is at solutions/ch12-mldsa/. The final assembly block imports that package to run an end-to-end signature, because the KeyGen, Sign, and Verify routines are too large to reproduce inline in full.
Serialization: SimpleBitPack and BitPack
Section titled “Serialization: SimpleBitPack and BitPack”Every polynomial ML-DSA puts on the wire is a little-endian bit-packing of a length- coefficient vector at a field-specific width (National Institute of Standards and Technology, 2024, sec. 7.1). Not everything on the wire is a polynomial. The object encoders build a public key as the raw seed followed by the packed . A signature is the raw challenge bytes , then the packed , then a hint encoding (National Institute of Standards and Technology, 2024, sec. 7.2). The hint is the exception on the polynomial side too, since writes the positions of the nonzero coefficients rather than a fixed-width field for every coefficient. Two primitives do the packing. packs unsigned coefficients in using bits each. packs signed coefficients in by storing the unsigned value in bits. Both lay coefficient into bit positions of one big integer and emit it with int.to_bytes(..., "little"), the same idiom the ML-KEM serializer used at .
import numpy as np
def bitlen(m): return m.bit_length()
def bit_pack(w, a, b): width = bitlen(a + b) mask = (1 << width) - 1 big = 0 for i in range(256): big |= ((b - int(w[i])) & mask) << (i * width) return big.to_bytes(32 * width, "little")
def bit_unpack(v, a, b): width = bitlen(a + b) big = int.from_bytes(v, "little") mask = (1 << width) - 1 return np.array([b - ((big >> (i * width)) & mask) for i in range(256)], dtype=np.int64)
# The response z packs at (a, b) = (gamma_1 - 1, gamma_1) for ML-DSA-65,# so each coefficient uses bitlen(2*gamma_1 - 1) = 20 bits.gamma_1 = 1 << 19rng = np.random.default_rng(seed=20260723)z = rng.integers(-(gamma_1 - 1), gamma_1 + 1, size=256, dtype=np.int64)packed = bit_pack(z, gamma_1 - 1, gamma_1)recovered = bit_unpack(packed, gamma_1 - 1, gamma_1)print("bits per coefficient =", bitlen(2 * gamma_1 - 1))print("packed length =", len(packed))print("round trip equal =", bool(np.array_equal(recovered, z)))# ==> bits per coefficient = 20# ==> packed length = 640# ==> round trip equal = TrueThe stored value maps the signed range onto the unsigned range so the packer never has to encode a sign bit, and bit_unpack inverts it by subtracting from . The signature’s response vector has polynomials at bits each, giving bytes, the bulk of the -byte signature. The hint has its own sparse format, HintBitPack, which lists the set positions poly by poly followed by cumulative end markers. Its decoder is the one serializer that can reject, returning FIPS 204’s when the positions are not strictly increasing, an end marker is out of range, or an unused slot is nonzero. That rejection is what makes a tampered-hint signature fail verification, and it is exercised by tests/ch12/test_mldsa_encode.py.
Hash derivations from a single SHAKE
Section titled “Hash derivations from a single SHAKE”ML-DSA uses only SHAKE and does not need ML-KEM’s zoo of , , PRF, XOF, and (National Institute of Standards and Technology, 2024, sec. 3.7). SHAKE-256 is the general hash , called with whatever output length a step needs, and SHAKE-128 is the extendable output used to grow the public matrix. Every derivation is one call to on a domain-separated byte string: the KeyGen seed split, the public-key transcript , the message representative , the per-signature mask seed , and the challenge hash .
import hashlib
def H(data, outlen): return hashlib.shake_256(data).digest(outlen)
def integer_to_bytes(x, length): return x.to_bytes(length, "little")
# ML-DSA-65 module shape.k, l = 6, 5
# KeyGen seed split: (rho, rho', K) = H(xi || k || l, 128).xi = bytes.fromhex( "A991FD42B071D49C48AE3E75C647459E0DAAD1E1BA356A04801912D3294BCFF8")raw = H(xi + integer_to_bytes(k, 1) + integer_to_bytes(l, 1), 128)rho, rho_prime, K = raw[:32], raw[32:96], raw[96:128]
# The public-key transcript tr = H(pk, 64), the message representative# mu = H(tr || M', 64), and the per-signature mask seed rho'' = H(K || rnd || mu, 64).pk_stub = bytes(1952) # length of a real ML-DSA-65 pktr = H(pk_stub, 64)m_prime = integer_to_bytes(0, 1) + integer_to_bytes(0, 1) + b"sign me"mu = H(tr + m_prime, 64)rho_dprime = H(K + bytes(32) + mu, 64) # rnd = 0^32 is the deterministic variant
print("H is SHAKE256 :", H(b"", 32) == hashlib.shake_256(b"").digest(32))print("len(rho, rho', K) =", (len(rho), len(rho_prime), len(K)))print("len(tr, mu, rho'') =", (len(tr), len(mu), len(rho_dprime)))print("mu[:8] =", mu[:8].hex())# ==> H is SHAKE256 : True# ==> len(rho, rho', K) = (32, 64, 32)# ==> len(tr, mu, rho'') = (64, 64, 64)# ==> mu[:8] = 5cc3785bc60dd808The message actually signed is , not the raw message . The internal message is framed with a context string as . Here the context is empty, so is two zero bytes followed by the message. The randomizer is bytes: random in the hedged variant, all zero in the deterministic one. Hedged is FIPS 204’s default, and it protects against fault attacks that resign the same message to compare outputs. The deterministic variant is the permitted alternative for a signer with no fresh randomness at signing time (National Institute of Standards and Technology, 2024). The ACVP vectors pin the deterministic form, so this chapter signs with throughout.
Sampling: SampleInBall, ExpandA, ExpandS, ExpandMask
Section titled “Sampling: SampleInBall, ExpandA, ExpandS, ExpandMask”Every structured value in ML-DSA is squeezed from a SHAKE stream and filtered (National Institute of Standards and Technology, 2024, sec. 7.3). Four samplers appear. ExpandA (SHAKE-128) fills the matrix directly in the NTT domain, rejecting any three-byte read that decodes to a value . ExpandS (SHAKE-256) fills the short secret vectors, rejecting half-bytes outside the small window that maps into . ExpandMask does not reject; it bit-unpacks a fixed number of bytes into the mask range . SampleInBall builds the challenge : exactly coefficients set to and the rest zero, placed by a Fisher-Yates-style swap driven by the stream, with the signs taken from the first eight squeezed bytes.
import hashlibimport numpy as np
def sample_in_ball(rho, tau): xof = hashlib.shake_256(rho) need = 8 stream = xof.digest(need) signs = int.from_bytes(stream[:8], "little") c = np.zeros(256, dtype=np.int64) pos = 8 for i in range(256 - tau, 256): while True: if pos >= len(stream): need += 168 stream = xof.digest(need) j = stream[pos] pos += 1 if j <= i: break c[i] = c[j] bit = (signs >> (i + tau - 256)) & 1 c[j] = -1 if bit else 1 return c
# ML-DSA-65: tau = 49 nonzero coefficients, challenge seed c-tilde is 48 bytes.tau = 49c = sample_in_ball(bytes(range(48)), tau)print("challenge length =", int(c.shape[0]))print("nonzero coefficients =", int(np.count_nonzero(c)))print("values are +-1 only =", set(int(x) for x in c) == {-1, 0, 1})print("sum of coefficients =", int(c.sum()))# ==> challenge length = 256# ==> nonzero coefficients = 49# ==> values are +-1 only = True# ==> sum of coefficients = 3The loop runs from to . At each step it reads bytes until it finds a position , moves whatever sits at up to position (position is still zero, since every earlier step wrote only positions no larger than its own smaller ), and writes a fresh at . Each iteration adds exactly one nonzero coefficient, whatever the stream contains: if already held a it is carried to and is re-signed, and if was zero it becomes the new . So the construction guarantees exactly nonzero coefficients. The signed sum is data-dependent (here , meaning of the are ). What SampleInBall fixes is the count and the magnitude, not the sum. A challenge with nonzero coefficients has infinity norm and one-norm , which is what bounds and by .
The full NTT at (256, 8380417)
Section titled “The full NTT at (256, 8380417)”Because , ML-DSA’s NTT is the full negacyclic transform, not ML-KEM’s partial one (National Institute of Standards and Technology, 2024, sec. 7.5). The forward transform is the decimation-in-time (Cooley-Tukey) butterfly with bit-reversed twiddle factors ; the inverse is the Gentleman-Sande butterfly with negated twiddles, followed by one scaling by . Multiplication in the NTT domain is plain coefficient-wise, with no base-case multiply, because every factor of is linear.
import numpy as np
Q = 8380417N = 256ZETA = 1753N_INV = pow(N, -1, Q)
def bit_rev_8(k): r = 0 for _ in range(8): r = (r << 1) | (k & 1) k >>= 1 return r
ZETAS = [pow(ZETA, bit_rev_8(k), Q) for k in range(256)]
def ntt(w): w_hat = (np.asarray(w, dtype=np.int64) % Q).copy() m = 0 length = 128 while length >= 1: start = 0 while start < N: m += 1 zeta = ZETAS[m] for j in range(start, start + length): t = (zeta * int(w_hat[j + length])) % Q w_hat[j + length] = (int(w_hat[j]) - t) % Q w_hat[j] = (int(w_hat[j]) + t) % Q start += 2 * length length //= 2 return w_hat
def ntt_inverse(w_hat): w = (np.asarray(w_hat, dtype=np.int64) % Q).copy() m = 256 length = 1 while length < N: start = 0 while start < N: m -= 1 zeta = (-ZETAS[m]) % Q for j in range(start, start + length): t = int(w[j]) w[j] = (t + int(w[j + length])) % Q w[j + length] = (zeta * (t - int(w[j + length]))) % Q start += 2 * length length *= 2 return np.array([(N_INV * int(w[j])) % Q for j in range(N)], dtype=np.int64)
def multiply_ntts(a_hat, b_hat): return np.array([(int(a_hat[i]) * int(b_hat[i])) % Q for i in range(N)], dtype=np.int64)
def schoolbook(a, b): out = [0] * N for i in range(N): ai = int(a[i]) for j in range(N): k = i + j prod = ai * int(b[j]) if k < N: out[k] = (out[k] + prod) % Q else: # X^256 = -1: wrap with a sign flip out[k - N] = (out[k - N] - prod) % Q return np.array(out, dtype=np.int64)
rng = np.random.default_rng(seed=20260723)f = rng.integers(0, Q, size=N, dtype=np.int64)g = rng.integers(0, Q, size=N, dtype=np.int64)prod_ntt = ntt_inverse(multiply_ntts(ntt(f), ntt(g)))prod_school = schoolbook(f, g)print("N_INV =", N_INV)print("ZETAS[1] =", ZETAS[1])print("NTT product equals schoolbook =", bool(np.array_equal(prod_ntt, prod_school)))# ==> N_INV = 8347681# ==> ZETAS[1] = 4808194# ==> NTT product equals schoolbook = TrueThe forward NTT, the inverse NTT, and the coefficient-wise multiply are correct by construction, and the schoolbook cross-check is the independent computation path: a tautological check like ntt(f) == ntt(f) would catch nothing. The value is the first twiddle consumed by the butterfly and is pinned in tests/ch12/test_mldsa_ntt.py against the FIPS 204 table, alongside . Both are landmarks rather than a complete test: a wrong root changes them, and so does any bit-reversal error reaching index 1 or 128, but an error confined to other positions leaves both standing. The scaling factor is applied once at the end of the inverse transform, where ML-KEM’s partial NTT scaled by instead because it split the ring into factors.
Power2Round, Decompose, and the hint
Section titled “Power2Round, Decompose, and the hint”The rounding operators are defined coefficient-wise on integers in (Algorithms 35 to 40 in National Institute of Standards and Technology, 2024). Power2Round drops the low bits; Decompose splits around ; MakeHint and UseHint carry the one-bit correction. The block below defines all four scalar cores, checks that Power2Round reconstructs its input, and checks the hint identity over random pairs.
import numpy as np
Q = 8380417D = 13
def mod_pm(r, alpha): m = r % alpha return m - alpha if m > alpha // 2 else m
def power2round(r): r %= Q r0 = mod_pm(r, 1 << D) return (r - r0) >> D, r0
def decompose(r, gamma2): r %= Q r0 = mod_pm(r, 2 * gamma2) if r - r0 == Q - 1: return 0, r0 - 1 return (r - r0) // (2 * gamma2), r0
def high_bits(r, gamma2): return decompose(r, gamma2)[0]
def make_hint(z, r, gamma2): return 1 if high_bits(r, gamma2) != high_bits((r + z) % Q, gamma2) else 0
def use_hint(h, r, gamma2): m = (Q - 1) // (2 * gamma2) r1, r0 = decompose(r, gamma2) if h == 1: return (r1 + 1) % m if r0 > 0 else (r1 - 1) % m return r1
gamma_2 = (Q - 1) // 32 # ML-DSA-65/87 low-order window
# Power2Round splits a public coefficient into a top part and the dropped d bits.t = 4211255t1, t0 = power2round(t)print("power2round(t) = (t1, t0) =", (t1, t0))print("t1 * 2^d + t0 == t :", t1 * (1 << D) + t0 == t)
# The hint lets a verifier that knows r and the hint recover HighBits(r + z)# whenever the perturbation z stays within the low-order window gamma_2.# UseHint decomposes r itself and branches on the sign of the low part.rng = np.random.default_rng(seed=7)ok = Truefor _ in range(20000): r = int(rng.integers(0, Q)) z = int(rng.integers(-gamma_2, gamma_2 + 1)) if use_hint(make_hint(z, r, gamma_2), r, gamma_2) != high_bits((r + z) % Q, gamma_2): ok = False breakprint("UseHint(MakeHint(z, r), r) == HighBits(r + z) for |z| <= gamma_2 :", ok)# ==> power2round(t) = (t1, t0) = (514, 567)# ==> t1 * 2^d + t0 == t : True# ==> UseHint(MakeHint(z, r), r) == HighBits(r + z) for |z| <= gamma_2 : TrueThe reconstruction recovers the input exactly, which is the invariant Power2Round guarantees. The hint identity holds for every one of the pairs because the perturbation stays inside the window . The exercises ask what happens at , where the single bit is no longer enough. UseHint reads the direction of the correction from the sign of the low part : a positive means the coefficient sits just below a boundary and adding pushed it up, so the high part increments, and a nonpositive means it decrements. The modulus wraps the high part cyclically so the boundary case at the top of the range stays consistent with Decompose’s boundary rule.
KeyGen
Section titled “KeyGen”KeyGen expands the seed, draws the secret, forms the Module-LWE sample, and truncates it. From it derives , expands from directly in the NTT domain, and draws from with ExpandS. It computes (the matrix product runs in the NTT domain and comes back), applies Power2Round to get , and packs and , where .
The key equation is the only new algebra, and it is easiest to see at ring degree , where each ring element is a single integer and the module becomes ordinary matrix arithmetic over . The block below runs at and truncates with the real , using the same and Power2Round as the full scheme.
import numpy as np
Q = 8380417D = 13
def mod_pm(r, alpha): m = r % alpha return m - alpha if m > alpha // 2 else m
def power2round(r): r %= Q r0 = mod_pm(r, 1 << D) return (r - r0) >> D, r0
# The ML-DSA key equation t = A s1 + s2, shown at ring degree n = 1 so each# ring element is a single integer in Z_q. Module shape (k, l) = (2, 2), secret# coefficients drawn from [-eta, eta] with eta = 4. The real scheme runs the# same equation over degree-255 polynomials with A expanded from rho.rng = np.random.default_rng(seed=204)A = rng.integers(0, Q, size=(2, 2), dtype=np.int64)s1 = rng.integers(-4, 5, size=2, dtype=np.int64)s2 = rng.integers(-4, 5, size=2, dtype=np.int64)t = (A @ s1 + s2) % Q
# Power2Round drops the low d = 13 bits of t; the public key ships t1 only.t1 = np.empty(2, dtype=np.int64)t0 = np.empty(2, dtype=np.int64)for i in range(2): t1[i], t0[i] = power2round(int(t[i]))
print("t =", [int(x) for x in t])print("t1 =", [int(x) for x in t1])print("reconstructs t :", all(int(t1[i]) * (1 << D) + int(t0[i]) == int(t[i]) for i in range(2)))print("t0 within (-2^12, 2^12] :", bool(np.all((t0 > -(1 << (D - 1))) & (t0 <= (1 << (D - 1))))))# ==> t = [2613718, 1033595]# ==> t1 = [319, 126]# ==> reconstructs t : True# ==> t0 within (-2^12, 2^12] : TrueThe public key ships (here ) and keeps in the secret key. A verifier reconstructs , which differs from the true by the discarded , bounded by in each coefficient. That gap is exactly what the hint corrects during verification. Because the low bits are the least significant, dropping them costs the public key nothing in security: the Dilithium security analysis assumes the public key is the full rather than the truncated , so hiding is not what protects the key (Ducas et al., 2018). FIPS 204 keeps in the secret key only so the signer can compute the hint, not because it is secret in the Module-LWE sense (National Institute of Standards and Technology, 2024).
Sign: the rejection-sampling abort loop
Section titled “Sign: the rejection-sampling abort loop”Sign is the Fiat-Shamir-with-aborts loop. It decodes the secret key, computes and the mask seed , and then loops. Each iteration:
- Expands a fresh mask from and a counter , and advances by so the next attempt reads a fresh block of sub-seeds.
- Computes the commitment and its high bits .
- Derives the challenge and .
- Forms the response and the low part .
- Rejects and restarts if or .
- Builds the hint and rejects if or the hint has more than set bits.
- Otherwise outputs .
The two rejection tests in step 5 are the whole point of the “with aborts” design. The first keeps inside the box where its distribution is independent of ; the second keeps the low part of far enough from a boundary that its high bits equal those of . Step 6’s tests keep the hint correctable by a single bit and within its sparse budget . Every rejected attempt is discarded in full: no partial state carries to the next iteration except the advancing counter , which only reads fresh randomness.
y, commits to HighBits(A y), derives the challenge c by hashing the commitment and message, and forms the response z = y + c s1. The first gate rejects when z or the low part r0 leaves its safe box; the second rejects when the hint term c t0 is too large or the hint exceeds its budget omega. A rejected attempt restarts with a fresh mask; an accepted one emits the signature.The diagram makes the loop structure visible. The two gates sit at different points because they guard different things. The first gate guards two properties at once: its bound on protects zero-knowledge by rejecting any response whose distribution would depend on , and its bound on protects correctness by keeping the low part of clear of a high-bit boundary. The expected number of trips through the loop is small and public. What must never leak is anything about the attempts that were thrown away.
Verify: recomputing the commitment through UseHint
Section titled “Verify: recomputing the commitment through UseHint”Verify decodes , rejecting immediately if the hint decode returns . It recomputes the approximate commitment
which expands to : substituting and cancels the terms. Applying uses the hint bit to undo the perturbation, recovering , which equals because the signer rejected any attempt whose was too large. Verify then recomputes and accepts iff and .
The end-to-end block imports the from-scratch package to run KeyGen, Sign, and Verify at ML-DSA-65 and to confirm that a one-byte tamper on the signature is rejected. It uses the ACVP tcId=26 seed for the key and signs with the deterministic .
import sys
sys.path.insert(0, "solutions/ch12-mldsa/src")from mldsa.params import ML_DSA_65from mldsa.ml_dsa import ( ml_dsa_keygen_internal, ml_dsa_sign_internal, ml_dsa_verify_internal,)
# The from-scratch package assembles the primitives above into the three# operations. KeyGen expands a 32-byte seed; Sign runs the abort loop; Verify# recomputes the commitment through UseHint. These are the internal (explicit# seed and rnd) variants the ACVP vectors drive.xi = bytes.fromhex( "A991FD42B071D49C48AE3E75C647459E0DAAD1E1BA356A04801912D3294BCFF8")pk, sk = ml_dsa_keygen_internal(ML_DSA_65, xi)
# M' is the internal message: 0x00 || len(ctx) || ctx || message, empty context.m_prime = bytes([0, 0]) + b"the abort loop terminates"sigma = ml_dsa_sign_internal(ML_DSA_65, sk, m_prime, bytes(32))
good = ml_dsa_verify_internal(ML_DSA_65, pk, m_prime, sigma)tampered = bytes([sigma[0] ^ 0x01]) + sigma[1:]bad = ml_dsa_verify_internal(ML_DSA_65, pk, m_prime, tampered)
print("pk, sk, sig lengths =", (len(pk), len(sk), len(sigma)))print("honest signature verifies =", good)print("tampered signature verifies =", bad)# ==> pk, sk, sig lengths = (1952, 4032, 3309)# ==> honest signature verifies = True# ==> tampered signature verifies = FalseThe tampered signature flips a byte of , so the verifier samples a different challenge , recomputes a different , and finds . Tampering with the response instead trips the norm check or the challenge recomputation; tampering with the hint trips either the HintBitUnpack path or the recomputed high bits. Each of those rejection paths is exercised by the per-parameter-set tamper tests in tests/ch12/test_mldsa_sign.py across all three sets. Those are selected byte flips, wrong messages and wrong keys, so they show that the displayed tampering is rejected rather than that no modification of any signature can verify. That stronger statement is a property of the construction and its stated assumptions, not something a finite test set establishes. The reference is toy code: it compares with a plain ==. A deployed signer must run every secret-dependent step in constant time, a point the cryptanalysis section returns to. In the ordinary case every verification input is public and the comparison processes nothing confidential. FIPS 204 §3.6.3 names the message, the signature and the public key as inputs that some applications need to keep confidential, and what it requires is that potentially sensitive intermediate data be destroyed once it is no longer needed (National Institute of Standards and Technology, 2024). Constant-time comparison is this book’s implementation advice for that case. The standard does not use the phrase anywhere.
Cryptanalysis and known attacks
Section titled “Cryptanalysis and known attacks”ML-DSA claims NIST security categories 2, 3, and 5 for ML-DSA-44, ML-DSA-65, and ML-DSA-87 (National Institute of Standards and Technology, 2024). Those categories rate a scheme by the resources an attack needs relative to reference attacks on generic primitives, with categories 2 and 4 using hash-collision reference problems and categories 1, 3, and 5 using key recovery against AES. Two separate attacks set the parameters, one per assumption.
Key recovery is Module-LWE. An attacker who could recover from would hold the signing key. The cost is the cost of solving the Module-LWE instance, which the CRYSTALS-Dilithium design paper prices with the same core-SVP methodology that sets the ML-KEM parameters (Ducas et al., 2018, sec. 4.3). Chapter 13 builds that estimator and runs it end to end, on ML-KEM’s Module-LWE instances first and then on ML-DSA’s, from the Kannan embedding through the core-SVP cost model to the NIST category floors. The short version is that the module dimensions are the security lever, exactly as the module rank was for ML-KEM.
Forgery is Module-SIS. A forger without the key must exhibit a short and a challenge satisfying the verification relation. Because is norm-bounded by and is a sparse vector, a forgery is a short solution to a homogeneous module-lattice system, and its cost is the cost of the corresponding SelfTargetMSIS instance, which is at least as hard as Module-SIS in the classical random-oracle model, by a non-tight reduction (Ducas et al., 2018, sec. 4). The hint budget and the bound enter here: they cap how much slack a forger has in the last coefficients, and FIPS 204 sets them so the SIS instance stays as hard as the target category. This is why ML-DSA needs two assumptions where ML-KEM needed one. The proof leans on both, through different doors: key recovery is a Module-LWE instance, and forgery reduces to SelfTargetMSIS, which the concrete estimates price as a Module-SIS instance. Losing either assumption removes the corresponding guarantee.
The rejection loop is the implementation’s most sensitive point. The number of iterations is public and leaks nothing, because the acceptance region does not depend on the secret (Lyubashevsky, 2012). The danger is the rejected values. Each discarded and each intermediate , , depends on the secret, so a side channel that leaks whether a particular coefficient was near a rejection boundary, or leaks the timing of the norm checks, hands an attacker a noisy view of the secret.
FIPS 204 §3.6.3 requires that implementations destroy any potentially sensitive intermediate data as soon as it is no longer needed, and adds that in certain situations, deterministic signing among them, additional care must be taken against side-channel and fault attacks (National Institute of Standards and Technology, 2024). Constant-time execution of the secret-dependent steps (the norm comparisons on , and , the hint construction, and every arithmetic step that touches , , or the mask ) is the accepted way to meet that. The deterministic variant this chapter signs with is the one that carries the caveat: §3.4 says it should not be used on platforms where side-channel attacks are a concern and cannot otherwise be mitigated.
The Fiat-Shamir transform’s security in the quantum random-oracle model, needed to claim EUF-CMA (Goldwasser et al., 1988) against a quantum adversary rather than only a classical one, rests on the QROM analyses of the transform (Don et al., 2019). As with ML-KEM, the security statement is reduction-based: it assumes Module-LWE and SelfTargetMSIS hardness, idealizes SHAKE as a random oracle, and requires constant-time implementation, so ML-DSA is believed to be EUF-CMA-secure under these assumptions rather than unconditionally.
Tradeoffs inside Part II
Section titled “Tradeoffs inside Part II”ML-DSA and ML-KEM share a ring family, a serialization style, and the Module-LWE assumption, and diverge on almost everything else. The comparison is by primitive role.
- ML-DSA versus ML-KEM (Chapter 11): ML-KEM is a key-encapsulation mechanism wrapped in the Fujisaki-Okamoto transform to reach IND-CCA2 from one assumption; ML-DSA is a signature built from Fiat-Shamir with aborts on two assumptions. ML-KEM’s forces a partial NTT with a base-case multiply; ML-DSA’s admits a full NTT with pointwise multiply, at the cost of larger coefficients. ML-KEM runs in fixed time; ML-DSA’s signer runs a variable number of abort iterations, so signing time is data-dependent even though the acceptance region is not. ML-DSA’s objects are larger: a -byte public key and -byte signature at category 3, against ML-KEM-768’s -byte encapsulation key and -byte ciphertext, because a signature must carry a full masked response vector while a KEM ciphertext carries only a compressed sample.
- ML-DSA versus SLH-DSA (Chapter 17): SLH-DSA is the hash-based signature standardized in FIPS 205, and it rests on no structured-lattice assumption at all, only on the security of its hash functions. That makes SLH-DSA the conservative choice against a future break of Module-LWE or Module-SIS, at the cost of much larger signatures (roughly to kilobytes across its parameter sets, against ML-DSA-65’s bytes) and slower signing. NIST presents ML-DSA as its primary signature standard and SLH-DSA as a backup resting on a different mathematical approach, to be reached for if ML-DSA proves vulnerable (National Institute of Standards and Technology, 2024b). That is an intended role and not a measurement. The announcement makes no claim about what deployments actually use, and neither does this book. The size and speed figures above are what a deployment weighs when the lattice assumptions are acceptable to it (National Institute of Standards and Technology, 2024a, 2024b).
- The abort loop is unique to the lattice Fiat-Shamir family. Neither ML-KEM’s FO wrapper nor SLH-DSA’s hash tree has anything like it, because neither needs to hide a secret-dependent response inside a bounded box. The rejection step is the price ML-DSA pays for building a signature from Module-LWE rather than from a hash tree or a KEM.
Chapter 13 closes Part II by putting a price on the Module-LWE assumption that this chapter and Chapter 11 both rest on. It builds a core-SVP estimator in Python, runs the primal and dual attacks through it, and turns a BKZ block size into a bit count under a stated cost model, which it then reads against the published category claims rather than assigning a category itself. It works that machinery against ML-KEM’s instances and then against ML-DSA’s. Its estimator prices Module-LWE only, and the Module-SIS row it reports is the Dilithium submission’s own, so the parameter table above stays taken as given on the forgery side.
Exercises
Section titled “Exercises”-
Counting abort iterations. Read the traced signer
_sign_internal_tracedin thech12-mldsapackage undersolutions/, which returns the number of rejection-loop iterations alongside the signature. Sign a few hundred distinct messages at ML-DSA-65 with the deterministic , record the iteration count for each, and report the mean. Compare it to the two-test prediction, the reciprocal of the product of the two acceptance probabilities: the probability that and the probability that . That prediction prices one of Algorithm 7’s two abort points. Identify the other, say which direction it moves the count, and state whether the difference is large enough to see in your sample. Explain why raising lowers the expected iteration count but enlarges the signature, and why ML-DSA-65 sits where it does on that tradeoff. -
The hint window, and its edge. The block above checks the hint identity over pairs drawn from inside the window, and it never fails. Go one step outside it. Using
power2round,decompose,make_hint, anduse_hintin thech12-mldsapackage undersolutions/, find a pair with for which . Report how far apart the two values are, and explain why the single-bit hint is exactly enough inside the window but not one step past it. The direction UseHint infers from the sign of is where the argument turns. Tie this back to the second rejection test in Sign, which enforces on the term the hint has to correct. -
Which check catches which tamper. Using the
ch12-mldsapackage undersolutions/, sign a message at ML-DSA-65, then produce three tampered signatures: one that flips a byte inside the packed response , one that corrupts a hint byte so a poly’s positions are no longer strictly increasing, and one that flips a byte of the challenge hash . For each, run verification and identify which of the three verifier checks rejects it: the norm bound on , the HintBitUnpack path, or the recomputed-challenge comparison . Explain why no single check catches all three. -
The commitment binds the encoding width. In the
ch12-mldsapackage undersolutions/,w1_encodepacks each high-bit coefficient of at the width implies: bits for ML-DSA-65, for ML-DSA-44. Widen the ML-DSA-65 packing to bits insidew1_encodeand rerun a sign-then-verify round trip. It still verifies. Now check a signature produced by an unmodified signer against the widened verifier. It fails. Explain both results. The width feeds into , so a signer and verifier that agree on the wrong width still agree. A signer and verifier that disagree hash different byte strings for the same , and the recomputed challenge no longer matches. Nothing in the scheme checks the width; it is only agreed. This is why the byte layer is part of the security contract, not just an encoding detail.
Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 12. A separate track, for rebuilding rather than reading: the package exercises/ch12-mldsa has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch12 to grade your version against the suite that proves the reference one.
References
Section titled “References”Last updated: