《后量子密码报告》摘编：NIST的初步计划

后量子密码报告

（Reporton Post-Quantum Cryptography）

作者：LilyChen、StephenJordan、Yi-KaiLiu、DustinMoody、

RenePeralta、RayPerlner、DanielSmith-Tone

翻译：郑凯燕

校审：王鹏

目录

摘要.. 3

1.介绍.. 4

2.抗量子密码概述.. 5

3.量子计算硬件的进展.. 6

4.前进的方向.. 6

参考文献.. 8

摘要

近些年，出现了一大批量子计算机的研究。量子计算机利用量子力学原理解决传统计算机难以或者无法解决的数学问题。如果大规模量子计算机建成，可以用于破解许多目前正在使用的公钥密码系统，这将严重危及互联网等场合中数字通信的机密性和完整性。后量子密码（或者称为抗量子密码）的目标是发展对量子或者经典计算机都安全的密码系统，并且能够和已有的通信协议和网络进行互操作。这份内部报告分享了NIST（National Institute of Standardsand Technology）目前对于量子计算和后量子密码状况的理解，描述了NIST迈向这一领域的初步计划。本报告同时意识到转移到新密码基础设施是一项挑战，因此强调关注密码敏捷性是有必要的。

关键词：后量子密码、公钥密码、量子计算、抗量子、量子安全

1.介绍

近三十年来，公钥密码体制已经成为我们全球化通信数字基础设施的一个不可或缺的组成部分。这些网络支撑了对经济、安全、生活方式都十分重要的大量的应用程序，如手机、互联网商务、社交网络和云计算等。在这样一个互连的世界中，个人、企业和政府的安全通信能力是最重要的。

许多至关重要的通信协议主要依靠三大核心密码模块：公钥加密、数字签名和密钥交换。目前，这些模块主要是利用Diffie-Hellman密钥交换协议、RSA（Rivest-Shamir-Adleman）密码体制和椭圆曲线密码体制来实现的。这些模块的安全性取决于一些理论难题的困难程度，如整数分解、在不同群上的离散对数问题。

在1994年，贝尔实验室的Peter Shor展示了量子计算机可以高效地解决上述所有的难题，这种利用物质和能量的物理性质进行计算的新技术使得所有公钥密码体系的假设不再成立[1]。因此，一个足够强大的量子计算机将使许多现代通信方式处于危险之中，包括从加密过程的密钥交换阶段到数字认证阶段。

在解决一些难题时量子计算机比传统计算机更快的这一发现激发了人们对量子计算的极大兴趣。量子复杂性和传统的复杂性是否有本质区别？大规模量子计算机何时能够建成？是否存在一种方法能够同时抵抗量子的和传统的计算敌手？研究人员正在研究这些问题。

自Shor的发现后，近二十年里量子算法理论有了极大发展。在与物理模拟、数论和拓扑结构相关的一些问题上发现了能够实现指数级提速的量子算法。然而这类通过量子计算实现指数级提速计算的难题相对较少。相比之下，在搜索问题、查找碰撞和布尔公式的评价的相关多类问题上有更多适度的提速计算的量子算法。特别是，Grover搜索算法在非结构化的搜索问题上提供了平方的提速计算。虽然这样的提速效果不会导致加密技术被淘汰，但其威胁使得密码技术需要采用更大的密钥，包括对称密钥体系。表1给出了大型量子计算机对常见的密码算法的影响，如RSA算法和高级加密标准（AES）。这些量子优势可以继续被推进多远，在传统模型和量子模型的可行性之间存在多大的差距，这些问题都悬而未决。

何时能够建立一个大型的量子计算机是一个复杂且有争议的问题。虽然在过去不太清楚大型量子计算机在物理上是否可能，现在许多科学家认为它只是一项重大的工程挑战。一些专家甚至预测，在未来的20年左右，可以建立足够大型的量子计算机，以从根本上破解所有目前在用的公钥密码方案[2]。部署现代公钥加密基础设施花了近20年的时间，要实现从目前广泛使用的密码系统到抗量子计算的相应体系的平滑和安全迁移需要相当多的努力。因此，不论我们对量子计算时代到来的时间估计是否精确，我们现在必须开始着手，让我们的信息安全系统能够抵抗量子计算。

