基于理想格的公钥加密方案快速实现技术研究.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(4):852861密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]基于理想格的公钥加密方案快速实现技术研究*王伯宇,高海英信息工程大学,郑州 450001通信作者:高海英,E-mail:摘要:在基于理想格和模格的公钥加密方案中,多项式环上的乘法运算是影响方案实现效率的重要模块,而该模块通常可通过数论变换(number theoretic transform,NTT)来快速实现.本文采用结合Karatsuba 算法的带预处理的 NTT(preprocess-then-NTT with Karatsuba,KNTT),提升格公钥加密方案的实现效率.在使用 KNTT 前,通过改进采样和密文打(解)包结果的存储方式来调整多项式环元素的数据结构,使之直接适用 KNTT,从而省去 KNTT 算法中的预处理和组合环节.改进了 KNTT 中的 NTT 变换的实现方式,进一步提高格公钥加密方案的实现效率.KYBER 是 NIST 在第三轮评选中决定标准化的格公钥密码算法,本文将上述改进技术应用于 KYBER 类加密方案,得到了 KNTT-basedKYBER 算法,与 KYBER.CPAPKE 相比,密钥生成实现效率提高了 5%8%,加密实现效率提高了 7%10%,解密实现效率提高了 9%10%.关键词:格公钥密码;容错学习问题;KYBER 类加密方案;数论变换;结合 Karatsuba 的带预处理的数论变换中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000633中文引用格式:王伯宇,高海英.基于理想格的公钥加密方案快速实现技术研究J.密码学报,2023,10(4):852861.DOI:10.13868/ki.jcr.000633英文引用格式:WANG B Y,GAO H Y.Research on fast implementation of ideal lattice-based public-key en-cryption schemeJ.Journal of Cryptologic Research,2023,10(4):852861.DOI:10.13868/ki.jcr.000633Research on Fast Implementation of Ideal Lattice-Based Public-KeyEncryption SchemeWANG Bo-Yu,GAO Hai-YingInformation Engineering University,Zhengzhou 450001,ChinaCorresponding author:GAO Hai-Ying,E-mail:Abstract:In the implementation of public-key encryption schemes based on ideal lattice and modulelattice,the multiplication on polynomial ring is an important module that affects the implementationefficiency of the scheme.The number theoretic transform(NTT)is often utilized to speed up theimplementation of the operation.In this paper,a technique called preprocess-then-NTT with Karat-suba(KNTT)algorithm is used to improve the implementation efficiency of the public-key encryptionscheme.Before KNTT is used,the data structure of polynomial ring elements is adjusted to be suitablefor KNTT by improving the storage mode of sampling and cipher-text packing(unpacking)results,so*基金项目:国家自然科学基金(61902428,61702548)Foundation:National Natural Science Foundation of China(61902428,61702548)收稿日期:2022-08-30定稿日期:2023-01-19王伯宇 等:基于理想格的公钥加密方案快速实现技术研究853as to remove the pre-processing and combination of KNTT algorithm.The implementation of NTTtransform in KNTT is optimized to further improve the implementation efficiency of lattice-basedpublic-key encryption scheme.KYBER was determined to be standardized in the third round of NISTevaluation.This paper applies the above improvements to the KYBER-like encryption schemes toget KNTT-based KYBER.Compared with KYBER.CPAPKE,KNTT-based KYBER is 5%8%moreefficient in key generation,7%10%in encryption,and 9%10%in decryption.Key words:lattice-based public-key cryptography;learning with Errors;KYBER-like cryptography;number theoretic transform;preprocess-then-NTT with Karatsuba1引言抗量子密码是密码领域当前的研究热点之一.为应对量子计算技术给传统公钥密码带来的挑战,美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)发起了抗量子密码算法标准化工作.在第 3 轮的 9 个入围和备选加密算法中,有 5 个基于格的方案,其中三个基于容错学习问题1(learning with errors,LWE)及其变体问题,即基于 LWE 问题的 FrodoKem2、基于模上容错学习问题3(module learning with errors,MLWE)的 KYBER4和基于模上带舍入的学习问题5(modulelearning with rounding,MLWR)的 SABER6.KYBER 经三轮评选后被确定为第一批标准化抗量子密码中唯一的加密算法.在 NIST 评选中,方案的实现效率是衡量算法性能的重要指标.对于具有代数结构的算法,如 KYBER、SABER 和进入 NIST 第二轮的基于环上容错学习问题7(ring learning with errors,RLWE)的 NewHope8,多项式环上乘法是整个算法中耗时较多而必不可少的环节.得益于其所基于的多项式环的特殊结构,KYBER 和 NewHope 使用快速数论变换(number theoretic transform,NTT)技术快速实现多项式环上乘法.NTT 是高效实现多项式环上乘法的技术.在多项式环 Rq=Zqx/(xn+1)中,q 是素数,n=2m,m Z+中,两个多项式的乘积对应于系数向量的循环卷积.如果 q 和 n 满足 q 1 mod 2n,也就是存在Zq上的 2n 次单位根,即可通过 NTT 高效计算多项式乘法.很多研究者对 NTT 技术进行了改进,相继提出了 NTT 变体算法.Zhou9等人在 Inscrypt 2018 上提出了带预处理的 NTT(preprocess-then-NTT,PtNTT).设参与乘法运算的 2 个 Rq上的多项式是 f 和 g.1 轮预处理的 PtNTT(1PtNTT)是将 f 和 g 按脚标奇偶性分成 4 个 Zqx/(xn/2+1)上的多项式,可记成 2 个奇式、2 个偶式,拆分多项式的过程即是预处理过程.f g 也可用 Zqx/(xn/2+1)上两个多项式计算得到.利用上述 2 个奇式、2 个偶式以及一个中间式的 NTT 正向变换(记为 NTT.为避免混淆,本文中“NTT”表示数论变换这项技术,“NTT”表示数论变换中的正向变换),再利用两个 NTT 逆向变换(记为 NTT1)求出 f g.该方法将 n 和 q 的限制条件降低至 n|(q 1),增大了 q 的选取范围.但其增加了中间式的 NTT(可认为增加了整数模 q 乘的次数),因此,PtNTT 计算效率低于最初的 NTT.类似地,对于 轮的 PtNTT(PtNTT),n 和 q 只需满足(n/21)|(q 1),但效率随着轮数的增加而降低.在 KYBER 算法4中,采用的是另一种 NTT 变体算法.将(xn+1)拆分成 n/2 个 2 次多项式.对参与乘法的 Rq上的多项式 f,进行 logn 1 层的 NTT,将 n 个 NTT 系数两两组合,组成 n/2 个 1 次多项式,最终 NTT(f)可表示为 n/2 个 1 次多项式的形式,同理计算出 NTT(g).由于 NTT(f)NTT(g)需要用到 n/2 个 1 次多项式的乘法运算,因此,该方法与使用完整的 NTT 做多项式乘法效率相同,但使得 q 的取值范围从满足 q 1 mod 2n 扩大到了满足 q 1 mod n.Zhu 等人10提出了一种与 Karatsuba 算法11,12结合的带预处理的 NTT(preprocess-then-NTTwith Karatsuba,KNTT)技术,其实现效率优于 NTT.KNTT 的预处理过程与 PtNTT 相同,但 KNTT并没有使用蝶形变换,而是利用预计算的一次项 NTT 变换后的结果,结合 Karatsuba 算法的部分思想完成乘法运算,从而减少了对应项点乘和 NTT 的次数,优化了实现效率.1.1本文贡献本文研究了格公钥加密方案快速实现技术,主要贡献如下:854Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023(1)通过改进 Rq上元素存储方式,使之适合使用 KNTT,省去了 KNTT 中的预处理过程和组合过程,从而提高了格公钥加密方案的实现效率.(2)改进 NTT 和逆 NTT 的实现方式,节省了其 C 代码实现中 for 循环次数,降低了时间复杂度.(3)将上述快速实现技术应用到 KYBER 类加密方案中,用 1 轮预处理的 KNTT 技术代替 NIST 第三轮的 KYBER 中的 NTT 技术,得到 KNTT-based KYBER 算法,可以看做是 KYBER 算法的一个变形.实验结果表明,在相同参数设置下,相比于 KYBER.CPAPKE 算法,KNTT-based KYBER 算法的密钥生成的效率提高了 5%8%,加密提高了 7%10%,解密提高了 9%10%.1.2组织结构本文的组织结构如下:第2节介绍预备知识和符号约定,给出了 KYBER 类加密方案的定义.第3节给出了使用 KNTT 技术改进格公钥加密方案的方法.第4节给出实验结果.第5节给出结论.2预备知识Z 表示整数环,对于整数 q 1,Zq表示模 q 剩余类环,即 Zq=0,1,q1,Rq=Zqx/(xn+1)表示系数取自 Zq的多项式模 xn+1 构成的多项式环.对于 Rq中的任一元素 f,将其记作f=n1i=0fixi,其中 fi Zq.f 也可表示成由多项式系数组成的向量,即 f (fn1,fn2,f0).对f,g Rq,f 和 g 的点乘记为 f g,即 f g (fn1gn1mod q,fn2gn2mod q,f0 g0mod q).f 和 g 的乘积(也称为循环卷积)记为 f g,令 h=f g Rq,即hi=(ij=0fjgijn1j=i+1fjgn+ij)mod q.(1)可见需要进行 n2次模乘.2.1基于 NTT 的 Rq上的乘法运算NTT、NTT1分别表示 NTT 正向变换和逆向变换,它们结合 Rq上的点乘运算能快速实现 Rq上的乘法运算13.设 n 是 2 的幂,q 是满足 q 1 mod 2n 的素数,是 Zq的 n 次本原根,即 n 1 mod q,令 =即 是 Zq上的 2n 次本原根.NTT 正向变换 NTT 可描述为:对 f Rq,令f=NTT(f),f(fn1,fn2,f0),其中fi=n1j=0jfj ijmod q.本文用 来表示 NTT().相应地,NTT逆向变换 NTT1可描述为,对 f Rq,令 f=NTT1(f),则 fi=n1n1j=0ifj ijmod q.令h=f g,可使用 NTT 和 NTT1计算出 f g,计算方法是h=NTT1(NTT(f)NTT(g),(2)包括两个 NTT 变换、一个 NTT1变换和一个 n 长的向量点乘运算.NTT 正向变换和逆向变换可用“分而治之”的策略快速实现14.具体地讲,KYBER 基于 Cooley-Tukey(CT)蝴蝶变换15实现 NTT,基于 Gentleman-Sande(GS)蝴蝶变换16实现 NTT1,本文讨论的 NTT 和 NTT1亦是如此.由于参与计算的 的幂次可以预先计算并建表存储,NTT 的实现包含n2logn 次模乘,NTT1的实现包含n2logn+n 次模乘,故利用 NTT 技术实现 Rq上的乘法运算,需要模乘的次数为32nlogn+2n.需要注意的是,经过这样实现的 NTT 和 NTT1后,多项式系数都是脚标比特翻转后的结果.所谓比特翻转,即对长度不大于 m 比特的正整数 k=km12m1+km22m2+k12+k0,其中k0,k1,km1 0,1,用 brv(k)表示 k 比特翻转后的结果,那么 brv(k)=k02m1+k12m2+km22+km1.为了配合 NTT 的蝴蝶变换,的幂次建表时也要按照从指数 0 到 n1 比特翻转的位置来建表.王伯宇 等:基于理想格的公钥加密方案快速实现技术研究8552.2结合 Karatsuba 算法的 PtNTT(KNTT)文献 10 提出了 KNTT 变换,与 NTT 的区别在于:将 f 和 g 各自预处理成 2个较短的多项式,利用对这些较短多项式的 NTT 变换、系数向量对应项点乘和 NTT1变换,按照 Karatsuba 算法计算系数向量hi,最后组合成 f g 对应的多项式系数.为便于理解,以 1KNTT 为例.预处理即将 f=f0+f1x+f2x2+fn1xn1,其中 fi Z,i 0,1,n1,调整为 f=f0+f2x2+fn2xn2+(f1+f3x2+fn1xn2)x,记f0(f0,f2,fn2),f1(f1,f3,fn1).1KNTT 的具体流程在算法1中给出.对长度为 8 的多项式,1KNTT 的 NTT 结构如图1所示,其中 fi.j表示第 i 个多项式的第 j 个系数.算法 1 1KNTT 算法Input:Coefficient vectors of f,g RqOutput:Coefficient vector of h=f g Rq1(Preprocessing)f(x)=f0(x2)+f1(x2)x,g(x)=g0(x2)+g1(x2)x,wherefi(z),gj(z)(i,j 0,1)are of degree bounded by n/2.2(Multiplication)Computehi(z)Zqz/(zn/2+1)as the follows:h0(z)=f0(z)g0(z)+z f1(z)g1(z)=NTT1(f0 g0+z f1 g1),h1(z)=f0(z)g1(z)+f1(z)g0(z)=(f0(z)+f1(z)(g0(z)+g1(z)f0(z)g0(z)f1(z)g1(z)=NTT1(f0+f1)(g0+g1)f0 g0f1 g1)where z can be pre-computed.3(Combination)Compute h Rqas follows:h(x)=h0(x2)+h1(x2)x图 1 长度为 8 的 1KNTT 的 NTTFigure 1 NTT in 1KNTT of length 8由以上描述可知,1KNTT 包含 4 个 n/2 长的 NTT,2 个 n/2 长的 NTT1和 4 个 n/2 长的对应项点乘,共需模乘数为32nlogn+32n.我们分别编程实现了基于 1KNTT、2KNTT、3KNTT 的 Rq(n=256,q=3329)上的乘法运算,其计算复杂度区别不大,因此,本文中采用 1KNTT,后续都简称为 KNTT.856Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.20232.3KYBER 类 CPA 安全加密方案KYBER.CPA 是 NIST 于 2022 年 7 月公布的首批后量子密码标准算法中的 CRYSTALS KYBER的核心模块,其安全性和实现效率决定了 CRYSTALSKYBER.KEM 的安全性和实现效率.基于 KY-BER.CPA 算法,本节介绍 KYBER 类 CPA 安全加密方案,简记为 KYBER 类加密方案,并指出可以通过修改哪些因素得到一系列方案实例.在 KYBER 类加密方案中,Rq=Zqx/(xn+1),方案的密钥生成算法、加密算法和解密算法分别如算法2,3和4所示.算法 2 密钥生成算法 KeyGenInput:Seeds,0,1nOutput:pk,sk1A Rqkl:=SamA()2(s,e)l1 k1:=SamD()3b:=As+e4return(pk:=(b,),sk:=s)算法 3 加密算法 EncInput:Seed r,pk,m Rqand the coeffecients of m belong to 0,1Output:c1r 0,1n2A Rqkl:=SamA()3(r,e1,e2)1k 2l 2:=SamD(r)4u:=Compress(ATr+e1,du)5v:=Compress(bTr+e2+q2 m,dv)6return c:=(u,v)算法 4 解密算法 DecInput:sk,u,vOutput:m1u:=Decompress(u,du)2v:=Decompress(v,dv)3return m:=Compress(v sTu,1)针对上述 KYBER 类格公钥加密方案,可以通过修改以下模块得到一系列方案实例:(1)根据解密错误率和方案安全性,修改方案参数,包括模数 q,Rq中的参数 n,公钥矩阵规模 k,以及采样分布、压缩参数 du和 dv;(2)伪随机序列的生成算法;(3)均匀分布采样算法 SamA 和 分布采样算法 SamD;(4)多项式环 Rq的乘法运算.可以把 KYBER-512、KYBER-768 和 KYBER-1024 看做三个方案实例.本文研究的是针对 KYBER 类加密方案的快速实现技术,主要通过 KNTT 技术实现 Rq的乘法运算,并且为了最大限度提升方案的实现效率,优化数据存储方式、数据打包方式以及优化 KNTT 中的核心 NTT 的软件实现技术,从而提升了 KYBER 类加密方案的实现效率.3基于 KNTT 的格公钥加密方案快速实现技术由2.2节知,算法1中包括预处理和组合处理,这两步操作势必导致额外的时间开销.所以,在用KNTT 对格公钥加密方案进行改进时,为避免这些额外开销,本文改变 Rq上元素存储方式来“隐藏”预处理和组合.此外,NTT 正向和逆向变换每次只处理一个多项式,在使用 KNTT 替换其多项式乘法时,改进 NTT 的实现方式,使其每次可对两个多项式进行变换.本节给出通过调整 Rq上元素存储方式,以及王伯宇 等:基于理想格的公钥加密方案快速实现技术研究857基于改进 KNTT 实现方式的格公钥加密方案的快速实现技术.整体思路如图2所示.图 2 基于 KNTT 的格公钥加密方案快速实现整体思路Figure 2 Fast implementation of lattice public key encryption scheme based on KNTT3.1对数据存储方式的改进在基于 NTT 实现 Rq上乘法的格公钥加密方案中,Rq上的元素存储在包含一个 n 元数组的结构体中.为了适用 KNTT 技术,Rq上的元素存储在包含两个 n/2 元数组的结构体中,这样在按照算法1执行KNTT 时,只需做第 2 步“乘法”即可.为了节省时间和便于操作,在采样时,即按上述两个 n/2 元数组存储采样的结果,在明文编码和密文打(解)包时也按两个 n/2 元数组存储结果.3.1.1对 Rq上元素存储方式的改进在 KYBER 类加密方案中,一般是利用采样算法依次采样出多项式的 n 个系数,并依次存储在以一个 n 元数组为成员的结构体中.而在基于 KNTT 实现 Rq上乘法的格公钥加密方案中,我们使用包含两个成员的结构体,将前 n/2 个元素存储在结构体的第一个成员中,后 n/2 个元素存储在结构体的第二个成员中.采用该方法,即将数据的预处理隐藏在了存储采样结果的过程中,两个 n/2 元数组即可直接参与KNTT 的“乘法”.这样看似与 KNTT 的隔一个抽取一个的预处理方式不同,但这并不影响整个方案的加解密正确性,关于这点,3.3节将详细讨论.本节给出的 Rq上元素存储方式与 KYBER 算法(包括-512、-768、-1024)中的数据存储方式不同,具体如图3所示.图 3 Rq上元素存储方式的改进Figure 3 Improvement to storage of elements in Rq3.1.2对密文打(解)包结果存储方式的改进由于把 Rq上的元素存储在了两个成员的结构体中,在对密文进行打包时,打包完第一个成员的第一个分组后,打包第二个成员的第一个分组,依次进行下去.在解包时按打包方法的逆方向进行,即解包出的分组交替赋给密文结构体的两个成员.以 KYBER 算法为例,KYBYE 算法中模数 q=3329,长度为 12比特,打包的过程即将每两个 12 比特的密文(看作一个分组)打包成 3 个字节,反之即是解包过程.打(解)包结果存储方式改进如图4所示.3.2对 KNTT 中 NTT 的改进在使用 KNTT 技术时,每进行一次多项式的乘法,要做 4 次 NTT 和 2 次 NTT1,这就增加了 C实现时 for 循环的使用次数.for 循环本身的结构以及相同单位根幂次的重复调用增加了额外的赋值操作.858Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023图 4 打(解)包结果存储方式改进Figure 4 Improvement to storage of(un)packing为了充分利用 NTT 算法的迭代结构,减少重复的赋值操作,将它们由输入一个多项式改为输入两个多项式.改进后的 NTT 和 NTT1如算法5和算法6所示.算法 5 改进的 NTTInput:f0,f1 Zqx/(xn/2+1),wheref=f0+f1 x,f RqOutput:f0,f11k 12for l n/4;l 0;l l/2 do3for s 0;s n/2;s j+l do4for j s;j s+l;j j+1 do5t kf0j+l6f0j+l f0j t7f0j f0j+t8t kf1j+l9f1j+l f1j t10f1j f1j+t11end12k k+113end14end算法 6 改进的 NTT1Input:f0,f1 Zqx/(xn/2+1)Output:f0,f1,where f=f0+f1 x,f Rq1k 02for l 1;l n/2;l 2l do3for s 0;s n/2;s j+l do4for j s;j s+l;j j+1 do5t f0j6f0j t+f0j+l7f0j+l t f0j+l8f0j+l kf0j+l9t f1j10f1j t+f1j+l11f1j+l t f1j+l12f1j+l kf1j+l13end14k k+115end16end17for j 0;j n;j j+1 do18f0j f0j/n19f1j f1j/n20end对于算法1中 z(即 NTT(z)的预计算,以 n=256 为例,KNTT 要用到的 z 实际是(1,3,王伯宇 等:基于理想格的公钥加密方案快速实现技术研究859253,255)按位置序号比特翻转后的结果.即若将(1,3,253,255)表示为:(1,3,253,255)(z0,z1,z127),KNTT 要用到的 z 实际上是:(zbrv(0),zbrv(1),zbrv(127)=(z0,z64,z32,z96,z63,z127)(1,129,65,193,127,255)=(1,1,65,65,127,127),而 1,65,127正是计算 NTT 前预先建立的 幂次表的后 64 个,故不需要为 z 单独建表,只需交替使用 幂次表的后 64 个的正负值即可.这样不仅节省了冗余操作,使得 for 循环的个数和层数、单位根的调用次数以及模乘的个数与 KY-BER 完全相同,而且更利于硬件实现.3.3改进后的正确性首先分析改进后 KNTT 的计算结果.为便于描述,这里用 fi.j表示参与多项式乘的一个多项式系数向量第 i 个结构体成员的第 j 项.由采样得来的两个多项式分别为f (f0.(n/21),f0.(n/22),f0.0),(f1.(n/21),f1.(n/22),f1.0),g (g0.(n/21),g0.(n/22),g0.0),(g1.(n/21),g1.(n/22),g1.0),它们对应的预处理前的多项式分别为f(f0.(n/21),f1.(n/21),f0.(n/22),f1.(n/22),f0.0,f1.0),g(g0.(n/21),g1.(n/21),g0.(n/22),g1.(n/22),g0.0,g1.0),那么,本文 KNTT 计算结果实际为 h=f g系数组合前的结果,即h(h0.(n/21),h0.(n/22),h0.0),(h1.(n/21),h1.(n/22),h1.0).以对应 KYBER-512 的算法为例,KNTT-based KYBER 的公钥矩阵 A,A A00,A01A10,A11,其中Aij(aij0,aij1,aijn1),i,j 0,1,实际对应的是AA00,A01A10,A11,而Aij(aij0,aij1,aijn2),(aij1,aij3,aijn1),其他如公钥向量 b,私钥 s,错误 e,e1,e2,随机因子 r 等均可类似表示.这里需要强调的是,KNTT-based KYBER 和 KYBER.CPAPKE 算法由于采样得到的数据存储方式不同,所以相同的密钥种子生成不同的公私钥对,因此,不能把这两个算法看成是相等的,应该看成同属于 KYBER 类算法.在 KNTT-based KYBER,为了提高实现效率,参与运算的 Rq中的元素都采用两成员结构体来存储,这样节省了 KNTT 算法中预处理和组合的时间损耗,并不影响解密正确性.并且,在相同的参数设置下,使用 KNTT 加速前后的格公钥加密方案的安全强度保持一致.3.4改进后效率提升分析如2.1节所述,KYBER 使用 NTT 的方式,使得每次 n 长多项式乘法需要32nlogn+2n 次模乘;而使用 KNTT,每次 n 长多项式乘法需要32nlogn+32n 次模乘,比使用 NTT 的方法少做 n/2 次模乘.以860Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023对应 KYBER-512.CPAPKE(以下简称 K5 方案)的 KNTT-based KYBER(以下简称 N5 方案)为例,分析每次密钥生成和加解密节省多少次模乘.对应 KYBER-512 的方案,公钥矩阵 A Rq22,公钥向量 b Rq2,私钥 s Rq2,错误 e,e1 Rq2,随机向量 r Rq2.由于3.2节的改进,N5 方案和 K5 方案的计算量差异完全来源于“对应项点乘”部分.K5 方案的“对应项点乘”是 128 个模 2 次多项式的乘法,由环上多项式乘法定义知,每个需要 5 次模乘.故 K5 方案中两个 256 长多项式的“对应项点乘”需要 128 5 次模乘.N5 方案的“对应项点乘”如算法1的步骤 2 所示,共需要 128 4 次模乘.可见,每次两个 256 长多项式相乘,N5 方案比 K5 方案节省 128 次模乘.对于密钥生成算法,涉及“对应项点乘”的只有 A 和 s 的相乘,故 N5 方案比 K5 方案节省 128 4次模乘;对于加密算法,有 A 和 r,以及 b 和 r 的相乘,故 N5 方案比 K5 方案节省 128 6 次模乘;对于解密算法,有 s 和 u 的相乘,故 N5 方案比 K5 方案节省 128 2 次模乘.由于3.1节的改进,我们省去了 KNTT 的预处理和组合过程.如果不省去预处理和组合,每次两个256 长多项式相乘,要进行额外的 256 3 次赋值,经过实验验证,需要多花费 340 个时钟周期.于是,依然以 N5 方案为例,在密钥生成算法中,要对 s 和 e 进行预处理,会额外增加 256 4 次赋值,大约 450 个时钟周期;在加密算法中,要对 r 进行预处理,对 A 乘 r 的结果和 b 乘 r 的结果进行组合,额外增加 256 5次赋值,大约 560 个时钟周期;在解密算法中,要对 s 乘 u 的结果进行组合,额外增加 256 次赋值,大约110 个时钟周期.可见相较于平凡地使用 KNTT,3.1节的改进节省了大量的赋值操作.4实验结果为验证基于 KNTT 快速实现技术的提速效果,将该实现技术应用于 KYBER 类算法,进行效率对比.实验环境:使用搭载七代 Intel Core i5 处理器的笔记本电脑,主频 2.5 GHz,在内核为 Linux 4.15.0的 Ubuntu 18.04 操作系统下使用 gcc 7.5.0,-O3 优化级别进行试验.实验方法:选取不同的公钥矩阵参数进行实验,分别对 KYBER.CPAPKE 的代码1和 KNTT-basedKYBER 的代码进行测试.对每套参数做 10 轮实验,每轮做 216次密钥生成、加密和解密,求出 10 轮的每次相应操作消耗的时钟周期的平均值.参数选取:将算法安全级别参数 k 依次取 2,3,4 进行试验,分别得到对应于 KYBER-512,KYBER-768 和 KYBER-1024 安全级别的实验结果,如表1所示,其中“比率”指 KNTT 改进后时钟周期与 KY-BER.CPAPKE 的时钟周期的比率.分析实验结果可知,KNTT-based KYBER 的密钥生成的效率提升 5%8%,加密的效率提升 7%10%,解密的效率提升 9%10%.表 1 实验结果Table 1Experimental results版本对比项Key generationEncryptionDecryptionKYBER.CPAPKEKNTT-basedKYBERKYBER.CPAPKEKNTT-basedKYBERKYBER.CPAPKEKNTT-basedKYBER512CPU cycle98629937861126601054253977636023Ratio10.95110.93610.906768CPU cycle1707221566761873831699915192247763Ratio10.91810.90710.9201024CPU cycle2684572471742757422578536496459133Ratio10.92110.93510.9101https:/csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Kyber-Round3.zip王伯宇 等:基于理想格的公钥加密方案快速实现技术研究8615结论本文通过改进格公钥加密方案中 Rq上元素和密文打(解)包结果存储方式,采用不需要预处理和组合的 KNTT 技术,以及 NTT 的快速实现技术,达到提高格公钥加密方案实现效率的目的.本文提出的快速实现技术不产生额外的存储消耗,对算法安全性亦没有影响,并且有利于快速实现,实验验证了快速实现技术的有效性.下一步将研究格签名方案的快速实现技术.参考文献1 REGEV O.On lattices,learning with errors,random linear codes,and cryptographyJ.Journal of the ACM(JACM),2009,56(6):140.DOI:10.1145/1568318.15683242 ALKIM E,et al.FrodoKEM learning with errors key encapsulation algorithm specifications and supportingdocumentationR.NIST,2021.3 LANGLOIS A,STEHL D.Worst-case to average-case reductions for module latticesJ.Designs,Codes andCryptography,2015,75(3):565599.DOI:10.1007/s10623-014-9938-44 AVANZI R,BOS J,DUCAS L,et al.CRYSTALS-Kyber algorithm specifications and supporting documenta-tionR.NIST,2021.5 BANERJEE A,PEIKERT C,ROSEN A.Pseudorandom functions and latticesC.In:Advances in CryptologyEUROCRYPT 2012.Springer Berlin Heidelberg,2012:719737.DOI:10.1007/978-3-642-29011-4_42.6 JAN-PIETER DANVERS,et al.SABER:Mod-LWR based KEMR.NIST,2019.7 LYUBASHEVSKY V,PEIKERT C,REGEV O.On ideal lattices and learning with errors over ringsC.In:Advances in CryptologyEUROCRYPT 2010.Springer Berlin Heidelberg,2010:123.DOI:10.1007/978-3-642-13190-5_1.8 ALKIM E,et al.NewHope algorithm