在量子计算机到来之前，请准备好抗量子破解的密码学

　　如果量子计算在未来取得突破性进展，一直守护着互联网的安全系统将变得岌岌可危。世界从此会变成怎样？第一个研发出实用量子计算机的政府或机构将会得到整个世界的秘密吗？事情并没有想象中那么糟糕。事实上，即便有了量子计算机，许多经典的保密算法仍将是有效的，更何况量子保密技术也在蓬勃发展。不过，由于密码系统更迭需要很长的时间，所以尽管看上去为时尚早，美国国家标准与技术局（NIST）却已经从学术界和工业界征集研究人员，希望在2022年之前准备好抗量子破解的密码学（quantum-resistant cryptography）。

　　撰文 | Jeremy Hsu

　　翻译 | 无邪（量子计算领域研究人员）

　　当实用的量子计算机最终来临的时候，它将能够破解一直在为我们的在线隐私、政府安全、公司安全以及几乎所有互联网使用者的个人安全保驾护航的标准数字密码。这就是为什么美国政府机关开始鼓励研究人员去开发新一代抗量子破解的密码学算法。

　　虽然许多专家并不认为量子计算机能够在未来十年内具备破解现代标准密码术所需要的复杂计算能力，但是，美国国家标准与技术局（NIST）希望走在前面，让新的密码标准在2022年之前准备好。这一机构正在审查其“后量子密码学标准化程序”的第二阶段，以缩小抗量子破解并能够替代现代密码学的最佳候选加密算法的范围。

　　“当前，那些保护广泛采用的加密系统，如RAS和基于椭圆曲线的密码方案等的难解计算问题有可能变得可解。这意味着量子计算机有可能最终会够破坏这个星球上最安全的通信系统，”英特尔公司的密码学专家 Rafael Misoczki说道，他同时也是参与上述NIST计划的两个小组（分别叫Bike和Classic McEliece）的成员之一。

　　Misoczki参加了8月22日至25日在加州大学圣巴巴拉分校举行的第二次PQC（后量子密码学）标准化会议，该会议有超过250人注册参加，几乎所有致力于26种候选算法研究的团队都做了报告。这些算法则是从第一轮的69个算法中筛选出来的。

　　NIST希望这些第二轮候选算法能够跨越单纯的原理验证的阶段，并开始进入基准测试。如果量子计算方面的突破性进展能够威胁到数千亿美元的电子商务——这还不包括数万亿美元更为广泛的数字经济领域，那么这么做就是非常值得的。不过，很多研究者警告，NIST在确定最终的后量子密码学算法清单之前，应该花一些时间去评估新的候选算法类型。

　　Misoczki解释说，NIST的计划主要考虑两大类的算法，第一类包括密钥建立算法，这类算法可以确保从未碰面的通信双方能够对共享的保密信息达成一致。这一类同时也包含公钥加密算法——比如RSA和椭圆曲线加密术，它们可以做同样的事情，但不是那么有效。

　　第二类包含数字签名算法，用于确保数据的真实可靠性。这种数字签名在代码签署等应用中非常重要，如此一来就可以确信一个程序是由预期的开发者开发的，而不是一个黑客。

　　这两大类都要求新的算法是基于即便量子计算机也无法解决的数学问题的。目前有几种正在考虑中的后量子密码学算法发展途径，每种都各有优缺点。举例来说，“基于编码的密码（code-based cryptography）偏爱长的公开审核历史，而基于网格的密码（lattice-based cryptography）可以提供非常快速的算法，”Misoczki说道。

　　这是一个计算问题的集合关系图。量子计算机能够解决一部分 NP 问题，但仍然无法解决 NP-完全（NP-complete）问题，这给了后量子密码学足够的机会。

　　每种方法的折中处理会对现实世界中的计算机应用和设备产生显著影响。基于网格的密码学甚至比现代加密技术如RSA更快，但它的数据量更大，因此如果带宽有限的情况下它的应用就会变得不一样。

　　位于瑞士IBM苏黎世研究室的密码学专家Vadim Lyubashevsky也参与了NIST的标准化计划。他说，这就是为什么NIST要从几个不同的途径来做算法标准化。“即便我们可以保证它们都是安全的，也不可能有哪种算法在所有场景都是最佳的。”

　　荷兰Radboud大学的计算机安全专家Peter Schwabe说，对这些很可能部分取代全球通信安全基础架构的候选算法，我们仍知之甚少。每种算法在面临各种可能攻击下的真实安全性仍有待更多的研究和测试，此外还需要权衡其安全-性能比，发展可靠的算法实施技术，并找出那些一旦算法实施之后会发生故障的事情。

　　Schwabe 还说：“我们现在看起来很清楚的是，与我们今天采用的方案相比，这些新的方案在性能特征上有极大的不同，并且很多在安全性上有细微差别。”

　　合作精神 vs.竞争机制

　　NIST的挑战已经将学术界专注于理论研究的学者和工业界熟悉现实世界性能需求和安全要求的技术专家聚集在一起。这个机构最开始将计划描述成“竞赛型过程”，不过看起来他们更希望鼓励参与者们互相合作。

