Fiat–Shamir with Aborts Framework and Dilithium-G

We present a non-optimized version of Dilithium-G signature scheme in Algorithms 1 to 3 . The random oracle is defined as . Due to [Lyu12, Lemma 4.4] we restate below, the maximum -norm of the signature is set to , where the parameter is chosen such that the probability is negligible.

Lemma 1. For any ,

The following claim by Lyubashevsky (adapted from [Lyu12, Lemma 4.5]) is crucial for the signing oracle of FSwA to be simulatable, and also to decide the standard deviation as well as the expected number of repetitions . For instance, setting and leads to Although is asymptotically superconstant, increases very slowly in practice, and hence behaves essentially like a constant for practical security parameters (in the literature, it is often taken as 12 to ensure , thereby ensuring bits of security).

Lemma 2. For let Fix some such that and If for any positive , then

where and .

We now present a supporting lemma which is required for Dilithium-G to be UF-CMA secure. This is almost a direct consequence of Lemma 2 and a similar result appears in [KLS18, Lemma 4.3] to prove the security of Dilithium signature instantiated with the uniform distribution. We remark that the simulator in Algorithm 5 can only simulate transcripts of non-abort executions in the underlying interactive protocol; in fact, if Trans output in case of rejection as it's done in the interactive protocol then there is no known method to simulate the joint distribution of (without assuming some ad-hoc assumptions like rejection-DCK or rejected-LWE [FH20]).

Lemma 3 (Non-abort Special Honest Verifier Zero Knowledge). Let and Fix some such that and If for any positive , then for any and , the output distribution of Trans (Algorithm 4) is within statistical distance of the output distribution of (Algorithm 5), where and Moreover,

:

The proof closely follows the rejection sampling lemma due to Lyubashevsky [Lyu12, Lemma 4.7], but since we are interested in showing special HVZK, we account for fixed challenge given to the simulator as input. For each and , we define and . We first consider simplified algorithms Trans and SimTrans , which do not take the public key as input and only output or . Then we have

where the last inequality holds from Lemma 2. As is not involved in the rejection sampling we also have that Now we find the statistical distance:

where the last inequality holds from Lemma 2. Finally, outputting in non-abort cases doesn't increase the statistical distance: since the underlying identification protocol is commitment recoverable [KLS18], can be reconstructed given and .