密码学家发现量子加密的新基础

研究者已经证明，在一个没有困难问题的世界中，安全的量子加密是可能的。

假设你想发送私有消息、进行无记名投票或安全地签署文档。如果你是在计算机上执行任意这些任务，你都需要依靠加密来保证数据安全。这种加密需要抵御来自使用自己的计算机的密码破译者的攻击，因此现代加密方法需要依赖计算机难以解决的数学问题作为假设。

但当密码学家在 20 世纪 80 年代为这种信息安全方法奠定数学基础时，一些研究者发现计算困难性并不是保护秘密的唯一方法。量子理论，最初是为了理解原子物理学而发展的，后来被证明与信息和密码学有着深刻的联系。研究者找到了将一些特定密码学任务的安全性直接建立在物理定律的基础上的方法。但这些任务都是些奇怪的异常情况——对于所有其他任务来说，除了经典计算方法之外似乎别无选择。

到了上世纪末，量子密码学研究者认为故事已经结束了。但在过去的几年里，该领域又经历了一次巨大的转变。

哥伦比亚大学量子信息理论家 Henry Yuen 表示：“我们认为关于量子密码学的可能性序列已经发生了重新排列。”

在最近的一系列论文中，研究者表明，即使在几乎所有计算都很容易的假想世界中，大多数密码学任务仍然可以安全地完成。唯一重要的是一个关于量子理论本身的特殊计算问题的困难度。

加州伯克利Simons计算理论研究所的量子密码学家Fermi Ma说：“你需要的假设可能要弱得多。这让我们对计算困难性本身有了新的认识。”

此消息将自毁

故事开始于 20 世纪 60 年代末，当时一位名叫斯Stephen Wiesner的物理学研究生开始思考量子理论中测量的破坏性本质。对受量子物理规则支配的任何系统进行测量，你将改变以数学方式描述其配置结构的量子态。这种量子测量扰动对大多数物理学家来说都是一个障碍。Wiesner对量子理论采取了非正统的以信息为中心的观点，他想知道它是否可以变得有用。也许它可以作为敏感数据的一种内禀的保护篡改的形式。

但Wiesner的想法远远超前于他们的时代，他在研究生毕业后离开了学术界。幸运的是，他与他的朋友兼物理学家Charles Bennett讨论了他的想法，Charles Bennett十年来一直试图引起其他人对这个主题的兴趣，但没有成功。最后，1979 年，Bennett在一次会议期间在波多黎各海岸游泳时遇到了计算机科学家Gilles Brassard。他们共同撰写了一篇开创性的论文，描述了完成重要密码学任务的新方法。他们的协议基于量子测量扰动，不需要对任何计算问题的困难度进行假设。

Quantum cryptography: Public key distribution and coin tossing https://arxiv.org/abs/2003.06557

“量子信息本质上似乎就有点密码学” ，Ma说。

Bennett 和 Brassard的突破让研究者乐观地认为，类似的量子技巧可以为其他密码学任务带来完美安全性。研究者主要关注一项称为比特承诺的任务，该任务本身很有用，同时也是最先进的密码协议的关键组成部分。

要理解比特承诺背后的基本思想，请想象一个两人游戏，你必须在其中做出一个秘密决定，该决定稍后会被揭晓。一种方法是将决定写在一张纸上，然后放入密封的信封中。这样，在之后就不能改变你的决定，你的对手也不能过早地看到结果。

现在想象一下你正在在线玩这个游戏。为了使作弊成为不可能，你需要将决定密封在一种数字信封中，任何玩家都无法单独打开。这正是密码学的用武之地。 1981 年，计算机科学先驱 Manuel Blum 构造了第一个比特承诺协议——一种从计算困难问题中构造实际不可破解的信封的方法。

Coin flipping by telephone a protocol for solving impossible problems https://dl.acm.org/doi/10.1145/1008908.1008911

但到底多难是难呢？计算复杂性理论领域的研究者研究了许多不同类型的困难问题，但并非所有问题都对密码学家有用。比特承诺和所有其他密码协议都依赖于复杂性理论家称为“NP”的一类问题，其特征是很容易检查一个候选解是否正确。

