A signature makes a statement about exact message bytes under a particular public key — nothing more. A trustworthy system must also establish who controls that key, what the statement authorizes, and whether the verifier is interpreting the same message as the signer. This chapter develops ML-DSA's signing relationship from Fiat–Shamir with aborts, explains precisely why signing sometimes rejects a candidate and retries, distinguishes hedged from deterministic signing, and tests context binding with a reproducible native OpenSSL lab whose real pass/fail results are reported below.
1. The goal and the prerequisites
ML-DSA is the module-lattice digital-signature algorithm standardized in FIPS 204. It's derived from CRYSTALS-Dilithium, but standardized ML-DSA and earlier Dilithium variants are not interchangeable names for every encoding or interface — applications should select the standardized algorithm explicitly and use a library that documents exactly that implementation.
Read Parts 2, 4, and 6 first if signatures, modular polynomial vectors, and short-vector problems are unfamiliar. This chapter develops the signing relationship, explains why candidates get rejected during signing, distinguishes hedged and deterministic behavior, and tests context binding with native OpenSSL — it does not attempt to reconstruct the complete reference implementation from illustrative algebra alone.
FIPS 204 is final, dated August 13, 2024. The publication page carries a July 2026 potential-errata update covering several explanatory, notation, and loop-estimate issues — read it alongside the standard itself, particularly before implementing arithmetic or interpreting rejection-loop limits (§6).
2. Signatures are public evidence, not encryption
KeyGen creates a private signing key and corresponding public verification key. Sign takes the private key, message, and context, returning a signature. Verify takes the public key, message, context, and signature, returning acceptance or rejection. Anyone with the authenticated public key can verify — verification never requires sharing the signing secret.
The core security objective is resistance to forgery even when an attacker has obtained signatures on chosen messages (Part 4 §14, EUF-CMA). The attacker should not be able to produce a valid new forgery within the relevant security model. This is a purely computational property, separate from the entirely different operational question of whether a signing service should have authorized a particular request in the first place.
Similarly, signatures do not conceal messages and do not inherently prevent replay. A signed command needs a defined audience, version, expiry or freshness mechanism, and canonical encoding if those properties actually matter for the application. The signature establishes integrity of the exact bytes it covers; application policy determines whether those bytes should be acted upon now.
3. Parameters and exact sizes
FIPS 204 defines the following raw expanded key and signature encodings. A library may additionally support a compact seed representation for private-key storage, and PEM or DER containers introduce their own overhead — never compare container file sizes directly against this table.
| Parameter set | NIST category | Public key | Expanded private key | Signature |
|---|---|---|---|---|
| ML-DSA-44 | 2 | 1,312 bytes | 2,560 bytes | 2,420 bytes |
| ML-DSA-65 | 3 | 1,952 bytes | 4,032 bytes | 3,309 bytes |
| ML-DSA-87 | 5 | 2,592 bytes | 4,896 bytes | 4,627 bytes |
The suffixes encode the module dimensions: \((k,\ell)\) equals \((4,4)\), \((6,5)\), or \((8,7)\). They are not security-bit counts or signature lengths. All three sets use degree-256 polynomials and modulus \(q=8{,}380{,}417\) — this modulus differs from ML-KEM's 3,329, even though both algorithms use module-lattice arithmetic and transforms (Part 7 §3).
The public key contains a 32-byte matrix seed and a compressed high-part vector. For ML-DSA-44, four polynomials with 256 coefficients represented using 10 bits each occupy 1,280 bytes; adding the seed gives 1,312 bytes. The arithmetic explains the representation, while security depends on all parameters together, including bounds, challenge weight, and hash-output lengths — not the modulus alone.
Choose a parameter set through the protocol profile and threat model. A larger category can increase transmission and computation costs, but category labels alone do not rank complete systems. A protected category-2 signer may be a more appropriate deployed component than an exposed category-5 key sitting in an unrestricted CI job — cryptographic strength and operational protection answer genuinely different questions.
4. The public relation and the secret witness
Key generation samples short vectors \(s_1\) and \(s_2\), expands a public matrix \(A\) from a seed, and computes \(t = As_1 + s_2\). The public key retains a rounded high part \(t_1\); a low part \(t_0\) is kept in the private representation along with other signing material. Rounding is part of the construction itself, not lossy storage added afterward as an optimization.
The noisy relation supplies the Module-LWE intuition (Part 6 §8): public information should not reveal the short secrets. Forgery analysis also involves finding short algebraic relations of the kind studied through Module-SIS and related variants (Part 6 §9). Saying only "it uses lattices" loses the crucial distinction between hiding the secret (LWE's job) and preventing a new valid short response (SIS's job).
The polynomial ring is again defined modulo \(X^{256}+1\), but ML-DSA's modulus supports its own full transform structure — unlike ML-KEM's, which needed the degree-two workaround from Part 7 §4. The pending errata clarify an explanatory NTT formula that accidentally described evaluating a polynomial twice; an implementer should follow the precise algorithms and corrections rather than transcribing ambiguous prose literally.
No practical security follows from a tiny numeric example, but a scalar relationship exposes the cancellation clearly. Let \(q=97\), \(A=7\), \(s=3\), and \(t=As=21\). Choose \(y=4\) and challenge \(c=2\). Then \(z=y+cs=10\), and \(Az-ct = 70-42=28=Ay \pmod{97}\). ML-DSA develops a carefully bounded, noisy, rounded module analogue of exactly this relationship.
5. From identification to Fiat–Shamir
Imagine an interactive identification protocol. A prover first commits to a fresh masked value derived from \(y\). A verifier chooses a challenge \(c\). The prover replies with a response \(z\) that combines \(y\) and the secret. The verifier checks an equation showing consistency with the public key, without ever receiving the secret itself.
Fiat–Shamir replaces the interactive challenge with a cryptographic hash of the message and commitment. The signature becomes independently verifiable without any online challenge exchange. The hash ties the challenge tightly to the exact statement being signed — its domain separation, input order, and output interpretation are all security-relevant details, not arbitrary formatting choices.
In ML-DSA, signing computes a commitment from \(Ay\) and uses its high bits together with a message representative \(\mu\) to derive a challenge digest. That digest expands into a sparse challenge polynomial \(c\) with prescribed weight. The response \(z = y + cs_1\) is accompanied by compact hint information that lets the verifier reconstruct the needed high-bit commitment despite the rounding involved.
Fig. 1 — The challenge depends on the commitment and message; the response depends on the challenge and secret. Changing that order, or hashing a different concatenation, defines a genuinely different (and likely insecure) scheme.
6. Why signing sometimes aborts
If every candidate \(z=y+cs_1\) were released unconditionally, its distribution could reveal information about \(s_1\). Boundary effects are easy to see in one dimension: suppose \(y\) is uniform over integers \(-4\) through \(4\). Adding a secret-dependent shift of 2 moves the support to \(-2\) through \(6\) — repeated observations near the extremes let an attacker distinguish this shifted distribution from another possible shift, leaking information about the secret shift itself.
Rejection sampling filters candidates so the released distribution satisfies the construction's requirements exactly. ML-DSA also checks low-bit and hint-related bounds needed for verification and security. Rejected candidates are ordinary internal events — they are not signatures to serialize, diagnostic records to export, or failures that justify returning an unchecked result to the caller.
The phrase Fiat–Shamir with aborts refers to exactly this strategy. A signing request can require several candidate attempts before succeeding. Verification checks one supplied signature and does not reproduce the signer's search at all — this asymmetry affects latency distributions in practice: measuring only the average signing time hides the tail created by retries and other implementation behavior, which matters for any latency-sensitive signing service.
7. Signing and verification, schematically
The following outline shows responsibilities rather than executable cryptographic code. All sampling, decomposition, norm checks, hint encoding, and domain-separated hashing must follow FIPS 204 exactly — this is a map, not a substitute for the standard.
Sign(sk, message, context):
form the specified domain-separated message input
derive message representative and masking seed
repeat:
sample fresh candidate mask y from that seed stream
derive high commitment bits from A*y
hash representative and encoded high bits → challenge digest
expand digest → sparse challenge c
compute response z and required low-part information
reject if response, low-part, or hint bounds fail
encode challenge digest, z, and hints
Verify(pk, message, context, signature):
decode strictly; reject malformed representation
reject response or hint bounds violations
derive the same message representative and challenge
reconstruct commitment high bits using public relation and hints
hash representative and reconstructed encoding
accept only if the challenge digest matchesThe verifier never learns \(y\) or the private vectors. It uses the public key, response, and hints to reconstruct the committed value at exactly the precision required by the scheme. Hints are controlled corrections to rounding — not arbitrary advice the verifier should simply trust; their canonical encoding and bounds are checked before acceptance, just like every other field.
A production implementation must also distinguish malformed input, unsupported parameters, provider errors, and a well-formed-but-invalid signature at its API boundary. An application should fail closed on all verification failures without treating every single failure as evidence of an active attack — misconfiguration, wrong context, and message-encoding mismatches can all produce the exact same final rejection.
8. Hedged signing, deterministic signing, and contexts
FIPS 204 specifies hedged signing using fresh per-message randomness combined with secret material and the message representative. It also allows a deterministic variant that replaces the external randomness input with 32 zero bytes — the resulting mask derivation still depends on secret and message inputs; it does not set the actual mask \(y\) to zero, a common misreading of "deterministic."
Both variants use the exact same verification algorithm. The standard favors the hedged approach for additional protection against certain implementation failures. Deterministic behavior can aid reproducibility, but it is not a blanket defense against side channels or faults — a repeated message can produce repeated internal behavior, which may matter significantly to an attacker collecting physical measurements over many signing operations.
The context is at most 255 bytes and participates in the specified domain separation. Pure ML-DSA and HashML-DSA have different formatted inputs. Prehashing a file manually and then signing the digest as an ordinary message is not automatically HashML-DSA — a protocol must specify the mode, prehash algorithm when applicable, and context consistently at both endpoints, or interoperability silently breaks.
For example, a release manifest and an access token could contain identical bytes while representing completely different authorizations. Distinct protocol contexts can prevent a signature from one domain being accepted in another, when the protocol actually defines and checks those contexts. Contexts don't replace canonical message formats or authorization rules — they make one specific boundary explicit and checkable.
9. Executed OpenSSL sign-and-verify lab
The OpenSSL 3.5 ML-DSA documentation describes context-string and deterministic parameters. This script was run with OpenSSL 3.5.8 on macOS ARM64. It creates a disposable key, verifies a signature, rejects modified content and a wrong context, and checks deterministic repetition. Keep OPENSSL pointed at the intended binary.
#!/usr/bin/env bash
set -euo pipefail
OPENSSL=${OPENSSL:-openssl}
LAB=$(mktemp -d)
trap 'rm -rf "$LAB"' EXIT
umask 077
cd "$LAB"
"$OPENSSL" version
printf '%s\n' 'release=1; artifact=example; environment=lab' > message.txt
"$OPENSSL" genpkey -algorithm ML-DSA-65 -out private.pem
"$OPENSSL" pkey -in private.pem -pubout -out public.pem
"$OPENSSL" pkeyutl -sign -rawin -inkey private.pem -in message.txt -out signature.bin -pkeyopt context-string:pqc-course
"$OPENSSL" pkeyutl -verify -rawin -pubin -inkey public.pem -in message.txt -sigfile signature.bin -pkeyopt context-string:pqc-course
python3 - <<'PY'
from pathlib import Path
assert len(Path('signature.bin').read_bytes()) == 3309
Path('changed.txt').write_bytes(Path('message.txt').read_bytes() + b'changed')
PY
if "$OPENSSL" pkeyutl -verify -rawin -pubin -inkey public.pem -in changed.txt -sigfile signature.bin -pkeyopt context-string:pqc-course > /dev/null 2>&1; then exit 1; fi
if "$OPENSSL" pkeyutl -verify -rawin -pubin -inkey public.pem -in message.txt -sigfile signature.bin -pkeyopt context-string:wrong-context > /dev/null 2>&1; then exit 1; fi
for i in 1 2; do
"$OPENSSL" pkeyutl -sign -rawin -inkey private.pem -in message.txt -out "det$i.bin" -pkeyopt deterministic:1 -pkeyopt context-string:pqc-course
done
cmp det1.bin det2.bin
printf '%s\n' 'PASS: verification, 3309-byte signature, tamper rejection, context binding, deterministic repeat'Add a wrong-public-key case and a corrupted-signature case as exercises. Record which public inputs changed and whether verification rejected them — never log private keys or internal signing randomness. Testing independent implementations later provides much stronger interoperability evidence than asking one binary to verify only its own output.
10. Protecting the signer and scaling verification
Signing processes secret-dependent intermediates and repeats candidate generation (§6). Constant-time arithmetic, careful memory access, fault resistance appropriate to the threat model, and secure randomness remain essential throughout. "The loop can repeat" does not authorize arbitrary secret-dependent branches or logging intermediate rejection reasons — each observable behavior needs analysis in the implementation's own leakage model (Part 13).
Protecting the key means protecting its seed as well as its expanded representation. A seed that regenerates the full key is equivalent in sensitivity to the private key itself. Backups, crash dumps, swap, container layers, and build logs can all defeat otherwise careful file permissions. A signing service should enforce request authorization and avoid handing raw signing keys to ordinary CI jobs, full stop.
Verification may be publicly accessible at high volume. Bound request sizes before expensive parsing, enforce the selected algorithm and context explicitly, and reject malformed signatures through maintained library APIs rather than hand-rolled parsing. Cache authenticated public-key parsing when appropriate, but never let cache entries bypass trust-policy updates, revocation decisions, or tenant isolation.
Benchmark signing and verification separately. Record parameter set, binary version, provider, CPU features, message length, whether hashing and key parsing are included, and concurrency level. Expanded matrix caching can trade memory for speed. A low-latency result from a warmed microbenchmark does not establish real service throughput under certificate processing, queueing, and network load (Part 14).
11. Questions before adopting ML-DSA
Can the verifier identify the exact signed bytes and context? Does it authenticate the verification key through a defined trust path? Does it enforce freshness or release-version policy separately? Can the signing service reject unauthorized requests even when they're syntactically valid? These four questions test the system built around the primitive, not the primitive itself.
Also be able to explain why a rejected signing candidate is entirely normal (§6), while accepting an out-of-bounds signature is a genuine security defect (§7); why a compact seed remains private-key material (§10); and why changing a message's whitespace may invalidate a signature even when a human considers its meaning unchanged (§8) — a precise byte-level contract is part of any robust integration.
Why does ML-DSA signing sometimes need multiple attempts internally?
Rejection sampling (§6) filters out candidate responses whose distribution would leak information about the secret key. Rejected candidates are normal internal events, not errors — the expected number of attempts is roughly 4-5 depending on parameter set, per NIST's own estimates.
Is deterministic ML-DSA signing less secure than hedged signing?
Not automatically, but it removes one layer of protection against certain implementation failures (§8) that fresh per-signature randomness provides. It is not a defense against side-channel or fault attacks on its own — a repeated message under deterministic signing produces repeated internal behavior, which matters if an attacker can take physical measurements.
Does a matching context string on both sides guarantee the signature is being used correctly?
No (§8). Context binding is one specific boundary among several — canonical message format, prehash mode consistency (pure vs. HashML-DSA), and authorization policy all still need to be independently correct.
Takeaways
- A signature proves integrity of exact bytes under a key — it says nothing about whether signing that content was authorized. Supply-chain trust needs key isolation and authorization policy on top of correct cryptography.
- ML-DSA is Fiat-Shamir with aborts: the challenge depends on the commitment and message; the response depends on the challenge and secret; rejection sampling on the response prevents the released distribution from leaking the secret.
- Rejected signing candidates are normal, expected internal events (~4-5 attempts on average) — not failures, not signatures to export, and never a reason to return an unchecked result.
- Deterministic signing zeroes the external randomness input, not the mask itself — it aids reproducibility but is not a side-channel or fault defense on its own.
- Context binding, message canonicalization, and prehash-mode consistency are three separate boundaries — matching one doesn't guarantee the others are correct.
- The reproducible lab (§9) confirmed all five checks on real hardware: verification, exact 3,309-byte signature size, tamper rejection, wrong-context rejection, and deterministic repeatability.
References & further reading
- FIPS 204 (ML-DSA) · publication page (errata) — the primary standard for this entire chapter.
- OpenSSL 3.5 ML-DSA documentation — §9, the lab's context-string and deterministic parameters.