Speedup signing: pre-rejection sampling towards dilithium

Abstract Security and efficiency have always been two critical factors in the development of post-quantum digital signatures. As the best-known scheme, (Ducas et al., TCHES 2018) is SUF-CMA in QROM and has a relatively fast efficiency with many untrivial optimizations. The goal of this paper is to propose some techniques that can promote signing speed without sacrificing security. We first propose the pre-rejection sampling technique in stage to reduce the rejections of the fourth condition, consequently resulting in some speedup in stage. To prove security, we propose the c -selected MLWE problem, a variant of MLWE that can offer the equivalent security as original MLWE. Applying these two techniques to , we obtain an advanced signature scheme with better efficiency, and without any other losses except some pre-computations. Security reduction demonstrates that our scheme is also SUF-CMA in QROM. The experimental results show that pre-rejection sampling achieves a $$47\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>47</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> , $$22\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>22</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> , and $$17\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>17</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> reduction in the rejection probability of the fourth condition over scheme when the parameter set corresponds to NIST’s security levels 2, 3 and 5, respectively. This type of reduction increases signing speed by approximately $$1\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> under the parameter set 2 of .