Key Generation

Key generation is the most familiar part of ML-DSA, because it is almost the same Module-LWE sample as ML-KEM's. One step at the end is new, and it creates a problem that the rest of the chapter has to solve.

01.The steps

K1. Expand the seed. Start from 32 random bytes $\zeta$ and hash into three pieces:

$$(\rho,\; \rho',\; K) \;=\; G(\zeta),$$

with $\rho$ being 32 bytes, $\rho'$ 64, and $K$ 32.

$\rho$ generates the public matrix. $\rho'$ generates the secrets. $K$ is a per-key salt kept for later, used inside signing to derive the commitment randomness.

K2. Expand $A$. Rejection-sample SHAKE128 keyed by $\rho$ into a uniform matrix $A \in R_q^{k \times \ell}$. Same "regenerate rather than transmit" arrangement as the KEM: the matrix travels as a 32-byte seed.

K3. Sample the secrets. From $\rho'$, draw $\mathbf{s}_1 \in R_q^{\ell}$ and $\mathbf{s}_2 \in R_q^{k}$, all coefficients from $\text{CBD}_\eta$ so they lie in $[-\eta, \eta]$.

K4. Form the Module-LWE sample.

$$\mathbf{t} \;=\; A\mathbf{s}_1 + \mathbf{s}_2 \;\in\; R_q^{k} .$$

Exactly the shape from Chapter 4, with $\mathbf{s}_1$ as secret and $\mathbf{s}_2$ as error. Recovering $\mathbf{s}_1$ from $(A, \mathbf{t})$ is Module-LWE hard.

K5. Truncate $\mathbf{t}$. This is the new step. Split every coefficient of $\mathbf{t}$ into a high part and a low part:

$$\mathbf{t} \;=\; 2^d \cdot \mathbf{t}_1 + \mathbf{t}_0, \qquad \mathbf{t}_0 \in (-2^{d-1},\, 2^{d-1}],$$

with $d = 13$. So $\mathbf{t}_1$ holds the top ten bits of each 23-bit coefficient and $\mathbf{t}_0$ holds the bottom thirteen.

Only $\mathbf{t}_1$ goes into the public key. The low part $\mathbf{t}_0$ is kept in the secret key.

K6. Precompute $\textsf{tr} = H(\rho \,\|\, \mathbf{t}_1)$, a digest of the public key, so signing does not recompute it.

K7. Output.

$$pk \;=\; (\rho,\; \mathbf{t}_1), \qquad sk \;=\; (\rho,\; K,\; \textsf{tr},\; \mathbf{s}_1,\; \mathbf{s}_2,\; \mathbf{t}_0).$$

At ML-DSA-65 that is about 1952 bytes of public key and 4032 bytes of secret key.

02.Why truncate

Step K5 is pure bandwidth economics.

Each coefficient of $\mathbf{t}$ is 23 bits, and there are $k \cdot 256$ of them. At $k = 6$ that is 1536 coefficients, so a full $\mathbf{t}$ costs about 4416 bytes. Keeping only the top ten bits costs 1920.

Public keys travel inside certificates, and certificate chains are already the largest thing in a TLS handshake. Halving the key is worth real effort.

03.The problem it creates

Discarding $\mathbf{t}_0$ means the signer and the verifier no longer hold the same value.

The signer knows $\mathbf{t}$ exactly. The verifier has only $\mathbf{t}_1$, from which it can compute $2^d \mathbf{t}_1 = \mathbf{t} - \mathbf{t}_0$. The two differ by $\mathbf{t}_0$, which the verifier does not have and cannot derive, since it is part of the secret key.

That discrepancy would not matter if the verification equation used $\mathbf{t}$ linearly and the error simply passed through. It does not. As Verification shows, $\mathbf{t}_0$ enters the verifier's computation multiplied by the challenge, as $c\mathbf{t}_0$, and then that result is rounded. Rounding is not linear, and a small perturbation just below a rounding boundary produces a completely different answer just above it.

So most coefficients round the same way for both parties, and a handful do not.

The design response is the one flagged in the source and worth stating as a principle: drop $\mathbf{t}_0$, bank the savings, and pay the cost later with a short hint. The hint vector in Signing is a list of exactly which coefficients rounded differently, and it is small because there are few of them.

That is a trade worth noticing as engineering. A cleaner design would send the full $\mathbf{t}$ and need no hint at all. ML-DSA instead accepts a genuinely intricate piece of machinery, the hint, in exchange for halving the thing that travels most often. The intricacy is confined to the scheme's internals, where it can be specified once and tested exhaustively, while the saving is paid out on every connection forever.