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

作     者：姜子铭 周永彬 张锐 JIANG Zi-Ming;ZHOU Yong-Bin;ZHANG Rui

作者机构：中国科学院信息工程研究所北京100093 中国科学院大学网络空间安全学院北京100049 南京理工大学网络空间安全学院南京210094 

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

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2022年第45卷第6期

页      码：1326-1347页

摘      要：格密码领域中的环上舍入学习(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方案设计与实现中的参数选取提供了指导.

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

学科分类：08[工学] 0839[0839] 0703[理学-化学类] 0714[0714] 0701[理学-数学类] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.11897/SP.J.1016.2022.01326

馆 藏 号：203112159...