表1量子计算对常见的密码算法的影响

国际上已经出现了一个大规模的研究团体，旨在解决未来量子计算下的信息安全问题，希望在采用新的抗量子模块后，我们的公钥密码基础设施不受影响。在学术界，这一新的科学命名为“后量子密码。”这是一个活跃的研究领域，拥有自己的系列会议，即2006年开始的pqcrypto会议。各国资助机构对后量子密码投入了大量的支持，特别是在欧洲和日本，分别有欧洲联盟（欧盟）项目pqcrypto和safecrypto，日本的CREST密码数学项目。

这些努力在基础研究方面取得了进展，为在现实世界中后量子密码的部署做好铺垫。在过去的几年中，行业标准组织已经开始了自己在这一领域的活动：自2013年以来，欧洲电信标准协会（ETSI）组织了三个“量子安全密码”研讨会；在2015年NIST举行题为“后量子世界的网络安全”研讨会，有来自政府、行业和学术界的超过140人参加。

NIST已经在规范后量子密码学中发挥着独特的作用，其肩负开发非国家安全的联邦信息系统的标准和指南的责任。许多NIST标准，如高级加密标准（AES），都是在学术界和工业界的共同参与下制定的，这些标准作为有效的解决方案而得到广泛应用，有助于保护美国的信息和信息系统。NIST对后量子密码的标准化工作将提供类似的益处。

考虑到各因素，很明显地，抗量子技术的发展正在不断加强。同样清楚的是，这些投资暗示了规范新的后量子公钥密码体制的需求十分紧迫。和NIST密码标准社团合作制定出世界各地工业和其他标准组织认可的标准至关重要。这份互联网报告分享了NIST当前对量子计算的角色、后量子密码学的理解，并概述了其初步的发展计划。

2.抗量子密码概述

当前公钥密码最重要的用途是数字签名和密钥建立。在第1节中提到的，建立一个大型的量子计算机将使许多公钥密码体制变得不安全。这里尤其包括了基于整数分解困难（如RSA算法）以及基于离散对数问题的困难的密码系统。相比之下，对称密钥系统受到的影响显得不激烈（见表1）。与传统计算机的搜索算法相比，Grover算法在量子搜索算法上有二次方的提速。我们不确定Grover算法是否有实际意义，若有，则将密钥规模增大一倍即可保证安全。此外，指数级提速的搜索算法已经被证明不可能存在，故在量子时代对称密码算法和散列函数仍然是可用的[3]。

因此，研究能够同时抵抗传统计算机和量子计算机攻击的算法集中在公钥密码体系上。在这一节中，我们简要地介绍后量子目标所提出的主要分类。这些分类包括了那些基于格、代码和多变量多项式，以及少量其他的。更进一步的信息可参考[4,5 ]。

基于格的密码——因为某些原因，基于格的密码系统重新引起了人们的兴趣。一些振奋人心的新应用（如全同态加密，代码混淆，和基于属性的加密）已经通过基于格的密码学得到实现。大多数基于格的密钥生成算法相当简单、高效且高度可并行。同时，一些基于格的系统的安全在最坏情况的困难假设下是可证明安全的，而不是在平均情况下。另一方面，对格方案的安全进行精确估计已经被证明是困难的，即便使用已知的密码分析技术。

基于编码的密码——McEliece密码系统自1978年提出后一直未被破解。自那时起，基于纠错码的其他系统陆续被提出了。而很快的，大多数基于代码的模块具有密钥规模太大的缺点。更新的改进方案尝试引入更多的结构到代码中以减少密钥规模，但是增加的结构也导致了一些方案存在成功的攻击。虽然有一些基于代码的签名方案提出，基于代码的密码学在加密方案的应用更成功。

多变量多项式的密码——这些方案是基于有限域上的多变量多项式系统的求解的困难性。在近几十年里，一些多变量密码系统被提出，但很多已被破解[6]。虽然有很多多变量加密方案被提出，多变量多项式密码学在签名方面的应用更成功。

