Fiat-Shamir with Rejection and Rotation
摘要
Fiat-Shamir with abort is a widely used paradigm in the design of lattice-based signatures. Compared to the original Fiat-Shamir framework, the main difference lies in the use of rejection sampling to prevent secret key leakage. There are mainly two types of rejections, the first one is used to control the distribution of the signature and the second one is to ensure the correctness of the signature. We propose a new approach to decrease the cost of the second type of rejection by re-randomizing instead of rejection. Briefly, when rounding a larger element in \(\mathbb {Z}_q\) to a smaller element in \(\mathbb {Z}_\gamma \) , the second type of rejection is used to guarantee the consistency of the result. Our main observation is that, instead of generating a new random element in \(\mathbb {Z}_q\) , re-randomizing the element in \(\mathbb {Z}_q\) may ensure the consistency with lower cost. That is, we attempt to remove the inconsistency by applying random rotation over \(\mathbb {Z}_q\) . When applying our new approach to the settings of ML-DSA, the average signing time is improved by about 20% to 30% in the AVX2 implementation. Additionally, by shrinking the parameters to compress the signature size while maintaining the computational efficiency of the signing algorithm, the signature size can be reduced by 125 to 221 bytes, depending on the security levels.