后量子密码发展综述

摘　要：公钥密码学是保障现代通信安全与数据安全的重要基础技术。介绍了当前量子计算发展对公钥密码学造成的威胁，以及密码标准化组织和密码学研究的应对措施，依据所使用的基础数学困难问题分类阐述基于格、编码、多变量、哈希函数、曲线同源的后量子密码及其优劣势等特点。以当前后量子密码标准进展为主线，从算法安全性分析、后量子迁移的技术路线、与量子通信技术结合、新的数学困难问题探索等方面提出后量子密码学的发展方向建议。

内容目录：

1　量子时代带来的挑战

2　后量子密码发展现状及技术路线

2.1　抵御量子威胁的战略意义

2.2　基于格的后量子密码算法

2.3　基于编码的后量子密码算法

2.4　基于多变量的后量子密码算法

2.5　基于哈希函数的后量子密码算法

2.6　基于曲线同源的后量子密码算法

2.7　后量子密码技术路线对比

3　后量子密码的发展趋势

3.1　后量子密码算法的安全性评估

3.2　后量子密码迁移应用验证探索

3.3　后量子密码与基于物理学的量子通信技术的融合应用探索

3.4　量子环境下新的数学问题探索

4　结　语

密码技术是信息技术领域的重要分支，随着科学技术的发展，密码技术不断进步，从机械密码到电子密码，再到现代的数字密码，每一步都推动了人类文明的快速前行。到了互联网时代，万物互联使得世界发生了颠覆性变化，虚拟空间的互认互信成为核心要素。而现代互联网的互联互信极大地依赖于公钥密码体系，不仅可以保证消息的机密性，还可以验证消息的来源，提供了数据加密、身份验证和消息完整性检查等功能，确保了互联网通信的安全和可靠。随着量子计算技术及量子计算机的迅猛发展 ，当代被广泛使用的密码系统受到量子计算的严重威胁。公钥密码学也开始技术革新，迎接量子计算时代的挑战，并且在密码标准化方面已取得阶段性进展。因此，有必要全面掌握当前已知抵抗量子计算的公钥密码，总结后量子密码技术路线及其特点 。本文进一步新增最新的针对密码算法的量子计算攻击进展，分析各种类别后量子密码的优劣势，提出后量子密码研究及后量子迁移的建议，为后量子密码的深入发展提供支撑。

1

量子时代带来的挑战

量子计算技术及量子计算机极大地威胁着经典密码的安全。一方面，量子计算破译经典密码具有显著优势。为保证信息的加密传输，基于数学上困难问题设计的 RSA、DSA、ECC等公钥密码算法已经维护了近 50 年的网络信息与通信安全。但是，随着第二次量子革命 中的量子计算机的快速发展，以及以 Shor 算法和 Grover 算法为代表的量子计算算法的高速迭代研究，给现有互联网基础设施带来巨大的信任危机。Shor 算法 能在多项式时间内求解给定大整数的大质因数，与经典整数分解算法相比，其能够指数级提升效率；Grover 算法是搜索非结构化数据库或无序列表的量子算法，应用于密码破解使得等效于同等攻击下密钥长度减半。Google 在2022 年发布的资料表明，其计划在 2030 年完成100 万量子比特的量子专用计算机的研制；2022 年 12 月，清华大学龙桂鲁教授团队提出基于经典的 Schnorr 算法及同时依靠量子近似优 化 算 法（Quantum Approximate OptimizationAlgorithm，QAOA）来优化 Schnorr 算法中最耗时的部分，实现了仅用 10 个超导量子比特就完成了 48 位因式分解，同时提出最低仅需要372 个物理量子比特的量子计算机即可能完成RSA-2048 的破解 。

