Security and efficiency have always been two critical factors in the development of post-quantum digital signatures. As the best-known scheme, Dilithium (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 KeyGen stage to reduce the rejections of the fourth condition, consequently resulting in some speedup in Sign 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 Dilithium, 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\%\) , \(22\%\) , and \(17\%\) reduction in the rejection probability of the fourth condition over Dilithium 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\%\) under the parameter set 2 of Dilithium.