不幸的是，研究者还无法证明任意 NP 问题确实是困难的。仍然可能存在一些未被发现的巧妙程序或算法，甚至可以解决那些看起来最难的问题。如果存在这样的算法，那么所有的经典密码学都将被攻破。

这些因素激发了对基于量子的安全保证的探索。但 1997 年，两篇论文证明，如果比特承诺方案仅基于量子物理定律，那么它们永远不可能彻底安全。这些论文暗示，存在某种计算困难性对几乎所有密码学任务都是必要的。

• Unconditionally Secure Quantum Bit Commitment is Impossible https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.78.3414
• Is Quantum Bit Commitment Really Possible? https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.78.3410

这是近 25 年来关于量子比特承诺理论基础的最终定论。然后，在 2021 年，一位名叫 William Kretschmer 的研究生发表的一篇论文促使研究者面对一个没人想到要问的问题。对于比特承诺和大多数其他形式的密码学来说，计算困难性显然是必要的，但到底是哪种困难性呢？

Quantum Pseudorandomness and Classical Complexity https://arxiv.org/abs/2103.09320

答案会比任何人预想的都要奇怪。

查询神谕

这篇 2021 年的论文源于 Kretschmer 努力理解一个在概念上听起来很简单的问题的特定版本：区分或辨别两个表面上相似的量子态有多难？Kretschmer现在是Simons研究所的博士后研究员，他最初对这个问题感兴趣的原因与比特承诺完全无关。

Pseudorandom States, Non-Cloning Theorems and Quantum Money https://arxiv.org/abs/1711.00385

“我甚至没有注意到密码学，”他说。

辨别问题很有趣，部分原因是我们甚至不清楚如何使用熟悉的数学语言来描述它。复杂性理论学家传统上研究具有由比特串（0和1串）表示的不同可能输入的问题。例如，对于将大数分解为质因数的问题，该串表示要分解的数字。

即使研究者开始研究如何利用量子物理进行计算，他们仍然在继续关注此类“经典输入”问题。典型的量子算法从普通的经典比特串开始，然后使用量子技巧对其进行处理。但在像Kretschmer这样的“量子输入”问题中，输入不是比特串——它们是量子态，很容易被计算和测量所扰乱。

“我们在传统复杂性理论中描述量子计算的语言无法直接谈论这些问题，”Yuen说。

起初，Kretschmer认为他只需要把问题翻译成更标准的语言，但他不知道如何去做。因此，他做了复杂性理论家在绝望时经常做的事情：求助于神谕。

在复杂性理论中，“神谕”一词指的是一种可以立即解决特定问题的假想设备。通过将神谕作为算法的中间步骤，能够访问神谕的计算机就可能能够更轻松地解决另一个问题。当然，现实世界中并不存在神谕，但研究它们可以帮助复杂性理论家理解不同问题的难度级别之间的关系。

Kretschmer想知道什么样的神谕可以轻松地区分两种量子态——即所谓的状态辨别问题。他决定从一个特殊的神谕开始，该神谕可以增强普通量子算法，即使用量子技巧来解决经典比特串输入问题的算法，的能力。这些算法可以解决一些对于经典算法来说很难的问题，比如分解大数，但它们并不是万能的——许多其他问题超出了它们的能力范围。

访问 Kretschmer 的神谕将使此类算法能够解决某些对于真正的量子计算机来说太难的经典输入问题。 Kretschmer 认为这有点过强了，但令他惊讶的是，他证明了状态辨别问题仍然可以难住这些增强的量子算法。

“我真的对William的论文很着迷，”波士顿大学密码学研究生Luowen Qian说。 “我实际上认为这一定是错误的，因为它太反直觉了。”

Qian， Yuen和其他人很快证明了，如果Kretschmer的状态辨别问题确实很难，那么安全的量子比特承诺方案是可能的。这接着意味着一系列更高级的密码协议的安全性。量子密码学的范围比 20 世纪 90 年代研究者意识到的要广泛得多，这一切都取决于一个问题的难度。

• Cryptography from Pseudorandom Quantum States https://arxiv.org/abs/2112.10020
• Quantum commitments and signatures without one-way functions https://arxiv.org/abs/2112.06369

它能有多难？

