后量子密码发展综述

密码技术是信息技术领域的重要分支，随着科学技术的发展，密码技术不断进步，从机械密码到电子密码，再到现代的数字密码，每一步都推动了人类文明的快速前行。到了互联网时代，万物互联使得世界发生了颠覆性变化，虚拟空间的互认互信成为核心要素。而现代互联网的互联互信极大地依赖于公钥密码体系，不仅可以保证消息的机密性，还可以验证消息的来源，提供了数据加密、身份验证和消息完整性检查等功能，确保了互联网通信的安全和可靠。随着量子计算技术及量子计算机的迅猛发展，当代被广泛使用的密码系统受到量子计算的严重威胁。公钥密码学也开始技术革新，迎接量子计算时代的挑战，并且在密码标准化方面已取得阶段性进展。因此，有必要全面掌握当前已知抵抗量子计算的公钥密码，总结后量子密码技术路线及其特点。本文进一步新增最新的针对密码算法的量子计算攻击进展，分析各种类别后量子密码的优劣势，提出后量子密码研究及后量子迁移的建议，为后量子密码的深入发展提供支撑。1量子时代带来的挑战量子计算技术及量子计算机极大地威胁着经典密码的安全。一方面，量子计算破译经典密码具有显著优势。为保证信息的加密传输，基于数学上困难问题设计的RSA、DSA、ECC等公钥密码算法已经维护了近50年的网络信息与通信安全。但是，随着第二次量子革命中的量子计算机的快速发展，以及以Shor算法和Grover算法为代表的量子计算算法的高速迭代研究，给现有互联网基础设施带来巨大的信任危机。Shor算法能在多项式时间内求解给定大整数的大质因数，与经典整数分解算法相比，其能够指数级提升效率；Grover算法是搜索非结构化数据库或无序列表的量子算法，应用于密码破解使得等效于同等攻击下密钥长度减半。Google在2022年发布的资料表明，其计划在2030年完成100万量子比特的量子专用计算机的研制；2022年12月，清华大学龙桂鲁教授团队提出基于经典的Schnorr算法及同时依靠量子近似优化算法（QuantumApproximateOptimizationAlgorithm，QAOA）来优化Schnorr算法中最耗时的部分，实现了仅用10个超导量子比特就完成了48位因式分解，同时提出最低仅需要372个物理量子比特的量子计算机即可能完成RSA-2048的破解。另一方面，量子攻击策略具有时间优势，不一定只在量子计算机成熟后才发挥作用。攻击者先将能够获取的所有加密状态信息存储起来，等到实用的量子计算机建造后再实施密码破译，而量子计算的快速发展极大地缩短了时间周期。按照国家保密管理要求，重要的信息管理期限甚至在10年以上。这意味着，如果2033年前研发出了可用于破译现有密码体制的量子计算机，那么在互联网或者其他公共信息网络传输的信息都存在极大的泄密风险。量子计算技术发展直接倒逼密码技术的发展，换言之，目前快速发展的量子计算技术迫使密码技术必须尽快采取应对措施。2后量子密码发展现状及技术路线2.1抵御量子威胁的战略意义传统公钥密码使用经典计算机在多项式时间内无法求解的公认数学困难问题作为安全基础。类似的，当代密码学探寻当前量子计算机无法有效求解的困难问题作为安全基础设计密码体制，这些体制被称为抗量子计算密码（QuantumResistantCryptography，QRC）或者后量子密码（Post-QuantumCryptography，PQC）。美国将后量子密码作为应对量子计算最具优势的技术手段，提出了《量子计算网络安全准备法案》，制定了政府信息技术向后量子加密过渡的路线图，并由美国国家标准与技术研究院（NationalInstituteofStandardsandTechnology，NIST）自2016年开始启动全球征集遴选PQC标准算法的工作。2022年9月，美国国家安全局（NationalSecurityAgency，NSA）发布了CNSA2.0时间表，计划于2033年完成后量子密码迁移。根据底层数学困难问题分类，后量子密码算法研究目前主要有5种技术路线，分别是基于格的密码、基于编码的密码、基于多变量的密码、基于哈希函数的签名以及基于曲线同源的密码。2022年7月NIST公布的后量子密码标准化遴选进展中，基于格的密码和基于安全哈希函数的签名算法已入选为标准，基于编码和超奇异同源的密码算法入选第四轮筛选并开展进一步评估，而其中基于超奇异同源的密码算法SIKE被完全破解。2.2基于格的后量子密码算法格是实数域上线性空间中的离散子群，可表达成一组向量的整系数线性组合。给定一组线性独立的向量图片它们生成的格是集合图片其中n被称为格的维数，图片被称为这个格的一组基。一个n维格具有很多格基，它的任意两组格基之间相差一个n阶幺模矩阵。计算格中的最短非零向量是重要的困难问题，是当代格密码的安全基石。Ajtai提出的短整数解（ShortIntegerSolution，SIS）问题和Regev提出的带错误学习（LearningwithErrors，LWE）问题开启了实用的可证明安全格密码研究。当前实用且安全的加解密格体制、数字签名格密码体制基本基于上述两个问题设计。一方面，格密码具有上述困难问题作为理论规约的安全基础；另一方面，格密码的空间时间资源消耗适中。进一步的，基于格密码能够设计属性加密、同态加密等高等密码学应用算法。因此，业界广泛认可格密码是最有前景的后量子密码技术分支。2.3基于编码的后量子密码算法经过编码的信息在信道上传输，由于噪声产生错误，在接收端通过译码算法恢复。基于编码的密码，其理论依据来源于随机线性码的译码是困难问题。1978年，使用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年提出的极小秩距离攻击，极大地降低了GeMSS签名算法的安全性，紧接着2022年提出Rainbow签名算法的攻击算法，极大地提高了密钥恢复攻击效率。因此，GeMSS与Rainbow算法均未能进入NIST后量子标准化遴选第四轮。基于多变量的密码具有资源优势，但需要进一步研究其安全性。一方面，基于多变量的密码具有较高的运算速度和较小的签名尺寸；另一方面，类似于编码密码，基于多变量的密码算法的公钥尺寸也很大，算法实用性受到限制。另外，NIST后量子标准化的情况表明，基于多变量设计安全高效的加密体制是挑战性高的研究工作。2.5基于哈希函数的后量子密码算法分组密码和哈希函数是研究深入且具有良好标准化对象的密码组件。基于对称密码设计后量子密码算法具有较好的工具基础。基于哈希函数的签名体制，利用提出的一次性签名作为叶子节点，利用Merkle树结构构造数字签名方案。代表性算法包括XMSS和SPHINCS+，前者是有状态的签名，后者是无状态的签名，两个算法在后量子标准化中均取得重要进展。NIST后量子标准化中出现基于分组密码和非交互零知识证明的签名体制Picnic，该体制具有所使用的对称组件效率高，设计模块化通用性强，公钥尺寸小，签名尺寸大，签名速度快的特点。这一方案的安全性和优化版本值得进一步研究。2.6基于曲线同源的后量子密码算法所谓同源（Isogenies），就是指两条椭圆曲线之间保持群结构同态的映射。一个同源的表达形式常如：给定两条定义在图片的椭圆曲线图片和图片记为映射图片图片分别是图片上的有理点）。2011年，首次提出了超奇异同源Diffie-Hellman问题（SupersingularIsogenyDiffie-Hellman，SIDH），并设计了基于超奇异同源的公钥密码系统SIKE，该算法也被提交到NIST成为唯一的同源类候选算法。与其他4类候选算法最大的区别在于，基于SIDH的算法参数尺寸非常小，计算速度较慢。但是，2022年至今，SIDH及其加密算法SIKE遭到提出的密钥恢复攻击，最终被完全破译。需要指出的是，SIKE的失败并不意味着基于同源的密码完全崩塌，同源问题本身并未被破解，以基于同源的签名SQISign为代表的算法仍然引领这一方向的研究。2.7后量子密码技术路线对比通过粗略对比，上述5类后量子密码的技术特点非定量对比如表1所示。表15类后量子密码的技术特点非定量对比3后量子密码的发展趋势通过对后量子密码研究现状的论述，结合当前量子技术与密码学的发展，针对后量子密码的技术需求和发展趋势提出一些观点。3.1后量子密码算法的安全性评估如前文所述，后量子密码算法主要集中在寻找一类或多类在量子计算攻击下的NP数学困难问题，而目前仅是利用Shor算法和Grover算法本身或其优化算法作为攻击的源算法。随着量子计算的发展，存在产生新的量子算法的可能性，或将再次颠覆现有的后量子密码算法体系。因此，在后量子算法的选择、试点探索、应用部署等任一阶段，针对已知和未知攻击的安全性评估将一直是后量子密码研究的重要方向。3.2后量子密码迁移应用验证探索NSA已发布了后量子迁移时间表，使用已遴选出的基于格、哈希函数的签名的后量子算法作为基础开展后量子迁移，它们与现有经典密码算法相比均存在尺寸更大、资源消耗更多的情况。因此，有必要探索后量子密码迁移所需软件和硬件平台极限，提前研究能同时兼容经典密码与后量子密码的可自适应的密钥管理系统、密钥分发系统、终端硬件平台，实现向后量子迁移的平稳过渡。3.3后量子密码与基于物理学的量子通信技术的融合应用探索基于物理学的量子密钥分发技术（QuantumKeyDistribution，QKD）是目前量子通信技术研究和投入较多的一个方向。以物理学、光学为理论基础的量子密码技术能够在使用一次一密的情况下实现信息论证明的绝对安全，能够抵抗量子计算的超高并行算力。而该技术方向中无论是具有远传输距离优势的离散变量量子密钥分发技术（DiscreteVariable-QKD，DV-QKD）还是具有高速率优势的连续变量量子密钥分发技术（ContinuousVariable-QKD，CV-QKD），均有中国团队占据国际领先技术优势。但是，目前QKD技术存在一些实用化技术难题亟须解决：一是小型化、低成本、高速率、远距离的系列技术需突破；二是由于与经典密码学的实现基础完全不同，导致无法直接与现有通信网融合。因此，探索QKD技术与PQC技术互补，建立具备保护特定关键基础设施的对抗量子攻击的密码网络，有利于未来做好网络安全保护。3.4量子环境下新的数学问题探索NIST的CRYSTALS-KYBER、FALCON、CRYSTALS-Dilithium和Sphincs+4个PQC标准化算法中，除了Sphincs+为基于哈希函数的签名算法，其他均为基于格的密码算法。国内也投入了大量研究力量集中攻关基于格的密码算法。后量子密码算法除了基于格、哈希函数、多变量、编码的技术路线，还有基于同源曲线的技术路线。因此，有必要拓展更多的后量子密码算法体制研究方