Verification

Verification is short, and the algebra proving it correct is the counterpart to ML-KEM's cancellation. It is worth following line by line for the same reason.

01.The algorithm

Inputs: $pk = (\rho, \mathbf{t}_1)$, the message $m$, and $\sigma = (\tilde{c}, \mathbf{z}, \mathbf{h})$.

V1. Regenerate $A$ from $\rho$, recompute $\textsf{tr} = H(\rho \,\|\, \mathbf{t}_1)$ and $\mu = H(\textsf{tr} \,\|\, m)$.

V2. Recover the challenge polynomial $c = \textsf{SampleInBall}(\tilde{c})$.

V3. Reconstruct the commitment's high bits:

$$\mathbf{w}'_1 \;=\; \text{UseHint}\bigl(\mathbf{h},\; A\mathbf{z} - c \cdot 2^d \mathbf{t}_1\bigr).$$

V4. Accept if all three hold:

$$\tilde{c} \;=\; H(\mu \,\|\, \mathbf{w}'_1), \qquad \|\mathbf{z}\|_\infty < \gamma_1 - \beta, \qquad \text{popcount}(\mathbf{h}) \le \omega .$$

The first is the Fiat-Shamir check: recompute the challenge from the reconstructed commitment and see whether it matches the one in the signature. The other two enforce the bounds the signer's rejection loop was supposed to guarantee, so a forger cannot simply ignore them.

02.Why it works

Expand what V3 actually computes. Substitute $\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$:

$$\begin{aligned} A\mathbf{z} - c\,2^d \mathbf{t}_1 &= A(\mathbf{y} + c\mathbf{s}_1) - c\,2^d\mathbf{t}_1 \\ &= A\mathbf{y} + cA\mathbf{s}_1 - c\,2^d\mathbf{t}_1 \\ &= \mathbf{w} + c\bigl(A\mathbf{s}_1 - 2^d\mathbf{t}_1\bigr) . \end{aligned}$$

Now use the two facts from key generation. Truncation gave $2^d\mathbf{t}_1 = \mathbf{t} - \mathbf{t}_0$, and the sample gave $\mathbf{t} = A\mathbf{s}_1 + \mathbf{s}_2$. Substituting both:

$$\begin{aligned} A\mathbf{z} - c\,2^d \mathbf{t}_1 &= \mathbf{w} + c\bigl(A\mathbf{s}_1 - \mathbf{t} + \mathbf{t}_0\bigr) \\ &= \mathbf{w} + c\bigl(A\mathbf{s}_1 - A\mathbf{s}_1 - \mathbf{s}_2 + \mathbf{t}_0\bigr) \\ &= \mathbf{w} - c\,\mathbf{s}_2 + c\,\mathbf{t}_0 . \end{aligned}$$

The $A\mathbf{s}_1$ terms cancel, exactly as $\mathbf{s}^\top A^\top \mathbf{r}$ did in the KEM. That cancellation is again the whole construction.

What the verifier holds is therefore

$$\mathbf{w} \;-\; c\mathbf{s}_2 \;+\; c\mathbf{t}_0 ,$$

where $\mathbf{w}$ is what it wants and the other two terms are perturbations it cannot compute.

Now the rejection checks earn their place.

The signer's second check ensured $\text{LowBits}(\mathbf{w} - c\mathbf{s}_2)$ stays at least $\beta$ away from a bucket boundary, which means $\text{HighBits}(\mathbf{w} - c\mathbf{s}_2) = \text{HighBits}(\mathbf{w}) = \mathbf{w}_1$. The $-c\mathbf{s}_2$ term is invisible to rounding.

The signer's third check ensured $\|c\mathbf{t}_0\|_\infty < \gamma_2$, so the remaining term can move a coefficient by at most one bucket, never further.

And the hint records exactly which coefficients it did move. So $\text{UseHint}$ corrects them, and

$$\mathbf{w}'_1 \;=\; \mathbf{w}_1 .$$

Therefore $H(\mu \,\|\, \mathbf{w}'_1) = H(\mu \,\|\, \mathbf{w}_1) = \tilde{c}$, and the first check passes. The other two hold because the signer enforced them before emitting.

03.What the verifier never learns

Worth noting what has just happened, because it is the point of the whole construction.

The verifier reconstructed $\mathbf{w}_1$, a value derived from the signer's secret randomness $\mathbf{y}$, without ever being sent $\mathbf{y}$ or $\mathbf{w}$. It did so using only public data and the signature.

And it learned nothing about $\mathbf{s}_1$. The only secret-derived value it saw is $\mathbf{z}$, which Rejection Sampling, or Fiat-Shamir With Aborts made uniform on a fixed box independent of the secret. Everything else it computed itself.

That is a proof of knowledge in exactly the sense of Schnorr and Fiat-Shamir: convincing evidence that the signer holds $\mathbf{s}_1$, conveying no information about what $\mathbf{s}_1$ is.

04.Why verification is the cheap direction

One matrix-vector product $A\mathbf{z}$, one small product $c\,2^d\mathbf{t}_1$, some rounding, and two hashes. No loop, no restarts, no rejection.

So verification costs roughly one signing attempt, and signing costs four to six of them. The asymmetry runs the opposite way to ML-KEM, where decapsulation was the expensive operation.

That asymmetry is the right way round for how signatures are used. A software update is signed once by the vendor and verified by every machine that installs it. A certificate is signed once by an authority and verified on every connection to that site. Verification happens millions of times more often than signing, and it is the fast one.