《自然》综述：后量子密码迁移指南
虽然一些后量子密码（PQC）算法已被破解，但后量子密码必然是保护未来信息安全的重要手段。除了不断修复漏洞外，后量子密码的另一个挑战是如何向新的密码系统迁移。针对这一问题，最近，来自量子初创公司SandboxAQ和谷歌的科学家在《自然》期刊上发表了一篇综述——《推动组织过渡到后量子密码》。
有了Shor算法，量子计算机有望打破现代公钥密码系统。因此，这些密码系统需要被抗量子算法——也叫后量子密码（PQC）算法所取代。
在过去的二十年里，PQC研究领域蓬勃发展，产生了一大批有望抵抗量子攻击的算法，这些PQC算法也正在被一些标准化机构选择和标准化。然而，即使有了这些重要工作的指导，危险并没有消失：有数十亿的新旧设备需要过渡到PQC算法，这需要一个长达数十年的过渡过程——必须考虑到安全、算法性能、安全实施的便利性、合规性等方面。
在这篇综述中，研究人员从组织（包括企业和政府机构）的角度介绍了PQC的过渡：讨论了过渡的时间表、保护系统免受量子攻击的策略，以及将前量子密码(pre-quantum cryptography)与PQC结合起来以减少过渡风险的方法。最后，文章提出了现在就开始实验、“以应用为中心”的标准，并提供了一系列建议帮助组织能够顺利、及时地向PQC过渡。
一般来说，密码学是对数学技术进行研究，以执行信息政策。这些政策广泛规定谁可以发送、阅读和编辑数字信息。常见的用途包括防止窃听者的安全、执行对数据的读写访问，以及信息验证。所有这些技术都有一个共同点：它们依赖于某些数学问题的不可控性。为了确保一个密码系统是安全的，需要证明破解这样一个密码系统的难度至少与解决一些被认为是难以解决的数学问题一样，而这些数学问题对于不掌握某些秘密信息的人来说是难以解决的，因此被称为“密钥”。撇开实施错误不谈，问题的难度是密码系统的核心安全保证，如果其容易被密码分析技术所驳倒，那么这个密码系统就认为被破解了。
支撑今天密码系统的关键数学技术密切相关，它们都基于整数分解问题和离散对数问题。密码系统的安全性依赖于解决这些问题的难度。1994年，数学家Peter Shor设计了一种量子算法，承诺在因式分解整数和求离散对数方面比非量子算法有指数级的加速，这在理论上允许量子计算机破解目前使用的大多数公钥密码系统。也就是说，当足够大、容错（LFT）的量子计算机建成后，我们目前的许多密码系统将被破解。量子计算机今天已经存在，但它们是高度初级和不完善的机器，需要大量的技术演进才能实现广泛应用。量子计算的困难主要在于创建高精度的硬件：即使是能够以0.1%的错误率执行基本操作的量子比特，在整个系统中，这些错误也会以指数形式传播和增长，从而限制了有用的量子计算机的规模。每一个额外的量子比特都会使量子计算机的功率增加一倍，因此，当谷歌A在2019年底宣布“量子计算优越性”时，他们的实验是在一个只有53个量子比特的处理器上进行的。但是，破解RSA-2048（其中RSA是一种密码系统，2048是最常用的参数集）所需的噪声量子比特数量估计约为2000万。
那么，为什么尽管这一发展意味着工程上的挑战，但仍要紧急采取行动呢？
在面对量子威胁时，需要新的密码原语（cryptographic primitives）来维持通信和信息存储的安全。这些密码算法被称为后量子密码，并且基于被认为是抗量子的数学问题。尽管已经存在基于量子的加密技术可以安全地对抗量子计算机，但与其他方案相比，PQC的一个实质性优势是：它可以嵌入任何常规通信基础设施或当代设备中。
02
向PQC过渡，组织该如何规划？
后量子密码时间线。这三条时间线可以被认为是：对密码系统的威胁（上），组织在迁移过程中应该经过的步骤（中），以及由多国标准机构主导的标准化过程（下）。
上图就PQC过渡的过程和时间表向各组织提出了一系列建议，总结了该领域的情况、描绘出了相应发展时间表，并为利益相关者汇编了资源清单。
最上面的红色时间线描述了两个最重要的“量子威胁”，以及它们将在何时变得至关重要。第一种威胁被称为“现存现解型”（SNDL）攻击，它目前已经是一个活跃的威胁。SNDL意味着对手现在就捕获有价值的加密信息，将其存储起来，一旦有了量子计算机再将其解密：假定这些信息在未来仍然有价值。第二种量子威胁是指对RSA和椭圆曲线密码（ECC）的破解——这是目前最普遍的两种用于加密信息的公钥算法，可以用肖尔算法破解。这将使对手能够伪造RSA和ECC数字签名，并对依赖它们的系统构成风险：如安全网络浏览、零信任架构和加密货币。
灰色的时间线描述了各组织在向PQC过渡时需要采取的两项行动。第一个行动是战略计划和技术实验，第二个行动是在生产系统中有效地采用PQC。文章强调，战略规划阶段必须在LFT量子计算机能够有效地攻击RSA和ECC之前完成（也就是说，这个过程不应该被推迟）。
最后，最下面的蓝色时间线涉及到由相关政府和行业组织的标准制定过程，特别是美国国家标准与技术研究院（NIST）的PQC标准化进程。
鉴于其成本低、易于集成到当前的基础设施、加密功能齐全，标准化机构和组织已经自然而然地趋向于使用PQC。因此，文章建议对保护他们的系统和用户免受量子攻击的组织应该采用PQC作为他们的主要量子保护策略；对于那些还没有开始在系统中整合PQC、甚至没有计划的组织，强烈建议他们现在就开始努力。如今，SNDL攻击已经是可行的了，还没有相关行动的组织已经晚了，今后面临的量子威胁风险也将越来越大。
不过，尽管有来自工业界的压力，标准化制定机构（如NIST）也应该明确重点，以安全第一的思想来创建标准。建议各组织应明确表达他们对PQC标准的兴趣，以促使标准化机构为这项工作分配资源。
现在！
鉴于LFT量子计算机还没有出现，下文中提供了一些论据，以强调为什么现在开始向PQC过渡是重要的。
1）先存储后解密
SNDL攻击对现在使用量子易损密码技术加密的信息构成了威胁。这样的加密数据通常是在公共互联网基础设施上传输，可以被收集、无限期地存储；未来，一旦对手接触到LFT量子计算机，就会被解密。在某些情况下，这并不是一个潜在隐患。然而，一些重要的商业机密、医疗记录、国家安全文件等，它们有数十年的保质期，必须在很长一段时间内保持机密。出于这个原因，SNDL攻击是不再推迟开始过渡的最重要的论据之一。
2）远期（Far-horizon）项目
PQC具有直接重要性的另一个原因是，现在正在设计和计划的项目寿命很长（例如，几十年）。例如，现在正在生产的许多汽车、飞机、火车和轮船，预计将在20年甚至30年后投入使用。某些情况下，它们会包含一些模块，其中一个密码系统可以被替换成另一个，但并不是所有模块都是如此。当特定应用的硬件被用来实现密码学并在产品生命周期内保持不变时，情况尤其如此。
另一个例子是国家关键基础设施项目，它们具有高可用性：有些应用需要99.999%的可用性，或每年仅6分钟的停机时间，而升级密码学软件/硬件需要不可接受的成本。
3）密码系统过渡需要时间
历史经验表明，密码系统的过渡需要相当长的时间。
ECC早在20世纪80年代就被提出，尽管比RSA更有效（空间和速度方面，取决于参数），但它花了20多年才获得广泛的采用。哈希函数是另一例加密工具，从其诞生到应用花了很长时间。例如，NIST的SHA-3密码早在2007年就宣布了，但到2021年仍然没有得到广泛采用。因此，密码系统的过渡（即使是比PQC简单得多的过渡）通常需要几年，甚至几十年。PQC的过渡更为复杂，因为许多方法都是相对较新的，而且许多候选算法的性能比目前的算法要差很多。
4）采用PQC标准的路径更加清晰
第四个原因是关于PQC标准化的一系列宣布。
2019年，NIST发布了基于状态哈希的签名标准，2020年宣布了他们的PQC竞赛的第三轮决赛（和备选赛道）结果。因此，密码学界现在有了一个更明确的方向，即哪些原语有可能成为PQC标准化密码系统套件的主干。尽早行动可以为消除错误、培训劳动力和为未来的漫长过程留出充分的准备时间。
5）NIST的PQC项目
在相当长的一段时间里，NIST一直非常积极地塑造网络安全的最佳实践。例如，广泛使用的高级加密标准（AES）算法和最近的SHA-3算法。2016年，随着量子威胁逼近，NIST启动了相关进程来规范公钥PQC算法。
NIST后量子密码进程时间表。显示了NIST PQC标准化过程中的标志性事件，从2016年开始到现在。这个过程是迄今为止对PQC进行的时间最长、最全面的研究。
从这个过程开始，NIST就承认PQC的过程将比AES和SHA-325的过程复杂得多。其中一个原因是，公钥密码学和数字签名的要求比对称密码学更复杂；另一个原因是研究提供的解决方案的广泛性。比较这些不同的方法带来了独特的挑战：如权衡安全性、密钥大小、延迟、带宽和安全实施的难易程度。
NIST对最初收到的82个提交文件的范围进行了安全评估、外部安全分析，以及NIST内部研究人员进行的密码分析。经过一年多时间，NIST宣布26种算法将进入第二轮程序。
2020年7月，NIST宣布了将进入第三轮的15种候选算法。其中，有7个被列为“入围”：4个非对称加密或密钥封装机制（KEM）和3个签名方案；8个被列为“备选”：5个非对称加密或KEM和3个签名方案。
2022年7月，NIST公布了第三轮评估结果。将进行标准化的算法包括：CRYSTALS-Kyber、CRYSTALS-Dilithium、Falcon和SPHINCS+，其中主要是格密码，另有4个算法进入第四轮的进一步评估：BIKE、Classic McEliece、HQC和SIKE。到2024年，完成整个标准化过程。
NIST后量子密码算法性能。上图显示了密钥交换算法的密码文本和公共密钥的大小，其中类似的算法按颜色分组。底部的图显示了密码文本和公共密钥的大小与所需的计算量。密钥生成器（Keygen）用于生成公钥和私钥，封装（Enc）使用公钥对秘密进行加密，解封装（Dec）使用私钥对秘密进行解密，然后秘密被安全地共享。
对于小的公共许可证密钥和密码文本，同源算法的空间效率极高，但速度性能较差；非结构格被认为是最保守的方法，并且在安全性方面比结构化的变体更受密码界的信任；同样，McEliece系统也被认为比其它系统更加保守；相比之下，结构格在所有指标上都表现得更好，但至少要付出一个额外的安全性假设。总之，这两类代表了安全和效率之间的权衡。
6）其他与PQC有关的标准化工作
美国互联网工程任务组（IETF）负责制定传输层安全（TLS）协议，该协议被广泛用于安全的网络浏览。如今，IETF正在进行一些努力，将后量子原语整合到不同的协议中，例如在TLS31和互联网密钥交换（IKE）标准。其目的是将基于RSA和ECC的方案与PQC方案结合起来，而不用面对新密码技术所固有的漏洞。第三代伙伴关系项目（3GPP）已经开始了关于该主题的初步讨论，但可能会等待NIST公布标准后再提出新的无线加密协议。
欧洲电信标准协会（ETSI）是另一个在后量子通信技术方面发挥积极作用的组织，它有关于量子密钥分发（QKD）和PQC的工作组，后者已经发布了量子安全密钥交换的标准。2015年，ETSI发布了一份白皮书，分析了一些最有前途的后量子密码算法，并讨论了这种过渡的主要挑战。
在中国，中国密码学会在2019年举办了一个为期数月的短期竞赛，以快速确定少数算法的标准化。一等奖授予了密钥交换类别中的轻量级认证加密密码（LAC）方案，这个密码系统进入了NIST程序的第二轮，但没有进入第三轮，原因是发生了一些连续攻击。
7）对各组织PQC标准化的建议
基于同态的哈希签名（HBS）是一种已经被多个标准化机构（例如NIST）标准化的技术。尽管需要实施一个强大的状态管理机制，这项技术有一个突出的优点：它的安全保证基于最小的假设。因此，那些需要在适合状态管理的应用中过渡到PQC的组织应该考虑把HBS作为一个潜在的解决方案。
NIST的PQC项目所选算法的标准预计将不晚于2024年发布。因此，文章建议监测这一过程的组织现在就应该开始对入围和替代的候选算法进行试验，这对减少NIST PQC标准发布后的过渡时间很重要。
乍一看，加密算法的过渡可能看起来是一项简单的任务，与任何其他算法的替换相似：老一代的（易受攻击的）算法被新一代的（后量子）算法所取代。不幸的是，鉴于对手可以（而且会）在任何时候利用不安全的节点来触发破坏性攻击，这项任务并不简单。为了补充本展望中的具体建议，作者提供了一套通用建议，以进一步帮助各组织以最小的安全风险、较短的过渡时间和优化成本过渡到PQC。
1）加密灵活性
面对量子化后的迁移，为了制定一个整体、安全的方法，组织必须采取措施实现加密的灵活性。因为改变加密算法，或将其与现有的加密算法分层，需要的不仅仅是直接工作本身。在密钥大小、加密文件大小和签名长度方面也存在差异。调整基础设施以适应这些考虑，将是迁移工作中的一个重要部分。此外，尽管新的算法作者和评估者做出了最大的努力，但在算法、操作模式或具体参数方面，仍有可能出现某种程度的持续变化，从而影响到更广泛的系统配置。
在准备实施这些变化时，组织应计划加密的灵活性，特别是在集中管理的工具包和服务上采用抽象层，以尽量减少任何后续的变化。同样，这种工具的实施也应该包括这种工具的应用程序或基础设施用户的能力，以应对调整后的数据格式和大小。明确地说，在启动一个加密敏捷性计划时，各组织应实施一套集中提供的加密库和服务，从应用和基础设施团队中抽象出正在使用的算法；确定数据字段和大小的依赖性，并调整数据库、数据存储、协议和其他假设当前固定字段大小的软件。
关于标准机构和监管机构，加密敏捷性应嵌入目前正在开发的任何标准中，例如，6G必须是固有的加密敏捷性和PQC兼容；关键基础设施部门的特定行业监管机构应紧急开始规划部门协调，以减少系统性风险。
2）优先级战略
为了确保过渡成功，组织需要注意的第一件事是确定优先级：这指的是确定哪里需要首先进行PQC过渡。这很重要，因为能够执行这项任务的劳动力是高度专业化的、通常稀缺的。
关于这种工作的优先次序，首先我们需要确定风险最高的加密方案。在急需保密的情况下，密钥交换算法的风险最高：因为密钥交换程序的结果可以被捕获，以便以后被破解（SNDL攻击）。同时有些系统虽然很难更新，但并不绝对需要立即的后量子保密性，如车辆通信。在这些情况下，安全数字签名应该是第一步，然后可以在以后的日子里用来推动密钥交换算法的更新。
3）混合算法
科学界并没有用研究相对较少的后量子算法来取代现有的算法，而是想出了一个简单而有效的方法：将传统算法和后量子算法结合到同一个机制中。换句话说，即使PQC算法随后被确定为有缺陷，经典方案所提供的安全性仍然可以得到保证：安全性在这种转变中只有潜在的增加，而没有减少。
为了结合密钥交换算法，需要使用每种算法（一种PQC算法和一种经典算法）来生成一个单一的共享秘密。这两个秘密可以结合起来，产生一个单一的对称密钥。这样一来，愿意攻击该系统的对手就必然需要同时破解经典和PQC方案。剩下的一个问题是如何结合这两个共享秘密。主要的方法是：在通过密钥推导函数（KDF）之前或之后，将共享秘密连接起来。
4）认证要求
由于合规性，许多密码学的用户被要求遵守NIST定义的联邦信息处理标准（FIPS）。如果将传统的公钥密码系统换成后量子替代品意味着失去FIPS认证，那将是一个问题。例如，联邦机构在购买基于密码学的安全系统时，必须确保有FIPS 140-2证书，否则就不符合条件。幸运的是，这一点已经有了规定，上面提到的“混合”方法允许从业者保持他们的FIPS 140-2等级，因为他们只是在增加安全，而不是取代它。
5）PQC资源
过渡期计划的一部分是对为这些新方案提供基础理论教育，以及掌握软件应用，分析它们与公司网络基础设施的整合。好的理论资源包括A decade of lattice cryptography、Post-Quantum Cryptography等书，对该领域提供了广泛的解释。
有许多地方可以获得NIST方案的软件实现。其中最全面的资源库是开放量子安全项目的Liboqs。其他资源包括BoringSSL和Tink，它们在混合模式下实现了NTRU-HRSS和X25519（一起称为CECPQ2）。对于高度标准化的实现，可以考虑SUPERCOP，它已经成为PQC方案的事实上的基准工具。用于PQC的加密硬件不太容易获得，而且是一个似乎需要进一步研究的领域。人们可以在一些重点和技术水平不同的会议上找到相关的最新材料。仅举国际密码学研究协会（IACR）日历上的几个会议，就有后量子密码、真实世界密码、公钥密码以及密码硬件和嵌入式系统。
迫不及待：以最小的成本和时间过渡到PQC
2021年，超过一半的受访专家认为，LFT量子计算机在15年内打破整数分解和基于离散对数的密码的概率大于50%，因此几乎没有时间过渡到PQC。特别是由于SNDL攻击，即使今天的私人数据也可能被明天的量子计算机所破坏，而且现在正在部署的密码硬件预计将在该领域保持数十年。
由于方案的多样性，在攻击成功的情况下需要立即从一种算法切换到另一种算法，以及对系统之间连接性的要求越来越高，在设计新的协议时必须考虑到加密的灵活性。
关于过渡的工作不必等待NIST的全面支持，因为混合密码学允许从业者在不影响当前安全水平的情况下安全地部署后量子方案。美国政府在2022年初发布了一份关于过渡到抗量子密码协议的备忘录，为全球公共和私人组织树立了一个强有力的榜样，表明应尽快开始过渡的准备工作。各组织现在可以采取的减轻量子计算威胁的措施包括：建立一个加密目录，列出所有公钥加密技术在其基础设施和产品中的存在；一旦标准发布，就制定一个过渡路线图；试验不同系列的PQC算法，以测量性能并研究不同的方法（例如混合），评估相互依赖性等；并确保系统是加密敏捷的。也就是说，准备以最小的成本和时间过渡到PQC。
这些任务都不是小事，而且都可以从现在开始，帮助组织、系统和用户负责任地努力实现更安全的未来。
综述原文：
https://www.nature.com/articles/s41586-022-04623-2