后量子密码技术路线及标准化进程如何？

基于多变量的后量子密码算法是后量子密 码算法最早的类别之一，这类密码算法基于求解高次多变量方程组 这一 NP 难问题。

1.后量子密码技术路线

为了应对量子计算机对现有密码算法的威胁，研究人员和密码 学家已经着手开发新一代的密码算法，这些算法基于各种数学难 题，旨在抵御量子计算的攻击。根据底层数学问题分类，后量子密 码算法研究目前主要有 5 种技术路线，分别是基于格的密码、基于 编码的密码、基于多变量的密码、基于哈希函数的密码以及基于曲 线同源的密码。

基于格的密码：格（Lattice）俗称为“数的几何”（Geometry of numbers），是一种数与形相结合的代数结构，其本质是一个离散加 法子群，定义为一组线性无关的非零向量（格基）的整系数线性组 合。格密码基于格上问题的困难性，如最短向量问题（SVP）、最近 向量问题（CVP）及其变种等。格最初多被用于某些密码问题的分 析，直到 Ajtai 和 Regev 分别引入小整数解问题（SIS）和容错学习 问题（LWE），开启了实用的可证明安全格密码研究。SIS 和 LWE 被广泛用于构造密码哈希函数、身份认证和数字签名等密码方案以 及全同态加密、不可区分混淆等高等密码算法。目前主流的加解密 格体制和数字签名个密码体制基本基于这两个问题，NIST 目前选 择标准化的算法也多数是基于格的。基于格的算法的公私钥尺寸更 小，计算速度也更快，且能被用于构造多种密码学原语，因此更适 用于实际应用环境。

基于编码的密码：信道编码的目标是设计高效的冗余编码，以 便在传输过程中纠正由信道噪声引入的错误，从而实现正确的译 码。然而研究人员们发现某些编码的译码计算是困难的，这种译码 的困难性为构造安全的密码算法提供了思路。基于编码的密码通常 具有较小的密文，但其缺点是公钥大、密钥生成慢，在实用化方面 有待提升。1978 年 McEliece 提出了 Classical-McEliece，这是基于对 称群隐藏子群问题的困难性，使用 Goppa 码设计的公钥加密方案。 与现有公钥密码方案相比，加密速度更快，但由于公钥尺寸太大， 实用性较低。随着后量子密码的提出，McEliece 等编码密码方案因 具备后量子的特性，被认为可能成为基于数论的公钥密码体制的替 代品，并成功通过了 NIST-PQC 前三轮评估，并入选了第三轮胜出 算法集 Finalists。

基于多变量的密码：基于多变量的后量子密码算法是后量子密 码算法最早的类别之一，这类密码算法基于求解高次多变量方程组 这一 NP 难问题。通常，这些密码算法采用二次多项式，并将有限 域上一组二次多项式作为公钥映射。代表性的基于多变量的密码算 法包括 HFEv-类型的 GeMSS 签名体制和 UOV 类型的 Rainbow 签 名算法。这两个算法都顺利通过了 NIST-PQC 评估的前三轮，并于 2022 年 7 月被分别选入第三轮的胜出集合 Alternates 集和 Finalists 集。多变量密码算法相比于其他后量子密码算法具有签名验签速度 快、消耗资源少的优势，虽然其具有公钥尺寸大的缺点，但适用于 无需频繁进行公钥传输的应用场景。

基于哈希函数的密码：哈希函数是将任意长度的消息映射到固 定长度输出的映射，其算法完全公开，没有密钥或任何秘密信息，设 计的主要安全目标是使得找到各类碰撞最有效的方法是通用攻击。 哈希函数的困难性可直接假设等同于理想的通用攻击的复杂度，其 安全性并不会随着设计的优化而减弱。哈希函数多用于数字签名算 法，其中最具代表性的由 Merkle 提出的数字签名方案 MSS 采用哈 希树将多个一次性验证密钥的有效性降低到一个公钥的有效性。在 后量子标准化过程中，取得重要进展的代表性算法包括 XMSS 和 SPHINCS+。XMSS 是一种有状态的签名，是在 MSS 基础上提出的 一种具有更小签名的可证明安全的数字签名方案。SPHINCS+ 签名 算法是一种无状态的签名，采用了一种在 Merkle 树和 Goldreich 树 之间相折中的 SPHINCS 超树的结构进行构造。基于哈希函数的签 名方案的理论安全性高，但也存在签名体积过大，有状态的哈希签 名所能支持的签名次数有限等缺点。尽管目前基于 Hash 函数的数 字签名方案成果并不多，但是由于 Hash 函数独特的属性及其实用 性，在后量子时代，基于 Hash 函数的签名算法具有巨大的潜力。

