Cryptographers Discover a New Foundation for Quantum Secrecy
20:09 Share

欢迎收听Quanta科学播客。每一期，我们都会为您带来关于科学和数学发展的故事。我是苏珊·瓦莱特。研究人员已经证明，即使在没有难题的世界里，安全的量子加密也是可能的。接下来就是这个话题。

这是《为什么的快乐》的第三季，我仍然有很多疑问。比如，我们所说的时间是什么？利他主义为什么存在？十一月在哪里？我在这里，我是天体物理学家兼联合主持人，随时准备应对任何事情。没错，我带来了A组。所以请做好准备。准备好学习吧。我是十一月。我是史蒂夫·斯特罗加茨。这是……量子杂志的播客，《为什么的快乐》。每隔周四都会发布新剧集。

假设您想发送私人消息、进行秘密投票或安全地签署文件。如果您在计算机上执行任何这些任务，那么您都依赖于加密来保护您的数据安全。

这种加密需要能够抵御使用他们自己计算机的密码破译者的攻击。这就是为什么现代加密方法依赖于关于哪些数学问题对于计算机难以解决的假设。但是，当密码学家在20世纪80年代为这种信息安全方法奠定数学基础时，一些研究人员发现，计算难度并不是保护秘密的唯一方法。量子理论家

系统理论最初是为了理解原子的物理学而发展起来的，但它也与信息和密码学有着深厚的联系。研究人员找到了直接基于物理定律来保证一些特定密码学任务安全性的方法。然而，这些任务是奇怪的异常值。对于所有其他任务，似乎没有替代经典计算方法的方案。

到千禧年末，量子密码学研究人员认为这就是故事的结局。但就在过去的几年里，该领域经历了另一次剧变。亨利·袁是哥伦比亚大学的量子信息理论家。有些事情就像我所说的低技术含量的东西，一直到真正的高技术含量的东西。多年来，人们已经逐渐建立了一些理解，认为这些东西实际上是彼此分离的。例如，如果我给你一个低技术含量的东西，你不能普遍获得高技术含量的东西。

现在我们从量子的角度来看待事物，我们说，如果你允许密码协议中的各方相互传输量子比特，那么低技术含量和高技术含量的东西之间是什么关系？看起来情况大不一样了。我们认为是高科技的东西实际上是相当低科技的。这是一件好事。这意味着您可以对它们的安全性更有信心。

因此，我们对量子密码学可能实现的事情有了重新安排。在一系列最近的论文中，研究人员已经表明，即使在假设所有计算都很容易的世界中，大多数密码学任务仍然可以安全地完成。所有重要的只是关于量子理论本身的一个特殊计算问题的难度。

费米·马是加州伯克利市西蒙斯计算理论研究所的量子密码学家。最令人兴奋的是，您需要的假设可以非常非常弱。因为归根结底，一切都是建立在假设之上的。我认为，即使在量子世界中，密码学仍然是关于结合假设、结合计算难度和量子信息以及用它做一些有趣的事情。让我如此兴奋的是，

实际上尝试这样做就像给了我们对计算难度本身的新见解。故事始于20世纪60年代末，当时一位名叫斯蒂芬·维斯纳的物理学研究生开始思考量子理论中测量的破坏性本质。测量任何受量子物理学规则支配的系统，你都会改变数学上描述其构型的量子态。这种量子测量扰动对于大多数物理学家来说都是一种障碍。

维斯纳对量子理论采取了一种非正统的、以信息为中心的观点。他想知道它是否可以派上用场。也许它可以作为敏感数据的内置防篡改保护形式。但维斯纳的想法过于超前，他在研究生毕业后离开了学术界。幸运的是，他与他的朋友兼物理学家查尔斯·贝内特讨论了他的想法，贝内特十年来一直试图让其他人对这个主题感兴趣，但没有成功。

