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

Optimization and Efficient Implementation of MLWR-based Key Encapsulation Mechanism

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

Lattice-based cryptography is considered to be one of the most promising post-quantum cryptography(PQC)routes due to its balanced performance in security,bandwidth complexity and computational efficiency,as well as simple structure and strong versatility.Saber is a key encapsulation mechanism based on module learning with rounding(MLWR),which is one of the seven finalists in the 3rd round of NIST post-quantum cryptographic standardization process.The optimization of Saber has important practical significance.This paper proposes new parameter sets for Saber after a large number of tests.The proposed new parameters can achieve a better balance in terms of security,error rate and bandwidth.In order to improve efficiency,the number theoretic transform(NTT)and the Chinese remainder theorem(CRT)are used to compute polynomial multiplication which is the basic and most time-consuming operation.According to the specific values of new parameters for Saber,including vector dimension,polynomial dimension,modulus and central binomial distribution parameters,two NTT-friendly primes are selected,they are q1=7681 and q2=3329.Then,based on256-bit advanced vector extension(AVX2),the key modules for Saber are optimized and implemented with new parameters,including the reduce module,polynomial multiplication module,central binomial distribution module,private key serialization module,parallel compression module and parallel encode/decode module.Performance results show that the proposed method is 37%faster than other existing implementations of polynomial multiplication.Compared with the AVX2 implementation of Saber Round3,the performance of our key generation,encapsulation and decapsulation algorithm are improved by about 21%,23%and 23%respectively.The proposed method has practical significance for the optimization and practical application of the post-quantum cryptographic algorithm.