另一方面，量子攻击策略具有时间优势，不一定只在量子计算机成熟后才发挥作用。攻击者先将能够获取的所有加密状态信息存储起来，等到实用的量子计算机建造后再实施密码破译，而量子计算的快速发展极大地缩短了时间周期。按照国家保密管理要求，重要的信息管理期限甚至在 10 年以上 。这意味着，如果2033 年前研发出了可用于破译现有密码体制的量子计算机，那么在互联网或者其他公共信息网络传输的信息都存在极大的泄密风险。量子计算技术发展直接倒逼密码技术的发展，换言之，目前快速发展的量子计算技术迫使密码技术必须尽快采取应对措施。

2

后量子密码发展现状及技术路线

2.1　抵御量子威胁的战略意义

传统公钥密码使用经典计算机在多项式时间内无法求解的公认数学困难问题作为安全基础。类似的，当代密码学探寻当前量子计算机无法有效求解的困难问题作为安全基础设计密码体制，这些体制被称为抗量子计算密码（QuantumResistant Cryptography，QRC）或者后量子密码（Post-Quantum Cryptography，PQC）。

美国将后量子密码作为应对量子计算最具优势的技术手段，提出了《量子计算网络安全准备法案》，制定了政府信息技术向后量子加密过渡的路线图 ，并由美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）自 2016 年开始启动全球征集遴选 PQC 标准算法的工作。2022 年 9 月，美国国家安全局（National Security Agency，NSA）发布了 CNSA 2.0时间表，计划于 2033 年完成后量子密码迁移 。

根据底层数学困难问题分类，后量子密码算法研究目前主要有 5 种技术路线，分别是基于格的密码、基于编码的密码、基于多变量的密码、基于哈希函数的签名以及基于曲线同源的密码。2022 年 7 月 NIST 公布的后量子密码标准化遴选进展中，基于格的密码和基于安全哈希函数的签名算法已入选为标准，基于编码和超奇异同源的密码算法入选第四轮筛选并开展进一步评估，而其中基于超奇异同源的密码算法 SIKE 被完全破解 。

2.2　基于格的后量子密码算法

格是实数域上线性空间中的离散子群，可表达成一组向量的整系数线性组合。给定一组线性独立的向量它们生成的格是集合其 中 n 被称为格的维数，被称为这个格的一组基。一个 n 维格具有很多格基，它的任意两组格基之间相差一个 n 阶幺模矩阵。计算格中的最短非零向量是重要的困难问题，是当代格密码的安全基石。Ajtai提出的短整数解（Short Integer Solution，SIS）问题和 Regev 提出的带错误学习（Learning with Errors，LWE）问题开启了实用的可证明安全格密码研究。当前实用且安全的加解密格体制 、数字签名 格密码体制基本基于上述两个问题设计。一方面，格密码具有上述困难问题作为理论规约的安全基础；另一方面，格密码的空间时间资源消耗适中。进一步的，基于格密码能够设计属性加密、同态加密 等高等密码学应用算法。因此，业界广泛认可格密码是最有前景的后量子密码技术分支。

2.3　基于编码的后量子密码算法

经过编码的信息在信道上传输，由于噪声产生错误，在接收端通过译码算法恢复。基于编码的密码，其理论依据来源于随机线性码的译码是困难问题 。1978 年，McEliece 使 用 Goppa码设计公钥加密方案 ，以 [n,k,t]-Goppa 码的生成矩阵 G 作为内核，在左侧和右侧分别施加可逆矩阵 S 和随机置换矩阵 P 来掩盖 G，方案的私钥包含矩阵 S，G，P，公钥包含矩阵 G'=SGP以及 Goppa 码的纠错能力 t。加密时将明文编码成向量 m，计算密文 c=mG'+e，其中 e 是重量不超过 t 的随机向量。解密时计算并施加译码操作。近年来，基于编码的密码考虑使用秩距离码、极化码等。

基于编码的密码具有自身优势，同时也面临着挑战。一方面，基于编码的密码相对于现有公钥密码算法表现出加密速度快的特点；另一方面，基于编码的加密算法的公钥尺寸很大，影响了算法的适用领域。另外，NIST 后量子标准化的情况表明，基于编码的加密算法发展较好，但是基于编码设计安全高效的实用签名体制仍然是挑战性高的研究工作。

