基于AVX512的格密码高速并行实现

量子计算的迅速发展可能对当前广泛使用的公钥密码算法造成严重威胁。格密码因优秀的抗量子安全性和高效的计算效率在后量子密码中占据重要地位。美国国家标准技术研究院于2022年5月公布4个后量子密码标准,其中3个是格密码算法,Kyber算法便是其中之一。随着后量子密码标准的确定,Kyber算法高效实现的需求日益增加。基于512位高级向量扩展(AVX512),对Kyber算法进行优化与高速并行实现。使用惰性模约减、优化的蒙哥马利模约减及优化的快速数论变化等技术,充分利用计算机的存储空间,减少大量不必要的模约减操作,提高多项式计算的效率与并行性。采用冗余比特技术,增强多项式抽样过程中比特的并行处理能力。通过AVX512的512 bit位宽和8路并行实现哈希运算,并对其产生的伪随机比特串进行合理调度,充分发挥并行性能。基于AVX512指令集高速并行实现Kyber上的多项式计算和抽样,并进一步实现整个Kyber公钥加密方案。性能测试结果表明,与C语言实现相比,基于AVX512实现的密钥生成和加密算法获得了10~16倍的加速,解密算法获得了约56倍的加速。

AKCN-MLWE算法AVX2高效实现

随着量子计算机的快速发展,经典密码系统面临巨大的威胁.Shor算法可以在量子计算机上多项式时间内分解大整数和求解离散对数,而这两类问题分别对应经典公钥密码系统中的RSA和椭圆曲线密码(ECC)所依赖的困难问题,因此可以抵御量子计算攻击的后量子密码近年来受到广泛的研究.格密码是后量子密码中最为高效且拓展性强的一类密码算法,在未来会逐步替代传统公钥密码算法(RSA、ECC等).256位高级向量扩展(AVX2)指令集是英特尔64位处理器中普遍支持的一类单指令多数据(SIMD)指令集,可用于并行计算.但是,由于格密码结构复杂,在支持AVX2指令集的英特尔64位处理器上难以对格密码方案进行高适配的深度优化.AKCN-MLWE算法是我国自主设计的基于模格上容错学习(MLWE)问题的格密码密钥封装(KEM)方案,是中国密码学会举办的公钥密码算法竞赛第二轮的获奖算法.本文基于256位高级向量扩展(AVX2)指令集设计了针对AKCN-MLWE算法的高效实现方案,包括以下几个关键优化点:针对多项式乘法,本文结合最优的数论变换(NTT)算法,将NTT的最后一层转换为线性多项式并使用Karatsuba算法进行加速计算,大幅提升计算效率的同时减少了预计算表的空间占用;针对取模运算,本文结合了Barrett约减算法和蒙哥马利约减算法的优势,同时采用延迟约减技术降低取模次数;本文针对所有多项式运算均实现了高度并行化,设计了针对多项式压缩与解压缩的并行算法,进一步提升了实现效率.本文设计的AKCN-MLWE算法AVX2高效实现方案在八核Intel Core i9-9880H处理器上仅需不到0.04 ms即可完成一次完整的KEM(包括密钥生成、密钥封装和密钥解封装),相比于参考实现提升8.84倍,其中密钥生成提升7.07倍,密钥封装提升7.90倍,密钥解封装算法提升11.78倍.本文提出的AKCN-MLWE算法AVX2实现方案在相近经典安全强度下性能优于美国国家标准技术研究所(NIST)后量子密码标准化进程第二轮中众多格密码方案(Kyber、NewHope和Saber等).同时,本文设计的部分优化方案可用于提升Kyber、NewHope等格密码方案的性能.