陈朝晖 马原 荆继武

1. 中国科学院大学计算机科学与技术学院, 北京 100049; 2. 中国科学院信息工程研究所信息安全国家重点实验室,北京 100093; 3. 中国科学院大学网络空间安全学院, 北京 100049; 4. 北京大学软件与微电子学院, 北京 102600;† 通信作者, E-mail: mayuan@iie.ac.cn

量子计算技术给现有 RSA 和椭圆曲线公钥密码算法的安全性带来巨大的挑战。Shor[1]提出一种可快速破解大整数分解和离散对数问题的量子算法, Gidney 等[2]发现只需要 2000 万个量子比特即可在 8 小时内破解的 RSA2048 算法。为征集合适的替代性公钥密码算法标准, 美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)自 2016 年起开始征集具有后量子特性的公钥加密、密钥交换和数字签名方案。其中, 基于格上困难问题的方案具有计算速度较快[3]、密钥和密文较小[4]等优势, 受到广泛关注, 成为热门的后量子密码候选方案[5]。

Lyubashevsky 等[6]提出的环上错误学习(ring learning with errors, RLWE)问题是许多格密码算法的理论基础。RLWE 密码算法中的关键运算是多项式乘法运算, 可以采用基于蝶形运算的数论变换(number theoretic transform, NTT)快速实现[7-8]。NTT要求密码算法使用特定的模数, 以 NewHope 算法[9]为代表的密钥交换算法和以 BLISS 算法[10]为代表的数字签名算法均选择适用于 NTT 的参数, 以便提高运算速度。NTT 多项式乘法硬件的实现受到学术界的广泛关注, 其设计难点在于, 一方面 NTT 控制逻辑包含多层循环嵌套的原位运算结构, 存储器中的多项式系数存取调度复杂且带宽要求较高; 另一方面, 蝶形运算在 NTT 计算过程中执行次数多, 例如 512 维多项式每次 NTT 需要执行 2304 次……