2.4　基于多变量的后量子密码算法

基于多变量的密码的安全基础来源于求解高次多变量方程组是 NP 难题。构造有限域上高维空间映射 F，使得它的逆运算也是容易的；在左右两端引入两个线性（或仿射）映射 S，T 来掩盖 F。私钥包括映射 S，F，T，公钥是它们的复合映射 P=S○F○T，其表现如同随机映射。基于多变量的代表性密码算法包括 HFEv- 类型的 GeMSS 签 名 体 制 [32] 和 UOV 类 型 的 Rainbow签名算法 ，二者均已进入 NIST 后量子标准化遴选第三轮。但是，2020 年 Tao 等人 提出的极小秩距离攻击，极大地降低了 GeMSS 签名算法的安全性，紧接着 2022 年 Beullens 提出 Rainbow 签名算法的攻击算法，极大地提高了密钥恢复攻击效率。因此，GeMSS 与 Rainbow算 法 均 未 能 进 入 NIST 后 量 子 标 准 化 遴 选第四轮。

基于多变量的密码具有资源优势，但需要进一步研究其安全性。一方面，基于多变量的密码具有较高的运算速度和较小的签名尺寸；另一方面，类似于编码密码，基于多变量的密码算法的公钥尺寸也很大，算法实用性受到限制。另外，NIST 后量子标准化的情况表明 ，基于多变量设计安全高效的加密体制是挑战性高的研究工作。关于多变量密码的一个很好的综述见文献 [37]。

2.5　基于哈希函数的后量子密码算法

分组密码和哈希函数是研究深入且具有良好标准化对象的密码组件 。基于对称密码设计后量子密码算法具有较好的工具基础。

基于哈希函数的签名体制，利用 Lamport提出的一次性签名作为叶子节点，利用 Merkle树结构构造数字签名方案 。代表性算法包括XMSS 和 SPHINCS+，前者是有状态的签名，后者是无状态的签名，两个算法在后量子标准化中均取得重要进展 。

NIST 后量子标准化中出现基于分组密码和非交互零知识证明的签名体制 Picnic，该体制具有所使用的对称组件效率高，设计模块化通用性强，公钥尺寸小，签名尺寸大，签名速度快的特点。这一方案的安全性和优化版本值得进一步研究。

2.6　基于曲线同源的后量子密码算法

所谓同源（Isogenies），就是指两条椭圆曲线之间保持群结构同态的映射。一个同源的表达形式常如：给定两条定义在的椭圆曲线和记为映射分别是上的有理点）。2011 年，Jao 等人首 次 提 出 了 超 奇 异 同 源 Diffie-Hellman 问题（Supersingular Isogeny Diffie-Hellman，SIDH），并设计了基于超奇异同源的公钥密码系统 SIKE，该算法也被提交到 NIST 成为唯一的同源类候选算法。与其他 4 类候选算法最大的区别在于，基于 SIDH 的算法参数尺寸非常小，计算速度较慢。但是，2022 年至今，SIDH 及其加密算法 SIKE 遭到 Castryck 等人提出的密钥恢复攻击，最终被完全破译。需要指出的是，SIKE 的失败并不意味着基于同源的密码完全崩塌，同源问题本身并未被破解，以基于同源的签名 SQISign为代表的算法仍然引领这一方向的研究。

2.7　后量子密码技术路线对比

通过粗略对比，上述 5 类后量子密码的技术特点非定量对比如表 1 所示。

表 1　5 类后量子密码的技术特点非定量对比

3

后量子密码的发展趋势

通过对后量子密码研究现状的论述，结合当前量子技术与密码学的发展，针对后量子密码的技术需求和发展趋势提出一些观点。

3.1　后量子密码算法的安全性评估

