环上舍入学习和模上舍入学习的通用实现算法与参数选取方法  

The General Implementation Algorithms and the Parameters Selection Methods of Ring Learning with Rounding and Module Learning with Rounding

作　　者：姜子铭 周永彬[1,2,3] 张锐 JIANG Zi-Ming;ZHOU Yong-Bin;ZHANG Rui(Institute of Information Engineering(IIE),Chinese Academy of Sciences(CAS),Beijing 100093;School of Cyber Security,University of Chinese Academy of Sciences(UCAS),Beijing 100049;School of Cyber Security,Nanjing University of Science and Technology(NJUST),Nanjing 210094)

机构地区：[1]中国科学院信息工程研究所,北京100093 [2]中国科学院大学网络空间安全学院,北京100049 [3]南京理工大学网络空间安全学院,南京210094

出　　处：《计算机学报》2022年第6期1326-1347,共22页Chinese Journal of Computers

基　　金：国家自然科学基金(61632020,U1936209,62002353);北京市自然科学基金(4192067)资助.

摘　　要：格密码领域中的环上舍入学习(RLWR)和模上舍入学习(MLWR)问题是构造后量子密码原语的一类重要数学工具,已广泛应用于伪随机函数、陷门函数等基础密码构造.RLWR和MLWR实现通常包括三项基础操作:多项式乘法、模约化和舍入计算,三项基础操作均有多种适用于不同参数的实现方案,相同运行平台、相同安全等级下RLWR和MLWR软件实现效率受参数影响显著.然而,现有RLWR和MLWR方案实现及效率优化工作大多仅针对某些特定参数,无法处理任意参数;此外,现有RLWR和MLWR方案参数选取大多只考虑了部分基础操作的效率,缺乏系统的快速实现参数选取方法.为解决上述问题,本文提出了通用高效的RLWR实现算法和MLWR实现算法,以及RLWR和MLWR快速实现参数选取方法.本文首先给出了NTT和NTT负折叠卷积的使用条件与方案参数以及CPU字长之间的量化关系,扩展了可快速实现的基于多项式环的密码方案参数空间;其次,提出了一种适用于RLWR和MLWR实现的新舍入算法,与通用的传统舍入实现相比,新舍入算法的效率在64位Intel i7平台下提高了11%左右;最后,提出了通用RLWR实现算法和MLWR实现算法,通用实现算法根据方案参数和CPU字长灵活选取高效的基础操作实现方案,将其应用于Saber方案实现,在64位Intel i7平台下未使用编译优化指令的Saber密钥封装效率提升了52%左右,此外,对比分析了不同参数下RLWR和MLWR的效率,提出了RLWR和MLWR快速实现参数选取方法,为RLWR和MLWR方案设计与实现中的参数选取提供了指导.The learning with rounding(LWR)problem in lattice cryptography is one of the fundamental tools for constructing post-quantum cryptographic primitives.As a deterministic variant of learning with errors(LWE),LWR replaces random errors in LWE with deterministic rounding.The removal of random error sampling makes LWR-based cryptosystems more efficient than LWE.Since it was proposed,LWR problem has been extensively applied to the construction of basic cryptosystems,such as low-depth pseudorandom functions,lossy trapdoor functions and public-key encryption schemes.In order to reduce the computational complexity and bandwidth,the ring and module version of LWR,that is,ring LWR(RLWR)and module LWR(MLWR),are mostly used in practice.To make the post-quantum cryptosystems more practical,it is of great significance to improve the efficiency of RLWR and MLWR.The ring in lattice usually takes the polynomial ring,so RLWR/MLWR includes three basic operations:polynomial multiplication,modular reduction,and rounding.For each of the three operations,there are a variety of implementation methods with different efficiencies which apply to different parameters.The efficiency of RLWR/MLWR with different parameters may vary greatly at the same security level.However,most of the existing implementations of RLWR and MLWR are only applicable to some certain schemes with specific set of parameters.In addition,most of the existing RLWR and MLWR schemes have not given consideration to the implementation efficiency of all basic operations.There is a lack of RLWR/MLWR parameter selection method for the purpose of achieving high efficiency.In order to solve the above problems,we propose the general and efficient implementation algorithms of RLWR and MLWR,as well as the parameters selection methods of RLWR and MLWR to achieve high efficiency.In this work,we first discuss the conditions of existing implementation methods of the three basic operations on CPU platform and focus on the special parameters commonly used in lattice-based cryptosystems.I

关 键 词：格密码 舍入学习 多项式乘法 数论变换 舍入计算 

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