微信服务号

微信订阅号

2025-4-5- 13
Home > Archive>Volume 36, Issue 2, 2025 >776-804. DOI:10.13328/j.cnki.jos.007164
PDF HTML XML Export Cite reminder
Efficient Lattice-based Digital Signature Scheme in Large-Galois-group Prime-degree Prime-ideal Field
Author:
Affiliation:

Clc Number:

TP309

  • Article
    • | |
  • Metrics
    • |
  • Reference [60]
    • | | | |
  • Comments
    Abstract:

    With the rapid development of quantum computing, especially the optimization and progress of the Shor quantum algorithm and its variants, the current classical public-key cryptography based on factoring large integers and discrete logarithm problems is facing serious security threats. To cope with quantum attacks, post-quantum cryptography has been proposed, among which lattice-based cryptography is commonly viewed as the most promising one due to its outstanding performance in security, bandwidth, and efficiency. Most of the existing lattice-based post-quantum cryptographic schemes use cyclotomic rings, especially power-of-two cyclotomic rings, as their underlying algebraic structures. However, targeted attacks against cyclotomic rings have been proposed, exploiting subfields, small Galois groups, and ring homomorphisms in these rings. This study uses the large-Galois-group prime-degree prime-ideal field as the new underlying algebraic structure, which has characteristics of high security, prime order, large Galois group, and inert modulus.First, this study proposes a post-quantum digital signature scheme based on the large-Galois-group prime-degree prime-ideal field, which is named Dilithium-Prime, and the recommended parameter sets are provided. Next, considering that the traditional number theory transform (NTT) algorithm cannot be used to multiply polynomials efficiently in the large-Galois-group prime-degree prime-ideal field, this study designs efficient polynomial multiplication strategies for Dilithium-Prime, including NTT for the large-Galois-group prime-degree prime-ideal field and small polynomial multiplication. Finally, this study provides a portable C language implementation of Dilithium-Prime, along with the implementation details and constant-time implementation skills, and compares Dilithium-Prime with other lattice-based digital signature schemes. The experimental results show that the public key size, secret key size, and signature size of Dilithium-Prime are reduced by 1.8%, 10.2%, and 1.8%, respectively, compared to CRYSTALS-Dilithium. The efficiency of the signature algorithm is improved by 11.9%, and the key generation algorithm and the verification algorithm are 2.0× and 2.5× slower than those of CRYSTALS-Dilithium, respectively. However, Dilithium-Prime can withstand the cryptographic attack against cyclotomic rings, which is exactly what CRYSTALS Dilithium lacks. Compared to NCC-Sign, Dilithium-Prime’s key generation algorithm, signature algorithm, and verification algorithm are 4.2×, 35.3×, and 7.2× faster, respectively, than those of NCC-Sign under the same security level and bandwidth.

    Reference
    [1] Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 1999, 41(2): 303–332.
    [2] Regev O. An efficient quantum factoring algorithm. arXiv:2308.06572, 2023.
    [3] NIST. PQC standardization process: Announcing four candidates to be standardized, plus fourth round candidates. 2022. https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
    [4] 中国密码学会. 关于全国密码算法设计竞赛算法评选结果的公示. 2020. https://www.cacrnet.org.cn/site/content/854.html
    Chinese Association for Cryptologic Research. Announcement of the selection results of the national cryptographic algorithm competitions. 2020 (in Chinese). https://www.cacrnet.org.cn/site/content/854.html
    [5] Regev O. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 2009, 56(6): 34.
    [6] Banerjee A, Peikert C, Rosen A. Pseudorandom functions and lattices. In: Proc. of the 31st Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Cambridge: Springer, 2012. 719–737. [doi: 10.1007/978-3-642-29011-4_42]
    [7] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In: Proc. of the 29th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. French Riviera: Springer, 2010. 1–23. [doi: 10.1007/978-3-642-13190-5_1]
    [8] Langlois A, Stehlé D. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 2015, 75(3): 565–599.
    [9] Avanzi R, Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck JM, Schwabe P, Seiler G, Stehlé D. CRYSTALS-Kyber: Algorithm specifications and supporting documentation (version 3.01). 2021. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf
    [10] Basso A, Mera JMB, D’Anvers JP, Karmakar A, Sinha Roy S, van Beirendonck M, Vercauteren F. SABER: Mod-LWR based KEM (round 3 submission). 2023. https://www.esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround3.pdf
    [11] Bai S, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schwabe P, Seiler G, Stehlé D. CRYSTALS-Dilithium algorithm specifications and supporting documentation (version 3.1). 2021. https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf
    [12] Fouque PA, Hoffstein J, Kirchner P, Lyubashevsky V, Pornin T, Prest T, Ricosset T, Seiler G, Whyte W, Zhang ZF. Falcon: Fast-Fourier lattice-based compact signatures over NTRU (specification v1.2). 2020. https://falcon-sign.info/falcon.pdf
    [13] Smart NP, Vercauteren F. Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Proc. of the 13th Int’l Workshop on Public Key Cryptography. Paris: Springer, 2010. 420–443. [doi: 10.1007/978-3-642-13013-7_25]
    [14] Campbell P, Groves M, Shepherd D. Soliloquy: A cautionary tale. In: Proc. of the 2nd ETSI Quantum-safe Crypto Workshop in Partnership with the IQC. Ottawa, 2014. 1–9.
    [15] Biasse JF, Song F. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: Proc. of the 27th Annual ACM-SIAM Symp. on Discrete Algorithms. Arlington: SIAM, 2016. 893–902.
    [16] Cramer R, Ducas L, Wesolowski B. Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time. Journal of the ACM, 2021, 68(2): 8.
    [17] Bernstein DJ, Lange T. Non-randomness of S-unit lattices. 2021. https://eprint.iacr.org/2021/1428
    [18] Bernstein DJ, Brumley B, Chen MS, Chuengsatiansup C, Lange T, Marotzke A, Peng BY, Tuveri N, van Vredendaal C, Yang BY. NTRU Prime: Round 3. 2020. https://ntruprime.cr.yp.to/nist.html
    [19] Bernstein DJ, Chuengsatiansup C, Lange T, van Vredendaal C. NTRU prime: Reducing attack surface at low cost. In: Proc. of the 24th Int’l Conf. on Selected Areas in Cryptography. Ottawa: Springer, 2018. 235–260. [doi: 10.1007/978-3-319-72565-9_12]
    [20] Alkim E, Cheng DYL, Chung CMM, Evkan H, Huang LWL, Hwang V, Li CLT, Niederhagen R, Shih CJ, Wälde J, Yang BY. Polynomial multiplication in NTRU prime: Comparison of optimization strategies on Cortex-M4. IACR Trans. on Cryptographic Hardware and Embedded Systems, 2020, 2021(1): 217–238.
    [21] OpenSSH Release Notes. OpenSSH 9.0/9.0p1. 2022. https://www.openssh.com/releasenotes.html
    [22] Ajtai M. Generating hard instances of lattice problems. In: Proc. of the 28th Annual ACM Symp. on Theory of Computing. Philadelphia: ACM, 1996. 99–108. [doi: 10.1145/237814.237838]
    [23] Goldreich O, Goldwasser S, Halevi S. Public-key cryptosystems from lattice reduction problems. In: Proc. of the 17th Annual Int’l Cryptology Conf. on Advances in Cryptology. Santa Barbara: Springer, 1997. 112–131. [doi: 10.1007/BFb0052231]
    [24] Hoffstein J, Howgrave-Graham N, Pipher J, Silverman JH, Whyte W. NTRUSign: Digital signatures using the NTRU lattice. In: Cryptographers’ Track at the RSA Conf. on Topics in Cryptology. San Francisco: Springer, 2003. 122–140. [doi: 10.1007/3-540-36563-X_9]
    [25] Nguyen PQ, Regev O. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In: Proc. of the 25th Int’l Conf. on the Theory and Applications of Cryptographic Techniques. St. Petersburg: Springer, 2006. 271–288. [doi: 10.1007/11761679_17]
    [26] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In: Proc. of the 40th Annual ACM Symp. on Theory of Computing. Victoria: ACM, 2008. 197–206. [doi: 10.1145/1374376.1374407]
    [27] Lyubashevsky V. Lattice signatures without trapdoors. In: Proc. of the 31st Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Cambridge: Springer, 2012. 738–755. [doi: 10.1007/978-3-642-29011-4_43]
    [28] Güneysu T, Lyubashevsky V, Pöppelmann T. Practical lattice-based cryptography: A signature scheme for embedded systems. In: Proc. of the 14th Int’l Workshop on Cryptographic Hardware and Embedded Systems. Leuven: Springer, 2012. 530–547. [doi: 10.1007/978-3-642-33027-8_31]
    [29] Bai S, Galbraith SD. An improved compression technique for signatures based on learning with errors. In: Proc. of the 2014 Cryptographer’s Track at the RSA Conf. on Topics in Cryptology. San Francisco: Springer, 2014. 28–47. [doi: 10.1007/978-3-319-04852-9_2]
    [30] Shim KA, Kim J, An Y. NCC-Sign: A new lattice-based signature scheme using non-cyclotomic polynomials. 2023. https://www.kpqc.or.kr/images/pdf/NCC-Sign.pdf
    [31] Kiltz E, Lyubashevsky V, Schaffner C. A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. In: Proc. of the 37th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Tel Aviv: Springer, 2018. 552–586. [doi: 10.1007/978-3-319-78372-7_18]
    [32] Bernstein DJ. Multidigit multiplication for mathematicians. 2001. http://cr.yp.to/papers.html#m3
    [33] Cooley JW, Tukey JW. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 1965, 19(90): 297–301.
    [34] Gentleman WM, Sande G. Fast Fourier transforms: For fun and profit. In: Proc. of the 1966 AFIPS Fall Joint Computer Conf. San Francisco: ACM, 1966. 563–578. [doi: 10.1145/1464291.1464352]
    [35] Cramer R, Ducas L, Peikert C, Regev O. Recovering short generators of principal ideals in cyclotomic rings. In: Proc. of the 35th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Vienna: Springer, 2016. 559–585. [doi: 10.1007/978-3-662-49896-5_20]
    [36] Biasse JF, Song F. On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in $ \makescalebox{0.8} {\mathbb{Q}({{\zeta }_{{{2}^{s}}}}) }$. Journal of Mathematical Cryptology, 2019, 13(3–4): 151–168.
    [37] Eisenträger K, Hallgren S, Kitaev A, Song F. A quantum algorithm for computing the unit group of an arbitrary degree number field. In: Proc. of the 46th ACM Symp. on Theory of Computing. New York: ACM, 2014. 293–302. [doi: 10.1145/2591796.2591860]
    [38] Laarhoven T. Sieving for closest lattice vectors (with preprocessing). In: Proc. of the 2016 Int’l Conf. on Selected Areas in Cryptography. Cham: Springer, 2016.
    [39] Pellet-Mary A, Hanrot G, Stehlé D. Approx-SVP in ideal lattices with pre-processing. In: Proc. of the 38th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Darmstadt: Springer, 2019. 685–716. [doi: 10.1007/978-3-030-17656-3_24]
    [40] Bernstein DJ. Fast norm computation in smooth-degree Abelian number fields. 2022. https://eprint.iacr.org/2022/980
    [41] Duc A, Tramèr F, Vaudenay S. Better algorithms for LWE and LWR. In: Proc. of the 34th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Sofia: Springer, 2015. 173–202. [doi: 10.1007/978-3-662-46800-5_8]
    [42] Buchmann J, Göpfert F, Player R, Wunderer T. On the hardness of LWE with binary error: Revisiting the hybrid lattice-reduction and meet-in-the-middle attack. In: Proc. of the 8th Int’l Conf. on Cryptology in Africa. Fes: Springer, 2016. 24–43. [doi: 10.1007/978-3-319-31517-1_2]
    [43] Albrecht MR. On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL. In: Proc. of the 36th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Paris: Springer, 2017. 103–129. [doi: 10.1007/978-3-319-56614-6_4]
    [44] Cheon JH, Hhan M, Hong S, Son Y. A hybrid of dual and meet-in-the-middle attack on sparse and ternary secret LWE. IEEE Access, 2019, 7: 89497–89506.
    [45] Guo Q, Johansson T. Faster dual lattice attacks for solving LWE with applications to CRYSTALS. In: Proc. of the 27th Int’l Conf. on the Theory and Application of Cryptology and Information Security. Singapore: Springer, 2021. 33–62. [doi: 10.1007/978-3-030-92068-5_2]
    [46] MATZOV. Report on the security of LWE: Improved dual lattice. 2022. https://zenodo.org/record/6412487
    [47] Bauch J, Bernstein DJ, de Valence H, Lange T, van Vredendaal C. Short generators without quantum computers: The case of multiquadratics. In: Proc. of the 36th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Paris: Springer, 2017. 27–59. [doi: 10.1007/978-3-319-56620-7_2]
    [48] Eisenträger K, Hallgren S, Lauter K. Weak instances of PLWE. In: Proc. of the 21st Int’l Conf. on Selected Areas in Cryptography. Montreal: Springer, 2014. 183–194. [doi: 10.1007/978-3-319-13051-4_11]
    [49] Chen H, Lauter KE, Stange KE. Security considerations for Galois non-dual RLWE families. IACR Cryptology ePrint Archive, Paper ID: 2016/193. https://eprint.iacr.org/2016/193
    [50] Poddebniak D, Somorovsky J, Schinzel S, Lochter M, Rösler P. Attacking deterministic signature schemes using fault attacks. In: Proc. of the 2018 IEEE European Symp. on Security and Privacy (EuroS&P). London: IEEE, 2018. 338–352. [doi: 10.1109/EuroSP.2018.00031]
    [51] Samwel N, Batina L, Bertoni G, Daemen J, Susella R. Breaking Ed25519 in WolfSSL. In: Proc. of the 2018 Cryptographers’ Track at the RSA Conf. on Topics in Cryptology. San Francisco: Springer, 2018. 1–20. [doi: 10.1007/978-3-319-76953-0_1]
    [52] Alkim E, Ducas L, Pöppelmann T, Schwabe P. Post-quantum key exchange: A new hope. In: Proc. of the 25th USENIX Security Symp. (USENIX Security 16). Austin: USENIX Association, 2016. 327–343.
    [53] Chen YM, Nguyen PQ. BKZ 2.0: Better lattice security estimates. In: Proc. of the 17th Int’l Conf. on the Theory and Application of Cryptology and Information Security. Seoul: Springer, 2011. 1–20. [doi: 10.1007/978-3-642-25385-0_1]
    [54] Bai S, Galbraith SD. Lattice decoding attacks on binary LWE. In: Proc. of the 19th Australasian Conf. on Information Security and Privacy. Wollongong: Springer, 2014. 322–337. [doi: 10.1007/978-3-319-08344-5_21]
    [55] Zheng JY, He F, Shen SY, Xue CX, Zhao YL. Parallel small polynomial multiplication for Dilithium: A faster design and implementation. In: Proc. of the 38th Annual Computer Security Applications Conf. Austin: ACM, 2022. 304–317. [doi: 10.1145/3564625.3564629]
    [56] Kocher PC. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Proc. of the 16th Annual Int’l Cryptology Conf. on Advances in Cryptology. Santa Barbara: Springer, 1996. 104–113. [doi: 10.1007/3-540-68697-5_9]
    [57] Montgomery PL. Modular multiplication without trial division. Mathematics of Computation, 1985, 44(170): 519–521.
    [58] Barrett P. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In: Odlyzko AM, ed. Proc. of the 1987 Conf. on the Theory and Application of Cryptographic Techniques (CRYPTO 1986). Berlin, Heidelberg: Springer, 1987. 311–323. [doi: 10.1007/3-540-47721-7_24]
    [59] Granlund T, Montgomery PL. Division by invariant integers using multiplication. In: Proc. of the 1994 ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). Orlando: ACM, 1994. 61–72. [doi: 10.1145/178243.178249]
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

董怡帆,方博越,梁志闯,赵运磊.素阶数域上的高效格基数字签名方案.软件学报,2025,36(2):776-804

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:October 19,2023
  • Revised:January 03,2024
  • Online: October 30,2024
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033169Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063