基于散列的签名——基于散列的签名是使用散列函数构造的数字签名方案。这些方案的安全，包括量子攻击，是很容易分析。许多高效的基于散列的签名方案的一个缺点是签名者必须记录已签署消息的精确数目，因为这个数目的任何错误都会导致不安全。另一个缺点是，这些方案只能产生有限数量的签名。虽然签名的数量可以增加，甚至是达到有效的无限制的程度，则签名的大小也必须变大。

其它——除上述类别，各类系统被相继提出。其中一个方案是基于评估超奇异椭圆曲线同源的。在椭圆曲线上的离散对数问题可以在量子计算机用Shor算法有效地计算，奇异曲线同源问题不存在相似的量子攻击。而其他一些方案，例如那些基于共轭搜索问题和辫(子)群相关问题的方案，尚未有足够的分析能够说明其安全性。

用这些已知的算法替代目前正在使用的算法，这似乎是不可能的。一个可能需要克服的挑战是，大多数的抗量子的密码算法相比要替代的算法具有更大的密钥规模。这可能会导致各网络协议的改动，比如传输层安全（TLS）协议，或Internet密钥交换（IKE）。如何进行替换需要仔细的考量。

我们注意到上述方案中没有一个能保证能抵抗所有的量子攻击。一种能破解这些方案的新量子算法可能随时被发现。然而这是类似于今天的状态。虽然大多数公钥密码体制有安全证据，这些证据都是基于未被证明的假设。因此，缺乏已知攻击可用来证明目前在用的公钥密码体制的安全性。然而，NIST认为上述提出的后量子算法需要更多的研究和分析才能被推荐使用。这些算法还没有从密码学界得到到和当前已采用算法几乎一样多的审查。一个例外是基于散列的签名，其安全性是很好的理解。对于某些特定的应用场景，如数字代码签名，基于散列的签名极有可能在未来几年内标准化。

3.量子计算硬件的进展

自1994年Peter Shor发现了一个多项式时间内解决整数分解的量子算法后，建设大型量子计算机的可行性研究正式开始[1]。在当时，量子计算能否发展成一个基础的可扩展的技术还不清楚。许多前沿专家认为，量子状态太脆弱，并存在大规模的量子计算的错误的积累，量子计算难以实现。在20世纪90年代末，随着量子纠错码和阈值定理的发展[7]，这种情况发生了变化。这些阈值定理表明，在一个量子计算机中，如果每一个逻辑操作（“量子门”）的错误率能够被降低到一个固定的阈值，则任意长的量子计算能够以一个可靠的和容错的方式进行，通过在整个量子计算的执行过程包含错误校正步骤[8]。

多年来，物理学家已经逐渐发展和改善了硬件，使得每量子门错误率更低。同时，理论家们已经开发出新的量子纠错程序以获得更高的容错阈值。最近，一些使用了离子阱和超导电路的实验显示了量子门的普遍集名义上是低于最高理论容错阈值（约1%）[9,10]。这是一个重要的里程碑，这刺激了政府和行业的投资增加。然而很明显地，从现在的涉及几个量子比特的实验室演示到大规模量子计算机的发展需要大量长期的努力，后者涉及了成千上万的逻辑量子比特编码成几十万或几百万的物理量子比特。

与通用数字量子计算机的并行发展的是专用模拟量子计算机，如量子退火设备（如d波机），类量子模拟器，和玻色子取样装置。其中一些设备所达到的量子比特规模远远大于数字量子计算机。然而，由于其专用性质，这些模拟量子设备不能被认为是密码分析相关的。

4.前进的方向

对更强大的密码的需要被传统和量子计算技术的进步驱动着。为了抵抗各传统的攻击并维护安全，NIST已经建议将提供80比特安全的密钥规模和算法提供为提供112或128比特安全的密钥规模和算法[SP 800-131a]。而为了抵抗量子攻击，NIST将促进更为困难的转变，以实现新的后量子密码系统。

目前还不清楚可扩展的量子计算机何时可用。然而，在过去的几年中，致力于建立一个量子计算机研究人员估计，大概在2030年可以建立一台能够在几个小时内破解2000比特RSA的量子计算机，其预算约十亿美元[11]。这对NIST目前标准化的密码系统是一个严重的长期威胁。

