未来安全的风暴热点：后量子密码（PQC）

量子通信&安全系列报告 后量子密码（PQC） ——未来安全的风暴热点 I 光子盒研究院2022年5月 2量子比特到127量子比特，量子计算正在飞速发展。由于量子计算的并行计算能力预计未来可为众多需要大 规模计算的难题提供解决方案，因此成为各国争相布局的技术前沿。但是，量子计算能力的提高同时将对当前经典密码体系下的信息安全造成巨大威胁。为了抵御未来量子计算实用化对当前密码体系的潜在冲击，几乎所有的加密算法都需要进行改进甚至必须进行迁移。由此，全球正在开展保护数据和加密通信的研究，其中包括2006年以来研究的后量子密码学（Post-quantumcryptography，PQC），又称抗量子密码学（Quantum-resistantcryptography），包括更新密码协议和标准等措施。 在美国，PQC的研究和实施活动得到多个政府机构的支持，包括NIST（国家标准与技术研究院）、NSF（国家科学基金会）、DOD （国防部）、DHS（国土安全部）和NSA（国家安全局）。此外，欧洲、日本、中国在PQC研究中也迅速崛起，力争在PQC标准中占据一席之地。在推进PQC技术标准的过程中，影响力最大的是NIST面向全球征集技术方案。 PQC能否成为抵御“量子之矛”（量子计算机）的“量子之盾”？这可能还需很长一段时间去验证，在没有开发出完全可用的量子计算机的情况下，难以真正衡量一个PQC算法的强度。即使如此，提前研究PQC并做好相应部署，仍十分必要。 光子盒全部原创作品版权归光子盒所有。其他媒体、网站或个人转载使用时不得进行商业性的原版原式的转载，也不得歪曲和篡改本网站所发布的内容。如转载须注明来源为“光子盒”，不得对本报告进行任何有悖原意的引用、删减和篡改。未经书面许可，任何机构和个人不得以任何形式翻版、复制或发表。如征得光子盒同意进行引用、刊发的，需在允许范围内。违规使用本报告者，法律必究。 光子盒引用其他资料的目的在于呈现信息，并不代表光子盒赞同其全部观点，不对其真实性、时效性负责。 本报告具有一定的时效性，仅表达截至发稿时的情况，不代表未来情况。在任何情况下，本报告中的信息或所表述的意见均不构成投资建议。 一、PQC恰逢其时1 （一）经典密码体系面临危机1 （二）PQC应运而生1 二、PQC算法方案与标准3 （一）主要方案及对比3 （二）标准研究和制定5 （三）PQC算法的硬件实现6 三、PQC应用体系7 （一）PQC主要应用7 （二）PQC应用时间8 四、PQC面临的潜在威胁与挑战9 （一）威胁9 （二）挑战9 五、全球竞争与应对11 （一）美国12 （二）英国16 （三）中国17 （四）欧洲18 （五）日韩19 （六）国际比较20 （七）小结22 六、PQC发展趋势预测23 （一）PQC逐步向全同态加密等更高级应用演变23 （二）公钥密码系统向PQC系统过渡仍有很大困难23 （三）短期内仍以多种密码体系混搭为主23 （四）金融机构将加快PQC评估和相关部署24 （五）企业将是推动PQC落地的主要力量24 （六）与PQC配套的硬件市场增长有望，更多芯片及安全公司入局25 关于我们26 联系我们27 表1量子计算能力对当前经典密码系统的影响2 表2经典密码、QKD和PQC比较2 表3四类PQC方案优缺点比较5 表4PQC标准研究及制定5 表5PQC技术的应用栈7 表6NIST公布的第三轮决赛方案12 表7NIST公布的第三轮备选方案13 表8NIST-PQC项目中的中国候选算法17 表9NIST-PQC项目第三轮的日本参与者20 图1量子计算能力演进图1 图2PQC主要应用领域8 图3全球后量子密码学市场的主要参与者11 图4NIST-PQC项目时间线12 图5DHS&NIST合作发布“应对量子技术风险的路线图”14 图6“应对量子技术风险的路线图”的七个步骤15 图72016-2020年PQC相关出版物数量总和21 图82016-2020年PQC相关风险投资综合21 图92016-2020年PQC相关专利数量总和22 随着量子计算技术不断取得突破，算力大幅提升，特别是以Shor算法为典型代表的量子算法的提出，相关运算操作在理论上可以实现从指数级别向多项式级别的转变。目前看来，量子计算机有潜力将破解速度从经典计算机的1万年，变为“一个响指”的时间。这意味着，在量子计算机面前，传统加密方式的信息被偷听窃密的可能性急剧增加。量子计算对公钥密码的潜在威胁是不容忽视的，有潜力完全攻破目前广泛使用的公钥密码算法，即便是增加参数长度也是无效的，因此，需要PQC作为新的解决方案。 图1量子计算能力演进图 注：尽管量子比特数不是衡量量子计算性能的唯一参数（还有保真度、相干时间、连接性等），但作为重要指标可以反映量子计算发展速度。 为了应对量子计算对公钥密码算法的威胁，PQC应运而生。PQC是能够抵抗量子计算对现有密码算法攻击的新一代密码算法，旨在研究密码算法在量子环 境下的安全性，并设计在经典和量子环境下均具有安全性的密码系统。 对于对称密码算法，尽管量子计算机可能降低现有算法的安全性，从k-bit降低为k/2-bit，但增大参数的长度对维护安全性是有效的。因此，PQC的研究重点是非对称密码算法。PQC与近些年发展迅速的量子密钥分发（主要包括QKD）有所差异，量子密码学涉及利用量子物理特性的密码算法，PQC关注的是可在经典计算机上运行的算法，这类算法即使用量子计算机也无法被破坏。 表1量子计算能力对当前经典密码系统的影响 密码算法 类型 作用 潜在量子计算能力威胁造成的冲击 AES 对称密钥 加密 增大密钥长度 SHA-2、SHA-3 — 哈希功能 输出长度增加 RSA 公钥密码 数字签名密钥建立 丧失安全性 ECDSA、ECDH 公钥密码 数字签名密钥交换 丧失安全性 DSA 公钥密码 数字签名密钥交换 丧失安全性 来源：ReportonPost-QuantumCryptography1、光子盒研究院 表2经典密码、QKD和PQC比较 保密类型 技术基础 专用设备 出发点 关注点 安全性 现存问题 经典密码 数学原理 无需专用硬件设备 解析数学难题 密钥的保密性 不能抵御量子计算机攻击 不能抵御量子计算机攻击 QKD 物理原理 需专用硬件设备 一次一密加密体制 解决密钥分配问题 量子环境下，理论绝对安全 成本高、有硬件要求、应用场景 有限 PQC 数学原理 无需专用硬件设备 解析数学难题 非对称密码系统 量子环境下，理论绝 对安全 未经过充分验证 来源：光子盒研究院 1https://csrc.nist.gov/publications/detail/nistir/8105/final PQC算法目前有四种主流方案：基于哈希（Hash-based）的公钥密码学、基于编码（Code-based）的公钥密码学、基于多变量（Multivariate-based）的公钥密码学、基于格（Lattice-based）的公钥密码学。 1.基于哈希的方案 基于哈希的签名算法由RalphMerkel提出，被认为是传统数字签名（RSA、DSA、ECDSA等）的可行代替算法之一2。基于哈希的签名算法由一次性签名方案演变而来，并使用Merkle的哈希树认证机制。哈希树的根是公钥，一次性的认证密钥是树中的叶子节点。基于哈希的签名算法的安全性依赖哈希函数的抗碰撞性。由于没有有效的量子算法能快速找到哈希函数的碰撞，因此（输出长度足够长的）基于哈希的构造可以抵抗量子计算机攻击。此外，基于哈希的数字签名算法的安全性不依赖某一个特定的哈希函数。即使目前使用的某些哈希函数被攻破，还可用更安全的哈希函数直接代替被攻破的哈希函数。 2.基于编码的方案 基于编码的算法使用错误纠正码对加入的随机性错误进行纠正和计算。一个著名的基于编码的加密算法是McEliece3。McEliece使用随机二进制的不可约Goppa码作为私钥，公钥是对私钥进行变换后的一般线性码。Courtois、Finiasz和Sendrier使用Niederreiter公钥加密算法构造了基于编码的签名方案4。基于编码的算法（例如McEliece）的主要问题是公钥尺寸过大。基于编码的算法包括加密、密钥交换等。基于多变量（Multivariate-based）的方案，被认为是能够抵御基于量子计算机攻击的新型公钥密码体制之一。 2MerkleRC,CharlesR,etal.Secrecy,authentication,andpublickeysystems[J].1979. 3McelieceRJ.Apublic-keycryptosystembasedonalgebraic[J].CodingThv,1978,4244:114–116. 4CourtoisNT,FiniaszM,SendrierN.HowtoachieveaMcEliece-baseddigitalsignaturescheme[C].ProceedingsofInternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity.Springer,2001.157–174. 3.基于多变量的方案 基于多变量的算法使用有限域上具有多个变量的二次多项式组构造加密、签名、密钥交换等算法5。多变量密码的安全性依赖于求解非线性方程组的困难程度，即多变量二次多项式问题。该问题被证明为非确定性多项式时间困难。目前没有已知的经典和量子算法可以快速求解有限域上的多变量方程组。与经典的基于数论问题的密码算法相比，基于多变量的算法的计算速度快，但公钥尺寸较大，因此适用于无需频繁进行公钥传输的应用场景，例如物联网设备等。 4.基于格的方案 格（Lattice）是一种数学结构，定义为一组线性无关的非0向量（称作格基）的整系数线性组合。格密码的主要数学基础是格中的两个困难问题：格的最短矢量问题（SVP）和格的最近矢量问题（CVP）。SVP是对于给定的一组基,找出其所生成的格中欧氏距离（两点之间的距离）最小的非零向量。即在格上找到一个非零向量v，满足对格上的任意非零向量u,均有||v||≤||u||。CVP是对于给定的格及任一向量,找出格中与该向量距离最近的向量。即在格上找到一个向量v,满足对格上的任意非零向量u,均有||v-y||≤||u-y||。格是一个困难的问题，并且难度还能控制，满足了成为密码学算法核心的必要条件。 PQC算法中，对格的研究是最活跃、最灵活的。基于格的算法在安全性、公私钥大小6、计算速度上可达到较好的平衡。�一，基于格的算法可以实现加密、数字签名、密钥交换、属性加密、函数加密、全同态加密等各类功能的密码学构造。�二，基于格的算法的安全性依赖于求解格中问题的困难性。这些问题在达到相同的安全强度时，基于格的算法的公私钥大小比上述其他三种方案更小，计算速度更快，且能被用于构造多种密码学原语，更适用于真实世界中的应用。因此，基于格的算法被认为是最有前景的PQC算法之一7。 5DingJ,GowerJE,SchmidtDS.Multivariatepublickeycryptosystems[M],volume25.SpringerScience&BusinessMedia,2006. 6注：公私钥大小是常见说法，指密钥长度，如2014位、2048位。 7Nejatollahi,H.,Shahhosseini,S.,Cammarota,R.,&Dutt,N..（2021）.Exploringenergyefficientarchitecturesforrlwelattice-basedcryptography.JournalofSignalProcessingSystems,1-10. 表3四类PQC方案优缺点比较 PQC方案分类 优点 缺点 基于哈希算法签名 安全要求是最小