基于模格MLWR的密钥封装方案优化与高效实现

格密码因其在安全性、密文尺寸和计算效率等方面性能均衡,同时具有构造简单和通用性强等优点,被认为是最有前景的后量子密码技术路线之一.基于模格MLWR的Saber密钥封装方案是NIST后量子密码标准征集第三轮公布的七个决赛算法之一,对Saber方案的优化和高效实现有重要的现实意义.本文针对Saber通过大量测试提出一组新参数,所提出的新参数可以在安全强度、错误率和带宽方面取得更好的平衡.为了提升实现效率,我们将数论变换(NTT)和显式中国剩余定理(CRT)应用于其中基础且耗时的多项式乘法,并根据新参数(向量维数、多项式维度、模数和中心二项分布参数)的具体取值,最终选取两个NTT友好素数:q1=7681和q2=3329.接下来,本文基于256位高级向量扩展(AVX2)对Saber新参数的关键模块进行了较为系统的实现和优化,包括:约减模块、多项式运算模块、中心二项分布模块、私钥序列化模块、并行压缩模块以及并行编码/解码模块等.性能测试结果表明,本文在多项式乘法模块相比于目前存在的Saber实现算法性能平均提升约37%.相比于Saber Round3的AVX2实现,我们密钥生成算法性能提升约21%,密钥封装算法提升约23%,密钥解封装算法提升约23%.本文工作对后量子密码算法的优化和实际应用具有现实意义.