　　一些研究者加入了多个研究不同算法的小组，比如，Lyubashevsky 是致力于CRYSTAL-KYBER、CRYSTALS-DILITHIUM和Falcon等多种算法研究的小组成员。Schwabe 则同属于七个研究各不相同的算法的小组：CRYSTALS-KYBER、CRYSTALS-DILITHIUM、Classic McEliece、NewHope、SPHINCS+、NTRU以及MQDSS。

　　各团队在一个统一的邮件列表中开放共享框架和反馈——这是一个既有优点又有弊端的办法。一位匿名的参与者在NIST的调查问卷中回应道：“某些声音和时不时的直接人身攻击充斥着邮件列表，导致其他人不愿意对这些人的工作或问题提供帮助。”

　　Misoczki 则说，大部分社区成员看起来还是很乐于一起工作的。他看到了“更多的合作氛围而不是竞争环境”，尽管有些不同的观点。

　　Schwabe 也描述了社区的合作精神，但提到某些个人似乎有更强的竞争倾向。他在一封邮件中写道：“很不幸，有些参与者并不是那么愿意合作，他们致力于推动他们自己的（通常是申请了专利的）方案，而不是像社区那样为找到可标准化并应用于未来的最佳方案而奋斗。”

　　某些竞争算法其实是从同一个加密方法派生出来的，差别并不大。Lyubashevsky 建议NIST保持参与者专注于共性标准化目标，对候选算法提出想要的加密特性指标。他说：“最好跟大家说‘看，忘掉与这些事有关的人名，这是我们想要的指标’。”

　　图片来源：Natasha Hanacek/NIST

　　新的后量子密码学标准

　　NIST计划于2022年左右起草后量子密码学标准。但学者们已经敦促其避免急迫处理对所有候选算法的审查。他们的匿名反馈来自于一份NIST调查问卷，这份问卷在八月份第二次PQC标准化会议结束时被公开出来。

　　一位调查对象写道：“NIST不应该将结束计划并于2022年前完成标准作为目标。这有点太急于得到正确的答案了... ...我们还需要更多的研究。”

　　另一位调查对象提出，NIST应该在2025年之前延迟推出任何标准，并在此之前资助所有候选算法的研究工作，以“给研究者创新的机会。”

　　一位调查对象描述了一幅急于推进的可能后果的悲观景象：“试图在短短几年内就终止计划是危险的，这将导致灾难性的后果，甚或丧失这一计划及其成果的合法性。”

　　很多人指出，对每种算法可能的弱点进行彻底研究需要更多的密码分析。有人敦促NIST更多地资助美国大学进行学术研究，以进一步发展“量子密码分析学”。

　　Lyubashevsky 说：“密码学的一个共性问题是，密码分析是一个毫无回报的过程。不管你失败了，没人知道你尝试过并失败了，或是你成功了，并且赢得了五分钟的名声，总归你写的算法再没人去用。”

　　NIST可能部分考虑过不同小组会试图相互破解对方算法的想法。但是Lyubashevsky 建议NIST也应该要求研究者们检查其他团队的工作，或者将密码分析作为算法开发理论研究获得资助的条件之一。

　　计算机什么时候可以破解密码？

　　没人知道什么时候量子计算会使得现代密码学算法变得没用。一个附带的后果可能是，第一个研发出实用量子计算机的政府或机构只要“静悄悄”地破解现代密码系统并爬取全球的秘密，就可以获得极大的增益。

　　“很大的可能性是，第一个大型通用量子计算机只能是那些不会明确声张他们有如此计算能力的政府机关所拥有，”Schwabe说。他认为“在20年之内，可以破解我们当今广泛使用的密码的量子计算机很有可能产生。”

　　密码学研究者们确知的是，要让全世界的政府和工业界采用最新的密码学标准需要很长的时间。举例来说，尽管椭圆曲线密码在上世纪80年代末就首次提出，但全球大部分地方仍在使用上世纪70年代末出现的更老的RAS密码。这就是为什么哪怕实用量子计算机仍然有几十年之遥，NIST 已经开始在后量子密码学标准化方面作出努力背后的紧迫性所在。

　　Misoczki说：“预测大规模量子计算机会在什么时候出现是一个很难的问题，而另一方面，加密社区的人知道，加密算法的过渡需要几年甚至几十年。”

　　所幸的是，那些拥有极度敏感数据的机构不需要等待NIST的标准化过程实施，相反，他们可以提前采用NIST计划中的部分已公开发表的免费候选算法来保护他们的系统与时俱进。

　　Lyubashevsky说：“如果你真的有敏感数据，那别迟疑，现在就迁移。如果没有，那么我觉得再等五年为好，让这些算法在竞争中自生自灭，最终产生一个大多数人喜闻乐见的好标准。”

　　对那些愿意等待的人，Lyubashevsky表示他有信心NIST聚拢的密码学家们会在量子计算机出现之前做好准备。他说：“在量子计算机出现之前，我们必定已经有了后量子密码学。我想如果我们在接下来五年里真的准备好了后量子密码学，那么几乎所有的应用都将有充分的时间做准备。”

　　本文翻译自 spectrum.ieee.org，原文标题为“How the United States Is Developing Post-Quantum Cryptography”。

　　本文为严肃科普媒体《返朴》（微信号：fanpu2019）首发，《返朴》由国际一流科学家和科普专家担任总编及编委。任何媒体转载时须保留《返朴》名称及微信号和作者信息。未经许可，严禁对包括标题在内的任何改动。转载、授权、合作请联系fanpusci@163.com。