比较上述预测与使用传统计算机破解这些密码系统的成本是有意义的。早在2011-2013年被淘汰的仅提供80比特安全或更少的密码系统正处于最大的风险之中：它们现在的破解成本是在几万到几百万美元之间[12,13,14,15]。而提供112比特安全的密码系统还可能维持安全一段时间：它们在30到40年内被破解的预算约为十亿美元（采用传统计算机）。

因此，从112到128（或更高）比特安全的转变比从现有密码体制到后量子密码的过渡也许没有那么紧迫。这个后量子密码的转变出现了许多根本性的挑战。

以前的过渡从弱到强的密码是基于比特级安全，也即衡量一个算法的安全是基于传统计算机进行攻击的时间复杂度（例如若用传统计算机攻击一个算法的难度跟暴力穷搜一个128比特密钥的时间和资源相当，则称其能达到128比特安全。）NIST特别出版物（SP）800-57第一部分[sp800-57]将NIST截至2016年1月标准化的算法分成80，112，128，192和256比特安全。它进一步建议了80比特安全级别被认为不再足够安全，且112比特安全级别将在2031年被淘汰。

不幸的是，这种比特安全的衡量没有考虑到量子密码分析，因而这些建议无法指导向抗量子密码体制的过渡工作。关于在抵抗量子攻击并得到可接受的安全级别时所需的密钥长度，目前还没有达成任何共识。在对称密钥方面，一个简单的启发式方法就是将密钥长度增加一倍以补偿Grover算法取得的平方提速。但这一建议可能过于保守，因为量子计算的硬件可能会比传统的硬件更昂贵。与此同时，这一建议并没有考虑到更复杂的量子攻击[16,17,18]。我们对量子密码分析的理解仍然是相当有限的，在这方面的研究更加迫切需要的。

后量子密码标准的制定将需要大量资源来分析各候选的抗量子方案，并将需要大量的公众参与来保证NIST选择规范化算法具有公众信任。由于在量子计算硬件方面具有里程碑意义的发展和美国国家安全局（NSA）在其套件B指导文件[19]的变动，在量子计算和抗量子密码学领域的研究兴趣最近得到增加。这提供了一个和研究社团参与研究的机会，这次机会在实际量子计算到来前仅此一次，且真正迫在眉睫。因此，NIST现在开始做好向抗量子密码学过渡的准备。

NIST正在采取以下步骤来启动后量子密码学的标准化工作。NIST计划指定抗量子公钥密码标准的初步评价指标。该指标将包括安全性和性能要求。其草案指标将在2016年发布以征求公众意见，期望在其年底完成。在那时NIST将开始接受抗量子公钥加密方案、数字签名和密钥交换算法的提案。在实现这些功能的每类方案中NIST将至少选择一个算法进行标准化。NIST将对所要考虑的算法确定一个2017年底的提交截止日期，并保定这些提案在标准前经过3到5年的公众审查。

虽然这个过程和AES[20]和SHA3[21]的标准过程有许多共同之处，但是这并不是一场竞赛。NIST的角色是透明、及时地管理这一过程，达到大众的共识。在理想情况下，有几种算法将成为“好选择”。NIST会在每个类别中选择一个或多个算法进行标准化。在这方面，NIST规范抗量子公钥密码的过程将类似于正在进行的分组密码模式发展过程[22]。

在抗量子公钥密码体制的标准可用之前，NIST将重新评估量子计算机对现有的标准造成危害的急迫程度，并做出反对或撤销这些受影响的标准的决定。因此，从现在开始10年内，各机构应准备抛弃这些算法的过渡工作。由于目前标准的公钥算法的替代算法都还没有准备好，保持密码的敏捷性是势在必行。在新的抗量子算法完成标准化之前，各机构应继续使用目前NIST标准中规定的推荐算法。

参考文献

【略】

声明：本文来自密码学报，版权归作者所有。文章内容仅代表作者独立观点，不代表安全内参立场，转载目的在于传递更多信息。如有侵权，请联系 anquanneican@163.com。