Efficient Lattice-based Digital Signature Scheme in Large-Galois-group Prime-degree Prime-ideal Field
Author:
Affiliation:

Clc Number:

TP309

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • 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
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:October 19,2023
  • Revised:January 03,2024
  • Adopted:
  • Online: October 30,2024
  • Published:
You are the firstVisitors
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