素阶数域上的高效紧凑NTRU密钥封装方案  

Efficient and Compact NTRU-based Key Encapsulation Mechanism in Large-Galois-group Prime-degree Prime-ideal Number Field

作　　者：梁志闯 赵旭阳 方博越 赵运磊 LIANG Zhi-Chuang;ZHAO Xu-Yang;FANG Bo-Yue;ZHAO Yun-Lei(School of Computer Science,Fudan University,Shanghai 200433,China;State Key Laboratory of Cryptology,Beijing 100036,China)

机构地区：[1]复旦大学计算机科学技术学院,上海200433 [2]密码科学技术国家重点实验室,北京100036

出　　处：《软件学报》2025年第2期747-775,共29页Journal of Software

基　　金：国家自然科学基金(61877011);国家重点研发计划(2022YFB2701600);上海市科学技术发展基金(21DZ2200500);山东省重点研发计划(2017CXG0701,2018CXGC0701)。

摘　　要：基于格(特别是NTRU格)设计后量子密钥封装方案是格密码领域的主流方向之一.现有多数格密码方案基于分圆环构造,但分圆环饱含丰富的代数结构导致这些方案容易遭受相关攻击.一个可选的且更安全的代数结构是大Galois群、素数阶、基于素理想的数域(简称为素阶数域).NTRU-Prime是一个基于素阶数域的备受青睐的NTRU密钥封装方案,且早已经在国际标准OpenSSH中默认应用.旨在设计出比NTRU-Prime性能更优的素阶数域上NTRU密钥封装方案.首先,梳理分圆环的安全隐患,特别是针对2次幂分圆环的系列攻击,同时展示出素阶数域在抵御这些攻击方面的安全优势.接着,基于素阶数域提出NTRU密钥封装方案CNTR-Prime,并给出详细的相关分析和参数集.然后,提出一种伪梅森数不完整NTT,它能有效计算CNTR-Prime中关于素阶数域的多项式乘法.此外,还提出一种改进的伪梅森数约减算法,并将它应用在伪梅森数不完整NTT中.它在软件实现方面比Barrett约减快2.6%,在硬件实现方面比Montgomery约减和Barrett约减快2–6倍.最后,提供CNTR-Prime的C语言实现,并与其他同类方案进行全面对比.结果表明,与SNTRU-Prime相比,CNTR-Prime在安全强度、带宽和实现效率上有优势,其中CNTR-Prime-761的经典和量子安全强度都比SNTRU-Prime-761的高19 bit,密文尺寸降低8.3%,密钥生成算法、密钥封装算法和解封装算法分别快25.3倍、10.8倍和2.0倍.实际上,CNTR-Prime-653的经典和量子安全强度已可与SNTRU-Prime-761相媲美,且CNTR-Prime-653的带宽降低13.8%,密钥生成算法、密钥封装算法和解封装算法分别快33.9倍、12.6倍和2.3倍.所提工作可为后续同类型的格密码方案的设计、分析和优化实现提供重要参考.Constructing post-quantum key encapsulation mechanisms based on Lattice(especially NTRU Lattice)is one of the popular research fields in Lattice-based cryptography.Commonly,most Lattice-based cryptographic schemes are constructed over cyclotomic rings,which,however,are vulnerable to some attacks due to their abundant algebraic structures.An optional and more secure underlying algebraic structure is the large-Galois-group prime-degree prime-ideal number field.NTRU-Prime is an excellent NTRU-based key encapsulation mechanism over the large-Galois-group prime-degree prime-ideal number field and has been widely adopted as the default in the OpenSSH standard.This study aims to construct a key encapsulation mechanism over the same algebraic structure but with better performance than NTRU-Prime.Firstly,this work studies the security risks of cyclotomic rings,especially the attacks on quadratic power cyclotomic rings,and demonstrates the security advantages of a large-Galois-group prime-degree prime-ideal number field in resisting these attacks.Next,an NTRU-based key encapsulation mechanism named CNTR-Prime over a large-Galois-group prime-degree prime-ideal number field is proposed,along with the corresponding detailed analysis and parameter sets.Then,a pseudo-Mersenne incomplete number theoretic transform(NTT)is provided,which can compute polynomial multiplication efficiently over a large-Galois-group prime-degree prime-ideal number field.In addition,an improved pseudo-Mersenne modular reduction algorithm is proposed,which is utilized in pseudo-Mersenne incomplete NTT.It is faster than Barrett reduction by 2.6%in software implementation and is 2 to 6 times faster than both Montgomery reduction and Barrett reduction in hardware implementation.Finally,a C-language implementation of CNTR-Prime is presented.When compared to SNTRU-Prime,CNTR-Prime has advantages in security,bandwidth,and implementation efficiency.For example,CNTR-Prime-761 has an 8.3%smaller ciphertext size,and its security is strengthened by 19 bits for bot

关 键 词：格密码 后量子密码 数论研究单元(NTRU) 素阶数域 密钥封装方案 数论变换 模约减 软件实现 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]