基于曲线同源的密码：同源是指两条椭圆曲线之间存在一个映 射，这个映射能够保持它们的群结构同态。同源密码包括超奇异同 源 Diffie-Hellman（SIDH）和 CSIDH 等公钥密码算法，可用作传统 的椭圆曲线密钥交换（ECDH）的后量子替代。2011 年 Jao 等人首 次提出了超奇异同源 Diffie-Hellman 问题，并设计了基于超奇异同 源的公钥密码系统 SIKE。与其他几类算法相比，其公钥和密文尺寸都非常小，可以在通信量受限的环境下运行，但是其运行效率非 常低，其密钥生成、加密和解密速度几乎比基于格的算法低两个数 量级，这使其不易实现在一些计算性能不足的设备上。SIKE 算法 在 2022 年 7 月进入了 NIST-PQC 评估的第四轮，但仅 1 个月不到 就遇到了致命性的攻击。但是，SIKE 的失败并不意味着同源密码 的崩塌，同源问题本身并未被破解，仍是后量子密码的重要研究方 向之一。

2.后量子密码算法的标准化进程

（1）美国 NIST-PQC 后量子密码算法候选标准征集工作 美国国家标准与技术研究所（National Institute of Standards and Technology，NIST）于 2016 年启动了全球征集后量子密码候选标 准算法的工作7，目前已进入第四轮。其中，第一轮入选了 69 个 算法，第二轮入选了 26 个算法，第三轮入选了 15 个算法且分为 两组：Finalists 和 Alternates。前者在第三轮评估结束后即可进入标 准化阶段，后者还要经过第四轮评估才有望成为潜在的标准候选 者。Finalists 包括 7 个算法，其中密钥封装算法包括 Kyber、NTRU、 SABER、Classic McEliece 共 4 个算法，而签名算法包括 Dilithium、 Falcon、Rainbow 共 3 个算法。Alternates 包括 8 个算法，其中密钥 封装算法包括 Bike、FrodoKEM、HQC、NTRUprime、SIKE 共 5 个 算法，而签名算法包括 GeMSS、Picnic、Sphincs+ 共 3 个算法。

2022 年 7 月，NIST 发布第三轮评估报告 NIST IR 8413[24]，宣布了第一批标准算法。同时 NIST 也宣布将通过一轮独立于原项目 第四轮评估继续征集额外的数字签名算法，尤其欢迎不同于有结构 格技术路线的具有“签名短、验证快”优势的通用签名算法提案。 到 2023 年 6 月 1 日截止，共有 40 个新的后量子签名算法提交，目 前正在第一轮评估中 8。 2023 年 8 月，NIST 发布了后量子密码学的初始公开标准草案： 基于有结构格的公钥加密/密钥封装算法 Crystals-Kyber[25]，以及基 于有结构格的公钥签名算法 Crystals-Dilithium[26]、Falcon 与基于哈 希的公钥签名 SPHINCS+[27]。最终标准预计将于 2024 年发布。随 后 NIST 将发布弃用 RSA、Diffie-Hellman 和椭圆曲线加密技术的指 南。

值得注意的是，NIST-PQC 标准化项目中，中国学者主导或参 与提交了多个后量子密码算法，其中第一轮竞赛中有 7 个密码算 法参与评选，其中由中科院信息工程研究所路献辉教授团队设计的 LAC 算法进入了第二轮。另外，目前正在进行的针对后量子数字签 名算法展开的附加轮征集中，也有 8 个国人参与设计的密码算法。