最后，在1979年，贝内特在一次会议期间在波多黎各海岸游泳时遇到了计算机科学家吉尔·布劳萨德。他们一起撰写了一篇具有开创性的论文，描述了一种解决重要密码学任务的新方法。他们的协议基于量子测量扰动，不需要对任何计算问题的难度做出任何假设。这是马的说法。在80年代，当人们第一次开始了解量子信息是如何工作的时候……

我们意识到的一件事是，量子信息的本质似乎在某种程度上是密码学的。

例如，你不能克隆量子态。有些东西在那里，就像量子性的一些东西一样，它就像大自然在保护信息一样。贝内特和布拉扎德的突破使研究人员乐观地认为，类似的量子技巧可以为其他密码学任务提供完美的安全性。研究人员主要关注一项名为比特承诺的任务，这项任务本身很有用，也是大多数高级密码协议的关键组成部分。

为了理解比特承诺背后的基本思想，袁说，想象一下一个两人游戏，在这个游戏中，你必须做出一个稍后会被揭示的秘密决定。所以比特承诺的想法是，它就像把信息放在一个密封的信封里，他们不能立即阅读的密码等价物。

然后在某个指定的时刻，你说，好吧，我们可以打开信封，并验证我是否已经提交了投标或投票。比特承诺方案就是这样的一种密码等价物。它对投票协议、多方计算甚至区块链都非常有用。

因此，首先，当您将信封交给接收者时，您不希望他们能够阅读信封中的内容。从数字角度来说，就像您给他们一些信息一样，它应该以某种方式对他们进行加密。这就是其中的一部分。然后，安全性的第二部分是，在第二阶段的稍后时间，当我们都同意揭示信封中的内容时，我不应该能够改变主意。现在想象一下您正在网上玩同样的游戏。

为了使作弊成为不可能，您需要将决定密封在一个双方都不能单独打开的数字信封中。这就是密码学发挥作用的地方。1981年，开创性的计算机科学家曼努埃尔·布鲁姆构建了第一个比特承诺协议，一种方法是用困难的计算问题构建有效不可破解的信封。

但是，困难有多困难？计算复杂性理论领域的研宄人员研究了许多不同类型的难题，并非所有这些难题都对密码学家有用。比特承诺和所有其他密码协议都依赖于复杂性理论家称为NP的一类问题。NP的定义特征是，很容易检查候选解决方案是否正确。

不幸的是，研究人员无法证明任何NP问题都是真正困难的。仍然可能存在一些巧妙的未被发现的程序或算法来解决即使是最难的问题。如果存在，那么所有经典密码学都将被破解。

这些考虑促使人们寻找基于量子的安全保证。但1997年，两篇论文证明，如果比特承诺方案仅仅基于量子物理定律，那么它们就永远不可能完全安全。这些论文暗示，几乎所有密码学任务都需要某种计算难度。

在近25年的时间里，这是关于量子比特承诺理论基础的最后一句话。然后，在2021年，一篇由研究生威廉·克雷奇默撰写的论文促使研究人员面对一个没有人想过要问的问题。计算难度对于比特承诺和大多数其他形式的密码学显然是必要的。但究竟是什么样的难度？

答案将比任何人预料的都要奇怪。2021年的论文来自于克雷奇默努力理解一个听起来在概念上很简单的问题的特定版本。区分或辨别两个看起来表面上相似的量子态有多难？

克雷奇默现在是西蒙斯研究所的博士后研究员，他最初出于与比特承诺无关的原因而对这个问题感兴趣。那时，他的密码学甚至不在他的雷达上。区分问题之所以有趣，部分原因在于，甚至不清楚如何使用熟悉的数学语言来描述它。

复杂性理论家传统上研究具有不同可能输入的问题，这些输入由比特串或零和一表示。例如，对于将大数分解为其素数因子的问题，此字符串表示要分解的数。

即使在研究人员开始研究如何利用量子物理进行计算之后，他们仍然专注于这种经典的输入问题。典型的量子算法从普通的经典比特串开始，然后使用量子技巧对其进行处理。但在像克雷奇默这样的量子输入问题中，输入不是比特串。它们是量子态，很容易被计算和测量所破坏。

