Don't throw your nonces out with the bathwater
We suggest a small change to the Dilithium signature scheme [DKL], that allows reusing computation between aborted attempts for a speed-up in signing time. To create a signature in Dilithium, one picks a vector y = (y1, . . . , y`) over the ring R = Fq/(x + 1). Not every y will do: the vector is subjected to four checks to ensure correctness of the algorithm and prevent leakage of the private key. If y fails any of the tests, the attempt is aborted and a fresh y is sampled to try again. Depending on the instance of Dilithium, one expects having to resample y between 3.3 and 5.6 times. Out of the four checks, the following two cause more than 99% of the aborts. ‖y + cs1‖∞ ≤ γ1 − β (1) ‖w0 − cs2‖∞ ≤ γ2 − β (2) Here β, γ1 and γ2 are scheme parameters; s1 ∈ R and s2 ∈ R are part of the private key; w0 ∈ R is part of the decomposition w0 + 2w1γ2 = Ay with w0 and w1 suitably small and A an k× ` matrix over R which is part of the public key and c ∈ R is a challenge generated via hashing from w1. As the norm is the sup norm, the first check involves the following ` subchecks, one for each component of y: ‖yi + c(s1)i‖∞ ≤ γ1 − β. If the first subcheck fails (without having performed the other checks or subchecks), then instead of aborting completely and resampling all elements of y, we propose to resample y1 but keep y2, . . . , y`. This allows one to reuse the computations of Aijyj for j 6= 1, which were required to compute c via Ay. Note that the challenge c will be different after this partial abort. If the first check fails at y2 (after y1 passed) then we cannot reuse y1, because it will have to pass the check for at least one other challenge c. This will ∗daan@dsprenkels.com †bas@westerbaan.name