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, 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 pap...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2025-02-01
|
| Series: | Cybersecurity |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s42400-024-00325-6 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1823861940199358464 |
|---|---|
| author | Lianglin Yan Ming Luo Mingsheng Wang |
| author_facet | Lianglin Yan Ming Luo Mingsheng Wang |
| author_sort | Lianglin Yan |
| collection | DOAJ |
| description | Abstract 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\%$$ 47 % , $$22\%$$ 22 % , and $$17\%$$ 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\%$$ 1 % under the parameter set 2 of Dilithium. |
| format | Article |
| id | doaj-art-0e4ca63fd17e4f898acbc2bb3749dd80 |
| institution | Kabale University |
| issn | 2523-3246 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Cybersecurity |
| spelling | doaj-art-0e4ca63fd17e4f898acbc2bb3749dd802025-02-09T12:43:01ZengSpringerOpenCybersecurity2523-32462025-02-018111510.1186/s42400-024-00325-6Speedup signing: pre-rejection sampling towards dilithiumLianglin Yan0Ming Luo1Mingsheng Wang2Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of SciencesKey Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of SciencesKey Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of SciencesAbstract 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\%$$ 47 % , $$22\%$$ 22 % , and $$17\%$$ 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\%$$ 1 % under the parameter set 2 of Dilithium.https://doi.org/10.1186/s42400-024-00325-6Post-quantum signatureMLWEPre-rejection sampling |
| spellingShingle | Lianglin Yan Ming Luo Mingsheng Wang Speedup signing: pre-rejection sampling towards dilithium Cybersecurity Post-quantum signature MLWE Pre-rejection sampling |
| title | Speedup signing: pre-rejection sampling towards dilithium |
| title_full | Speedup signing: pre-rejection sampling towards dilithium |
| title_fullStr | Speedup signing: pre-rejection sampling towards dilithium |
| title_full_unstemmed | Speedup signing: pre-rejection sampling towards dilithium |
| title_short | Speedup signing: pre-rejection sampling towards dilithium |
| title_sort | speedup signing pre rejection sampling towards dilithium |
| topic | Post-quantum signature MLWE Pre-rejection sampling |
| url | https://doi.org/10.1186/s42400-024-00325-6 |
| work_keys_str_mv | AT lianglinyan speedupsigningprerejectionsamplingtowardsdilithium AT mingluo speedupsigningprerejectionsamplingtowardsdilithium AT mingshengwang speedupsigningprerejectionsamplingtowardsdilithium |