这是伊万。不知何故，我们使用的语言

在传统的复杂性理论中描述量子计算无法直接讨论人们感兴趣的这些问题。起初，克雷奇默认为他可能需要将问题翻译成更标准的语言，但他不知道如何去做。我认为，你知道，我只是不够聪明。可能有一种更巧妙的方法可以将它简化为一些简单的东西。最终，我意识到你做不到。所以他做了复杂性理论家在绝望时经常做的事情。他求助于预言机。

在复杂性理论中，“预言机”一词指的是一种假设的设备，它可以立即解决特定问题。拥有访问预言机的计算机可能能够通过将预言机作为算法中的中间步骤来更容易地解决其他问题。当然，预言机在现实世界中并不存在，但研究它们有助于复杂性理论家理解不同问题难度级别之间的关系。

克雷奇默想知道什么样的预言机可以很容易地区分两种量子态，即所谓的态区分问题。他决定从一个特殊的预言机开始，这个预言机将增强普通量子算法的能力，这些算法使用量子技巧来解决具有经典比特串输入的问题。

这种算法可以解决一些对于经典算法来说过于困难的问题，例如分解大数。但它们并非万能的。许多其他问题超出了它们的范围。

访问克雷奇默的预言机将使这种算法能够解决某些对于真正的量子计算机来说过于困难的经典输入问题。克雷奇默认为这将是杀鸡用牛刀，但令他惊讶的是，他证明了态区分问题仍然可以难倒这些经过改进的量子算法。罗文建是波士顿大学的一名研究生，研究密码学。威廉的论文让我着迷。

我实际上认为它一定是错的。这太违反直觉了。钱、袁和其他人证明，如果克雷奇默的态区分问题确实是困难的，那么安全的量子比特承诺方案将是可能的。这反过来又意味着可以保证一系列更高级的密码协议的安全。

量子密码学的范围远远超出了20世纪90年代研究人员所意识到的范围，这一切都归结于一个问题的难度。克雷奇默的结果有一个很大的警告。为了使证明有效，他必须依赖于一个只有量子算法才能咨询的异常预言机。

也许一个更熟悉的预言机会使他的态区分问题变得容易，从而使安全的量子比特承诺成为不可能？这是春天的说法。在现实世界中，我们如何真正获得这种神奇的产品？我们如何真正实现这些量子密码学对象，而不是说，首先获得一个神奇的按钮？

在这篇量子密码学论文中，我们使用随机预言机，这实际上为您提供了一种方法，一种潜在的方法，一种更具体、更易于理解的方法来实际实现这些量子密码学对象，而不是说，首先获得一个神奇的按钮。

2022年，克雷奇默和肖恩开始合作，看看他们能证明关于每个人都能理解的预言机什么，一个可以立即解决任何NP问题的预言机。在一个拥有这种预言机的世界里，所有经典密码学都将是不可能的。这是克雷奇默的说法。我会说这只是一个研究较少的模型。例如，随机经典预言机是一个人们已经研究了几十年的假设，也许是40年左右。

我认为我们对这些东西何时安全有相当好的理解。对于这个量子预言机，是的，你知道，这个量子随机预言机在某种意义上看起来很自然，但它不是人们研究了四年的东西。它不是人们研究了四年的东西。我的意思是，我认为人们对它知之甚少。克雷奇默很快意识到，态区分问题与量子复杂性理论中一个表面上不同的问题在数学上是相关的。所以

所以我们请来了该领域的两位专家，复杂性理论家阿维沙伊·塔尔和马克兰·辛哈。

塔尔记得那段时间。“威廉真的像个经理，我们就像承包商。我们想，好吧。在我向他提出一些想法后，他告诉我了全局。”通过合作，这四位研究人员很快证明，即使对于可以调用这个NP预言机的计算机来说，克雷奇默的态区分问题仍然可能是棘手的。那