如前文所述，后量子密码算法主要集中在寻找一类或多类在量子计算攻击下的 NP 数学困难问题，而目前仅是利用 Shor 算法和 Grover 算法本身或其优化算法作为攻击的源算法。随着量子计算的发展，存在产生新的量子算法的可能性，或将再次颠覆现有的后量子密码算法体系。因此，在后量子算法的选择、试点探索、应用部署等任一阶段，针对已知和未知攻击的安全性评估将一直是后量子密码研究的重要方向。

3.2　后量子密码迁移应用验证探索

NSA 已发布了后量子迁移时间表 ，使用已遴选出的基于格、哈希函数的签名的后量子算法作为基础开展后量子迁移，它们与现有经典密码算法相比均存在尺寸更大、资源消耗更多的情况。因此，有必要探索后量子密码迁移所需软件和硬件平台极限，提前研究能同时兼容经典密码与后量子密码的可自适应的密钥管理系统、密钥分发系统、终端硬件平台，实现向后量子迁移的平稳过渡。

3.3　后量子密码与基于物理学的量子通信技术

的融合应用探索基于物理学的量子密钥分发技术（Quantum Key Distribution，QKD）是目前量子通信技术研究和投入较多的一个方向 。以物理学、光学为理论基础的量子密码技术能够在使用一次一密的情况下实现信息论证明的绝对安全，能够抵抗量子计算的超高并行算力。而该技术方向中无论是具有远传输距离优势的离散变量量子密钥分发技术（Discrete Variable-QKD，DV-QKD）还是具有高速率优势的连续变量量子密钥分发技术（Continuous Variable-QKD，CV-QKD），均有中国团队占据国际领先技术优势。但是，目前 QKD 技术存在一些实用化技术难题亟须解决：一是小型化、低成本、高速率、远距离的系列技术需突破；二是由于与经典密码学的实现基础完全不同，导致无法直接与现有通信网融合 。因此，探索 QKD 技术与 PQC 技术互补，建立具备保护特定关键基础设施的对抗量子攻击的密码网络，有利于未来做好网络安全保护。

3.4　量子环境下新的数学问题探索

NIST 的 CRYSTALS-KYBER、FALCON、CRYSTALS-Dilithium 和 Sphincs+ 4 个 PQC 标 准化算法中，除了 Sphincs+ 为基于哈希函数的签名算法，其他均为基于格的密码算法。国内也投入了大量研究力量集中攻关基于格的密码算法 。后量子密码算法除了基于格、哈希函数、多变量、编码的技术路线，还有基于同源曲线的技术路线。因此，有必要拓展更多的后量子密码算法体制研究方向来积极应对未知的量子计算世界。回归本源，密码学是数学的延伸，探索密码学和数学的跨学科融合，利用现代数学的理论赋能密码学的拓展研究，探索新的数学困难问题，有利于研制具有自主技术特色的后量子密码体制。

4

结　语

本文简要描述了后量子密码发展现状及对其未来发展的个人思考。量子计算技术是未来发展相当不确定的前沿技术，而后量子密码技术作为防御者，理应下好先手棋。美国发布的后量子迁移计划表明，传统密码学优势大国已经开始未雨绸缪，提前布局。因此，应在抗量子密码及相关领域的科研计划中，持续探索未来技术发展的路线，积极落地后量子密码应用，保障国家的网络与信息安全。

引用格式：孙奥 , 何银 , 李海波 , 等 . 后量子密码发展综述 [J]. 信息安全与通信保密 ,2023(9):27-35.

作者简介 >>>

孙　奥，男，硕士，工程师，主要研究方向为通信及网络安全；

何　银，男，学士，工程师，主要研究方向为网络安全；

李海波，男，硕士，工程师，主要研究方向为保密通信；

张云蓓，女，学士，助理工程师，主要研究方向为网络安全。

选自《信息安全与通信保密》2023年第9期（为便于排版，已省去原文参考文献）

原文始发于微信公众号（信息安全与通信保密杂志社）：后量子密码发展综述