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

Research on Fast Implementation of Ideal Lattice-Based Public-Key Encryption Scheme

作　　者：王伯宇 高海英[1] WANG Bo-Yu;GAO Hai-Ying(Information Engineering University,Zhengzhou 450001,China)

机构地区：[1]信息工程大学,郑州450001

出　　处：《密码学报》2023年第4期852-861,共10页Journal of Cryptologic Research

基　　金：国家自然科学基金(61902428,61702548)。

摘　　要：在基于理想格和模格的公钥加密方案中,多项式环上的乘法运算是影响方案实现效率的重要模块,而该模块通常可通过数论变换(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%.In the implementation of public-key encryption schemes based on ideal lattice and module lattice,the multiplication on polynomial ring is an important module that affects the implementation efficiency of the scheme.The number theoretic transform(NTT)is often utilized to speed up the implementation of the operation.In this paper,a technique called preprocess-then-NTT with Karatsuba(KNTT)algorithm is used to improve the implementation efficiency of the public-key encryption scheme.Before KNTT is used,the data structure of polynomial ring elements is adjusted to be suitable for KNTT by improving the storage mode of sampling and cipher-text packing(unpacking)results,so as to remove the pre-processing and combination of KNTT algorithm.The implementation of NTT transform in KNTT is optimized to further improve the implementation efficiency of lattice-based public-key encryption scheme.KYBER was determined to be standardized in the third round of NIST evaluation.This paper applies the above improvements to the KYBER-like encryption schemes to get KNTT-based KYBER.Compared with KYBER.CPAPKE,KNTT-based KYBER is 5%–8%more efficient in key generation,7%–10%in encryption,and 9%–10%in decryption.

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

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