（2）欧盟后量子密码标准化工作 欧盟并没有公布单独的后量子密码标准化计划，而是考虑沿用 但又不局限于 NIST 遴选出来的候选标准算法。事实上，欧盟通过 其“地平线 2020”项目[28]，配合了美国 NIST-PQC 后量子密码候 选标准算法的征集活动。美国 NIST 遴选出的第一批标准 4 个算法 中，其主提交人均来自欧洲。在德国 BSI[7]、法国 ANSSI[12]、荷兰 AIVD[8] 等欧盟国家的监管机构发布的后量子密码白皮书中，均表 示在使用 PQC 算法的过程中会重点参考 NIST 标准的评估结果。

德国联邦信息安全办公室（Bundesamt für Sicherheit in der Informationstechnik，BSI）信任基于无结构格的加密 FrodoKEM 和基 于编码的加密 Classic McEliece，认为它们虽然性能不及 Kyber，但 安全性更可靠，可以用于需要长期保密的高安全场景，并在其技 术规范（BSITR-02102-1）中推荐。由于目前在 NIST 标准化项目中 FrodoKEM 已落选，而 Classic McEliece 也未能成为第一批标准，尽 管德国 BSI 扔试图推动这两个算法在 ISO 的标准化（PWI19541）， 但现在改项目的状态似乎已经被取消[29]。法国国家信息系统安全局 （Agence nationale de la sécurité des systèmes d’information，ANSSI） 表示会严格遵循 NIST-PQC 流程，但认识到还有其他替代方案，所 以其并不打算将推荐的后量子算法限制为 NIST 获胜者，并且可 能会考虑其他算法。荷兰内政王国关系部情报安全总局 (Algemene Inlichtingenen Veiligheidsdienst, AIVD) 推荐使用 SPHINCS-256 作为 无状态数字签名、XMSS 作为有状态数字签名。

（3）其它国家和国际化组织的后量子密码标准化工作 英国国家网络安全中心（NCSC）建议 ML-KEM-768 和 ML-DSA65 为大多数用例提供适当级别的安全性和效率，在部署生产系统 之前，用户应等待基于最终 NIST 标准的实施的可用性[30]；加拿大 网络安全中心并未开发自己的 PQC 算法，而是与 NIST 合作开发 PQC。 在澳洲，澳大利亚网络安全中心（Australian Cyber Security Centre，ACSC）未开发 PQC 算法，选择将由 NIST 流程通知。新西兰 政府通信安全局 (GCSB) 在选择 PQC 算法之前将审查 NIST 运行 的 PQC 国际标准化计划的结果；

在亚洲，日本、新加坡等国表示将参考 NIST 的标准化方案。 韩国 PQC 标准化项目 KpqC9 于 2021 年宣布启动[9]，遴选过程计 划分两轮。第一轮评估已经于 2023 年底完成，共有 15 个算法提 交，最终有 8 个算法胜出，进入第二轮评估——预计将于 2024 年 11 月结束。 欧洲电信标准化协会（ETSI）、国际互联网工程任务组（IETF）、 美国电气和电子工程师协会（IEEE）、国际标准化组织（ISO）等均在 后量子标准化方面做了大量工程，制定了系列标准，如 ETSIGR QSC 001《量子安全算法框架》、IETF RFC 8391《XMSS:eXtended Merkle Signature Scheme》、IEEE 1363.1-2008《IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices》等。

（4）我国后量子密码标准化的准备工作 我国后量子密码标准算法的公开征集工作尚未正式启动，但是 已经做了一系列准备工作。2018 年 6 月，中国密码学研究会（CACR） 启动了全面密钥算法设计竞赛[31]。该竞赛历时一年半，最终于 2019 年 12 月底遴选出了 14 个后量子公钥密码算法。

2023 年，国家标准化管理委员会发布的《2023 年全国标准化工 作要点》[32] 指出要开展后量子密码准的前瞻研究和规划布局。2024 年的前沿研究[33] 透露，一些后量子密码方案已在我国密码行业标 准化技术委员会立项[34]。