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\%$$ 47 % , $$22\%$$ 22 % , and $$17\%$$ 17 % 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\%$$ 1 % under the parameter set 2 of .
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% 47 % , 22% 22 % , and 17% 17 % 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% 1 % under the parameter set 2 of .
Rejection sampling technology is a core tool in the design of lattice-based signatures with ‘Fiat–Shamir with Aborts’ structure, and it is related to signing efficiency and signature, size as well as security. In the rejection sampling theorem proposed by Lyubashevsky, the masking vector of rejection sampling is chosen from discrete Gaussian distribution. However, in practical designs, the masking vector is more likely to be chosen from bounded uniform distribution due to better efficiency and simpler implementation. Besides, as one of the third-round candidate signatures in the NIST postquantum cryptography standardization process, the 3rd round version of CRYSTALS-Dilithium has proposed a new method to decrease the rejection probability in order to achieve better efficiency and smaller signature size by decreasing the number of nonzero coefficients of the challenge polynomial according to the security levels. However, it is seen that small entropies in this new method may lead to higher risk of forgery attack compared with former schemes proposed in its 2nd version. Thus, in this paper, we first analyze the complexity of forgery attack for small entropies and then introduce a new method to decrease the rejection probability without loss of security including the security against forgery attack. This method is achieved by introducing a new rejection sampling theorem with tighter bound by utilizing Rényi divergence where masking vector follows uniform distribution. By observing large gaps between the security claim and actual security bound in CRYSTALS-Dilithium, we propose two series of adapted parameters for CRYSTALS-Dilithium. The first set can improve the efficiency of the signing process in CRYSTALS-Dilithium by factors of 61.7 % and 41.7 % , according to the security levels, and ensure the security against known attacks, including forgery attack. And, the second set can reduce the signature size by a factor of 14.09 % with small improvements in efficiency at the same security level.
The lattice-based signature schemes are promising quantum-resistant replacements for classical signature schemes based on number theoretical hard problems. An important approach to construct lattice-based signature is utilizing the Fiat-Shamir transform and rejection sampling techniques. There are two Fiat-Shamir signatures among five lattice signature schemes submitted to the post-quantum project initiated by National Institute of Standards and Technology. One of them is called Dilithium, which is based on Module-Learning-With-Errors (MLWE) problem, it features on its simple design in the signing algorithm by using uniform sampling. The Dilithium is built on the generic lattices, to make the size of public key more compact, Dilithium adopts compression technique. On the other hand, schemes using NTRU lattices outperform schemes using generic lattices in efficiency and parameter sizes. This paper devotes to designing an efficient NTRU variant of Dilithium, by combining the advantage of NTRU and uniform rejection sampling, this scheme enjoys a concise structure and gains performance improvement over other lattice-based Fiat-Shamir signature without using extra compression techniques.
To overcome the issue of traditional blind signature schemes being vulnerable to quantum computing attacks during interactions over the consumer electronic Internet of Things (CIoT), a new blind signature scheme called CDBS has been developed. The post quantum digital signature technique CRYSTALS-Dilithium, which was standardized by NIST, serves as the foundation for the quantum-resistant blind signature scheme, CDBS, presented in this study. This system is appropriate for a variety of internet application scenarios, including e-ticketing, anonymous payments, and privacy protection, because it integrates the idea of blind signatures, which is not included in typical digital signature schemes. This scheme is designed to resist quantum computing attacks and is based on the post-quantum digital signature algorithm CRYSTALS-Dilithium, which NIST has selected. The whole technique utilizes the Fiat-Shamir signature structure, which consists of five stages: key creation, blinding, signing, unblinding, and verification. The security of the proposed scheme is dependent on the resolution of the Module Learning with Errors (MLWE) problem and the Short Integer Solution (SIS) problem. Additionally, the scheme must satisfy the criteria of correctness, blindness, and unforgeability. According to the test results, the CRYSTALS-Dilithium scheme requires an average of 401.89 μ s for a single round of verification and signing. The CDBS technique takes an average of 657.65 ls for one round of signing and verification since the blinding and unblinding modules are added on top of the original algorithm, increasing the algorithm’s complexity. The software testing results indicate that the average time required to complete a single full blind signature and verification operation is 657.65 microseconds. The suggested system offers a framework for expanding the CRYSTALS-Dilithium digital signature algorithm.
Since 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new postquantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution.MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm.At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speedup of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management.
Due to the scalability of the stateless and compact JSON Web Tokens (JWT), they are increasingly used in securing modern applications to support single-sign-on context and establish trust in microservices or connected-devices architectures. However, currently JWT relies on traditional encryption algorithms that are based on integer factorization or discrete logarithm problems; this exposes JWT signatures to vulnerability when quantum computers become available. Recently, NIST has announced new standards which are quantum safe. In this paper, we investigate the usage of two quantum-resistant algorithms, which are NIST candidates of round 2 standardization process in 2019, to create and verify JWT signatures. Namely, we consider lattice-based schemes (DILITHIUM and qTESLA) and compare their performance against RSA for digital signature for different security levels defined by NIST. The results show that lattice-based digital signature schemes have better performance than RSA in terms of request per seconds and average response time. DILITHIUM has demonstrated the best performance while also having smaller performance loss when scaling the security level.
The MPC-in-the-Head paradigm is a promising approach for constructing post-quantum signatures, and its variants VOLE-in-the-Head (VOLEitH) and TC-in-the-Head (TCitH) are adopted in some NIST PQC candidates. Recent works by Aguilar-Melchor et al. (ASIACRYPT 2023), Hülsing et al. (CRYPTO 2024), and Baum et al. (CRYPTO 2025) establish EUF-CMA security for MPCitH/VOLEitH in the quantum random oracle model (QROM), but these proofs either ignore crucial optimizations such as rejection sampling and grinding or rely on round-by-round soundness and key-generation lossiness. Due to these restrictions, they do not directly apply to TCitH signatures such as Mirath, RYDE, or MQOM. This paper addresses this gap by analyzing the QROM security of TCitH signatures that incorporate the crucial optimizations. Our treatment of rejection sampling and grinding applies more generally to MPCitH signatures, while our complete security proofs are instantiated for the TCitH signatures Mirath and RYDE. Our contributions are twofold: 1) We provide a new (strong) EUF-CMA security proof that accommodates rejection sampling and grinding. 2) We identify a gap in the EUF-CMA proof of MQOM and show that this issue extends to some schemes, including SBC (Huth and Joux, CRYPTO 2024) and rBN++ (Kim, Lee, and Son, EUROCRYPT 2025).