环上舍入学习和模上舍入学习的通用实现算法与参数选取方法
2022-10-29 18:07:52   来源：    点击：

摘要 格密码领域中的环上舍入学习(RLWR)和模上舍入学习(MLWR)问题是构造后量子密码原语的一类重要数学工具,已广泛应用于伪随机函数、陷门函数等基础密码构造.RLWR 和MLWR实现通常包括三项基础操作:多项式乘法、模约化和舍入计算,三项基础操作均有多种适用于不同参数的实现方案,相同运行平台.相同安全等级下RLWR和MLWR软件实现效率受参数影响显著.然而,现有RLWR和MLWR方案实现及效率优化工作大多仅针对某些特定参数,无法处理任意参数;此外,现有RLWR和MLWR方案参数选取大多只考虑了部分基础操作的效率,缺乏系统的快速实现参数选取方法.为解决上述问题,本文提出了通用高效的RLWR实现算法和ML-WR实现算法,以及RLWR和 MLWR快速实现参数选取方法.本文首先给出了NTT和NTT负折叠卷积的使用条件与方案参数以及CPU字长之间的量化关系,扩展了可快速实现的基于多项式环的密码方案参数空间;其次，提出了一种适用于RLWR和MLWR实现的新舍入算法,与通用的传统舍入实现相比,新舍入算法的效率在64位Intel i7平台下提高了11%左右;最后,提出了典用RLWR实现算法和MLWR实现算法,通用实现算法根据方案参数和CPU字长灵活选取高效的基础操作实现方案,将其应用于Saber方案实现,在64位Intel i7平台下未使用编译优化指令的Saber密钥封装效率提升了52%左右,此外,对比分析了不同参数下RLWR和MLWR的效率,提出了RLWR和MLWR快速实现参数选取方法,为RL.WR和MLWR方案设计与实现中的参数选取提供了指导.