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

来源：计算机工程杂志2024年第2期北京时间：

作者：雷斗威, 何德彪, 罗敏, 彭聪

单位：武汉大学国家网络安全学院, 湖北 武汉 430072

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

关键词：后量子密码,格密码,公钥加密,512位高级向量扩展指令集,并行计算

基金资助：国家重点研发计划(2022YFB4400700)