Kretschmer的结果有一个很大的注意点——为了使证明有效，他必须依赖一种不寻常的神谕，只有量子算法才能查询。也许一个更熟悉的神谕就会让他的状态辨别问题变得容易，从而使安全的量子比特承诺变得不可能？ 2022 年，Kretschmer 和Qian开始合作，看看他们可以对一个人人都能理解的预言可以证明什么：一个可以立即解决任意 NP 问题的神谕。在拥有这样的神谕的世界里，所有经典密码学都是不可能的。

Kretschmer很快意识到，状态辨别问题在数学上与量子复杂性理论中的一个表面上不同的问题有关，他得到了该领域两位专家的帮助，即复杂性理论家Avishay Tal 和 Makrand Sinha. “William真的就像一名经理，而我们是承包商，”Tal说。

四位研究者共同努力，很快证明，即使对于可以调用 NP 神谕的计算机来说，Kretschmer 的状态辨别问题仍然是困难的。这意味着即使支撑经典密码学的每个问题都很简单，几乎所有量子密码学依然都可以保持安全。经典密码学和量子密码学越来越像是两个完全不同的世界。

Quantum Cryptography in Algorithmica https://arxiv.org/abs/2212.00879

结果引起了Ma的注意，他开始思考自己能将Kretschmer发起的工作推进到什么程度。即使使用更古怪的神谕（可以立即解决比 NP 中的计算问题困难得多的计算问题），量子密码学还能保持安全吗？ “NP 中的问题并不是人们能想到的最难的经典问题，”伊利诺伊大学厄巴纳-香槟分校的密码学家Dakshita Khurana 说。 “除此之外还能更难。”

Ma开始与普林斯顿大学密码学家 Alex Lombardi 和加州大学伯克利分校量子计算研究员 John Wright 一起合作，讨论如何最好地解决这个问题。 “这太令人着迷、太令人费解了，我立刻就被迷住了，”Wright说。

在思考了这个问题一段时间但毫无结果后，Ma 建议他们考虑可能的最极端情况：一个可以立即解决任何经典输入计算问题的神谕。这将包括复杂性理论家传统上研究的所有问题，甚至是那些已知在现实世界中无法解决的问题。

“这对我来说听起来有点疯狂，”Lombardi说。

但事实证明这个问题非常富有成效。经过近一年的研究，他们终于发表了令人震惊的结果。没有允许查询全能神谕一次的算法可以区分两个量子态，这是攻破量子比特承诺方案所必需的。

A one-query lower bound for unitary synthesis and breaking quantum cryptography https://arxiv.org/abs/2310.08870

将算法限制为单个查询实际上并没有听起来那么严格，因为量子算法可以通过利用称为叠加的现象，高效地要求神谕同时解决多个问题。可以按顺序进行多个查询的算法可能会更强大，因为它们可以使用神谕对先前查询的答案来决定下一步要问什么。这些算法是否同样受到限制仍然是一个开放问题。

Ma, Lombardi 和 Wright的论文之所以重要还有另一个原因。当三位研究者在努力解决他们的问题时，他们意识到这与 16 年前复杂性理论家 Scott Aaronson 和数学家 Greg Kuperberg 提出的一个重大开放问题密切相关，该问题关于将一种量子态转变为另一种量子态的难度。这篇新论文是解决这个问题重要的第一步。

Quantum Versus Classical Proofs and Advice https://arxiv.org/abs/quant-ph/0604056

京都汤川理论物理研究所的量子密码学研究员 Tomoyuki Morimae 表示：“这是一个非常强的结果，也是一个非常令人惊讶的结果。”

最近的一系列结果表明，区分两种量子态的问题这个听起来无害的问题，不仅困难，而且是令人难以置信的难——远远超出了普通量子算法甚至更奇特的量子算法的能力范畴。这对于密码学来说是个好消息，同时它对于输入为量子态的计算问题也具有更广泛的影响。传统的复杂性理论似乎无法解决这些问题。真正理解它们可能需要一个全新的理论框架。

华盛顿大学量子密码学家Andrea Coladangelo表示：“感觉就像量子信息的行为模式存在着根本的不同，它必然具有超出密码学范畴的联系。”