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

摘要：

在基于理想格和模格的公钥加密方案中,多项式环上的乘法运算是影响方案实现效率的重要模块,而该模块通常可通过数论变换(number theoretic transform,NTT)来快速实现.本文采用结合Karatsuba 算法的带预处理的 NTT(preprocess-then-NTT with Karatsuba,KNTT),提升格公钥加密方案的实现效率.在使用KNTT前,通过改进采样和密文打(解)包结果的存储方式来调整多项式环元素的数据结构,使之直接适用KNTT,从而省去KNTT算法中的预处理和组合环节.改进了 KNTT中的NTT变换的实现方式,进一步提高格公钥加密方案的实现效率.KYBER是NIST在第三轮评选中决定标准化的格公钥密码算法,本文将上述改进技术应用于KYBER类加密方案,得到了 KNTT-based KYBER算法,与KYBER.CPAPKE相比,密钥生成实现效率提高了 5％-8％,加密实现效率提高了 7％-10％,解密实现效率提高了 9％-10％.

关键词：格公钥密码、容错学习问题、KYBER类加密方案、数论变换、结合Karatsuba的带预处理的数论变换

所属期刊栏目：10

分类号：TP309.7(计算技术、计算机技术)

在线出版日期：2023-09-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：852-861