后量子密码研究浅析

摘要：随着量子计算技术的快速发展，目前广泛使用的密码技术受到严重威胁。本文从量子计算对密码学的影响出发，介绍后量子密码的主要技术路线，相关标准化进展，最后展望相关技术发展。

量子计算对密码学的影响

量子计算利用量子叠加与量子纠缠等量子力学原理进行计算，在一些特定问题上具有远优于传统计算的能力。自 20 世纪八十年代提出，量子计算已取得巨大进步。2019 年，Google 研究人员构建 53 量子比特处理器，宣称成功演示了“量子计算优越性”。2020 年，我们科研团队构建九章量子原型机，实现高斯玻色采样任务的量子计算优越性：在 200 秒内生成的样本数量对于经典超级计算机需要进行 25 亿年的计算。IBM、微软、Amazon、华为、阿里巴巴等国内外科技巨头均纷纷布局量子计算软硬件开发，量子计算技术正快速发展中。

要发挥量子计算的优势，需要量子计算硬件支持，同时还需要结合量子算法。据 Quantum Algorithm Zoo 网站统计，目前已有数百个量子算法用于不同问题的求解，其中对密码学有较大影响的量子算法主要有 Shor 算法、Grover 算法、Simon 算法：Shor 算法：由 Peter Shor 于 1994 年提出，可用于求解整数分解与离散对数等问题，将求解复杂度由经典计算机的指数规模降低到多项式级别，对 RSA、ECC、SM2 等当前广泛使用的公钥密码算法具有严重威胁。

Grover 算法：由美国计算机科学家 Lov K. Grover 于 1996年提出，用于在无序数据库中搜索特定项，使得搜索复杂度由经典计算机线性时间复杂度降低为平方根时间复杂度，将使目前所有密码算法的有效密钥长度减半。

Simon 算法：由 Daniel R. Simon 于 1994 年提出，可用于快速获取一个函数的周期，将复杂度由经典算法的 O(2^(n/2)) 降低到 O(n)。Simon 算法导致部分在经典计算模型下可证明安全的密码模型在量子时代不再安全，也对 CBC-MAC、PMAC、GMAC等分组密码工作模式构成严重威胁。

后量子密码技术路线

传统的公钥密码算法（如 RSA、SM2 等）所基于的数学难题，如整数分解、离散对数等，易于被量子计算机求解，基于这些数学难题的密码算法在量子时代将不再安全。为了应对这一挑战，后量子密码学（Post-Quantum Cryptography，PQC）作为一种新兴的密码学技术应运而生。

PQC 基于现有量子计算仍难以有效求解的数学难题，PQC 研究的目标是提供一种能够在量子计算时代仍然保持安全性的密码算法和协议。目前，PQC 算法的主要技术路线有基于杂凑、编码、多变量、格和同源等问题的方案：

基于杂凑（Hash-based）的方案使用 Merkle 杂凑树等技术进行运算，主要用于生成数字签名。其安全性依赖于杂凑函数的安全性，而不是依赖于数学问题的困难性假设，如果所采用的杂凑算法被攻破，只需将杂凑算法更新为更安全的算法，就能确保签名算法的安全性。

基于编码（Code-based）的算法利用纠错码构造单向函数，其安全性依赖于编码理论中的 Syndrome Decoding（SD）和Learning Parity with Noise（LPN）等难解问题，可用于构建加密算法、数字签名和密钥交换方案等。

基于多变量（Multivariate-based）的密码算法使用有限域上的多变量二次多项式组构建加密、签名和密钥交换等方案，其安全性依赖于求解多变量方程组的困难性，主要用于构建签名算法，代表性算法等。

基于格（Lattice-based）的密码算法基于格中的难解问题，可以用于构建加密、数字签名和密钥交换等密码方案。这类方案具有快速计算速度和较小的通信开销，安全性、公私钥尺寸和计算速度方面取得了良好的平衡，有望成为标准化的选择。

基于同源（Isogeny-based）的密码算法利用超奇异椭圆曲线同源问题构建加密和密钥交换等密码方案。这类方案具有较小的公私钥尺寸，但运行效率较低。代表性算法包括 SIKE 等。

关于对称密码算法，人们普遍认为其在量子时代仍能够保持一定的安全强度，可通过增加密钥长度或杂凑值长度的方式抵抗量子攻击。抗量子攻击的对称密码研究相对较少，设计方案只有Saturnin 等少量方案。

标准化进展

为应对量子计算威胁，国际上各大标准化组织正积极推动后量子密码标准化工作，为后量子密码应用作储备。

早在 2012 年，美国 NIST 就启动了后量子密码标准化工作，并于 2016 年 12 月正式启动后量子密码算法征集活动。经过三轮评选以及额外的两年评估，NIST 在 2022 年 7 月选出 4 个算法进入标准化程序，包括公钥加密与密钥交换算法 CRYSTALS-KYBER，与数字签名算法 CRYSTALS-Dilithium、FALCON、SPHINCS+。同时，NIST 为使算法技术路线多样化，在标准化上述算法的同时启动第四轮算法评估并征集新算法。值得一提的是，第三轮终选算法之一基于多变量的算法 Rainbow 以及进入第 4 轮评估的基于椭圆曲线同源技术的算法 SIKE 已被研究人员攻破，无法提供应有的安全性。

我国在 2018 年启动全国密码算法设计竞赛，其中非对称算法部分征集到 38 个算法，经过形式审查、公开评议、检测评估和专家评选，竞赛最终评出14项优胜算法：11个基于格困难问题的算法、1 个基于编码问题的非对称加密算法、1 个基于超奇异椭圆曲线上同源问题的密钥交换协议和 1 个基于置换核问题的数字签名算法。

欧洲电信标准化协会（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》等。

研究展望

后量子密码学是一个充满挑战和机会的领域，面对即将到来的量子计算时代，它的研究与应用将对整个密码学界和信息安全产业产生深远的影响。

除了后量子算法与标准化研究外，将现有密码系统向能够抵御量子计算攻击的后量子密码系统迁移也是一项重要任务。后量子迁移过程需对现有的密码系统进行评估和分析，确定其在量子计算机攻击下的脆弱性，并设计出能够抵御量子攻击的替代方案。后量子密码迁移是一个复杂的过程，涉及密码算法、协议、硬件设备和网络基础设施等多个方面，需要密切关注量子计算技术的发展，并与密码学研究人员、行业和标准化组织密切合作，迁移过程需要谨慎规划和逐步实施，以确保安全性和平滑过渡。

太阳成集团tyc4633作为一家密码企业，为产业提供高质量密码供给是职责所在。太阳成集团tyc4633后量子密码研究小组在后量子迁移、后量子密码算法与标准化研究等领域拥有充足的技术储备。一方面，太阳成集团tyc4633紧跟后量子密码研究进展，掌握后量子密码算法和协议及其性能特点等，及国内外相关标准化进展等。其次，研究了密码系统风险评估、迁移策略等，制定了一些方案。太阳成集团tyc4633也与产学研建立了广泛深入的合作，储备了后量子密码相关技术资源。欢迎交流探讨。