Signing

This is the heart of the scheme, and it is a loop. Everything in it is either the Schnorr skeleton from Schnorr and Fiat-Shamir, the rejection rule from Rejection Sampling, or Fiat-Shamir With Aborts, or machinery for keeping the signature small.

01.The rounding gadgets

Two small routines are needed first. Both are pure integer arithmetic.

With bucket width $\alpha = 2\gamma_2$, decompose each $r \in \mathbb{Z}_q$ as

$$r \;=\; \alpha \cdot r_1 + r_0, \qquad r_0 \in (-\alpha/2,\; \alpha/2],$$

and define $\text{HighBits}_\alpha(r) = r_1$ and $\text{LowBits}_\alpha(r) = r_0$.

So $\text{HighBits}$ says which bucket of width $\alpha$ a value falls in, and $\text{LowBits}$ says where inside that bucket. Knowing only the high bits locates a value to within $\alpha$, which is coarse but often enough.

Both must be branchless, because they are applied to secret-dependent values and a data-dependent branch would leak through timing or cache behaviour.

02.The loop

S1. Compute the message digest. $\mu = H(\textsf{tr} \,\|\, m)$, where $\textsf{tr}$ was precomputed in key generation.

Then repeat the following until it succeeds.

S2. Commit. Sample $\mathbf{y} \in R_q^{\ell}$ with coefficients uniform on $(-\gamma_1, \gamma_1]$, and compute

$$\mathbf{w} \;=\; A\mathbf{y} \;\in\; R_q^{k} .$$

S3. Take the high bits. $\mathbf{w}_1 = \text{HighBits}(\mathbf{w})$.

Only the coarse part is committed to. Sending the whole of $\mathbf{w}$ would be wasteful, and the verifier only needs to be able to recompute the same coarse value.

S4. Challenge. $\tilde{c} = H(\mu \,\|\, \mathbf{w}_1)$, and then $c = \textsf{SampleInBall}(\tilde{c})$, which places exactly $\tau$ coefficients of $\pm 1$ at pseudorandom positions and leaves the rest zero.

This is Fiat-Shamir: the challenge is a hash of the commitment and the message, so the signer cannot choose it.

S5. Respond.

$$\mathbf{z} \;=\; \mathbf{y} + c\,\mathbf{s}_1 .$$

S6. The rejection checks. Restart if any of these fails.

$\|\mathbf{z}\|_\infty < \gamma_1 - \beta$. This is the zero-knowledge check from Rejection Sampling, or Fiat-Shamir With Aborts. It is what makes the released $\mathbf{z}$ uniform on a box that does not depend on $\mathbf{s}_1$.

$\|\text{LowBits}(\mathbf{w} - c\mathbf{s}_2)\|_\infty < \gamma_2 - \beta$. This one is not about secrecy at all. It is about the verifier being able to reproduce $\mathbf{w}_1$, and it keeps every coefficient a margin of $\beta$ away from a bucket boundary so that a small later perturbation cannot push it across.

$\|c\,\mathbf{t}_0\|_\infty < \gamma_2$. This bounds the discrepancy created by truncating the public key in Key Generation, guaranteeing it can move a coefficient by at most one bucket.

S7. Build the hint. Compute a one-bit flag per coefficient recording whether adding $c\mathbf{t}_0$ changes the bucket:

$$\text{MakeHint}(z, r) \;=\; \mathbf{1}\bigl\{ \text{HighBits}(r + z) \neq \text{HighBits}(r) \bigr\}.$$

Restart if more than $\omega$ bits are set.

S8. Emit.

$$\sigma \;=\; (\tilde{c},\; \mathbf{z},\; \mathbf{h}).$$

03.The three checks, separated

It is easy to read step S6 as one blob of conditions. They serve three distinct purposes and it is worth keeping them apart.

The first check exists so that the signature reveals nothing. Without it the scheme leaks the key, as note 3 demonstrated.

The second exists so that verification is possible at all. It guarantees the signer's $\mathbf{w}_1$ can be reconstructed from what the verifier will have.

The third exists so that the hint stays well defined. It caps the damage from public-key truncation at one bucket, which is what makes a single bit per coefficient sufficient to describe it.

Only the first is about security. The other two are the price of the two size optimisations, committing to high bits only and truncating the public key.

04.The hint vector

The hint deserves its own explanation because it is the least obvious piece of the scheme.

The verifier will reconstruct something close to $\mathbf{w}$, but off by $c\mathbf{t}_0$, because it holds only $\mathbf{t}_1$. It then takes high bits. Almost always the perturbation is too small to change which bucket a coefficient sits in, and the verifier gets the right answer. Occasionally a coefficient was near a boundary and the perturbation pushes it over.

The hint is a list of exactly which coefficients that happened to. One bit each, across $k \cdot 256$ coefficients.

Nearly all of those bits are zero, so serialising the hint as a bitstring would waste space. Instead it is stored as the positions of the set bits, of which there are at most $\omega$, which keeps it under a hundred bytes.

The check "restart if more than $\omega$ bits are set" is what makes that encoding safe. Without it a signature could occasionally need more positions than the format allows.

The verifier applies $\text{UseHint}$, which returns the high bits as computed if the bit is zero, and the adjacent bucket if it is one.

05.What signing costs

Per attempt: one matrix-vector product $A\mathbf{y}$ over $R_q$, which is $k\ell$ ring multiplications, plus two smaller products $c\mathbf{s}_1$ and $c\mathbf{s}_2$, plus a hash.

Expected attempts: four to six, from the rejection rate in Rejection Sampling, or Fiat-Shamir With Aborts.

So signing costs roughly five times a verification, and its running time varies from one invocation to the next. Both facts are unusual coming from ECDSA, and both matter for anybody building hardware: the signing datapath needs the same NTT engine as everything else, but it needs to be scheduled for a variable number of passes.

One property is worth stating explicitly because it looks alarming and is not. The number of restarts is public, observable in timing, and reveals nothing. Each attempt uses a fresh $\mathbf{y}$, and whether it passes depends on $\mathbf{y}$ and on the resulting $c$, not on any fixed property of $\mathbf{s}_1$. An observer counting restarts learns about the discarded randomness, which is discarded.