这意味着，即使支持经典密码学的每个问题都被证明很容易，几乎所有量子密码学都可以保持安全。经典密码学和量子密码学越来越像两个完全不同的世界。

这个结果引起了马的注意，他开始想知道他能把克雷奇默发起的这项工作推到多远。即使有更奇特的预言机，那些可以立即解决比NP中更难的计算问题的预言机，量子密码学是否仍然可以保持安全？

达克希塔·库拉纳是伊利诺伊大学厄巴纳-香槟分校的密码学家。NP中的问题并不是人们可以想到的最难的经典问题。还有比这更难的问题。

因此，马开始与普林斯顿大学的密码学家亚历克斯·伦巴第和加州大学伯克利分校的量子计算研究员约翰·赖特一起集思广益，如何最好地解决这个问题。这太迷人了，而且有点令人难以置信，我立刻就被迷住了。

然后我就想，“费米、亚历克斯，你们想什么时候让我加入一个项目？”我就是这样参与进来的。在思考这个问题一段时间后毫无结果后，马建议他们考虑最极端的情况：一个可以立即解决任何具有经典输入的计算问题的预言机。

这将包括复杂性理论家传统上研究的所有问题，甚至包括那些已知在现实世界中无法解决的问题。伦巴第对此的看法是：“当我们提出这个问题时，这听起来有点疯狂。我们实际上仍然不知道答案，但我认为我甚至没有预料到我们能够证明的单查询结果。所以这个问题结果非常有成效。在研究了近一年之后，他们最终发表了一个惊人的结果——

任何允许咨询那个无所不能的预言机一次的算法都不能区分这两个量子态，这是确定量子比特承诺方案所必需的。将算法限制为单个查询比听起来要少一些约束，因为量子算法可以通过利用称为叠加的现象来有效地要求预言机同时解决多个问题。

可以顺序进行多次查询的算法可能更强大，因为它们可以使用预言机对先前查询的答案来决定接下来要询问什么。这些算法是否同样受到限制仍然是一个悬而未决的问题。马、伦巴第和赖特的论文也因另一个原因而意义重大。

当三位研究人员正在努力解决他们的问题时，他们意识到它与16年前复杂性理论家斯科特·阿隆森和数学家格雷格·库珀伯格提出的一个重大未解决问题密切相关。这是关于将一种量子态转换为另一种量子态的难度。这篇新论文是解决这个问题的第一步。

Tomohiro Morimae是京都大学汤川理论物理研究所的量子密码学研究员。他称这是一个非常强大的结果，也是一个非常令人惊讶的结果。

最近的一系列结果表明，区分两个量子态这个看似无害的问题不仅困难，而且几乎难以想象地困难。它远远超出了普通量子算法甚至更奇特的算法的范围。这对密码学来说是个好消息，但它也对输入为量子态的计算问题具有更广泛的影响。

传统的复杂性理论似乎无法解决这些问题。真正理解它们可能需要一个全新的理论框架。或者用华盛顿大学的量子密码学家安德里亚·科拉丹杰洛的话来说：“感觉量子信息的运行方式与经典信息有根本的不同。它必然会有一些也超越密码学的联系。”

阿琳·桑塔纳帮助制作了这一集。我是苏珊·瓦莱特。要了解更多关于这个故事的信息，请阅读本·布鲁贝克的完整文章《密码学家发现了量子保密的新基础》，该文章发表在我们的网站quantummagazine.org上。快速说明一下，斯科特·阿隆森是量子杂志顾问委员会的成员。他的作品在这档播客中被提及，但他没有参与编辑过程。

此外，西蒙斯计算理论研究所是由西蒙斯基金会的一笔赠款建立的，该基金会也资助了这份编辑独立出版物。西蒙斯基金会的资助决定不会影响我们的报道。一定要告诉你的朋友们关于Quanta科学播客，并给我们一个积极的评价或关注你收听的地方。这有助于人们找到这个播客。