量子科学家建立了一种新的密码学数学

原文：https://www.quantamagazine.org/quantum-scientists-have-built-a-new-math-of-cryptography-20250725/

作者：Ben Brubaker

译者：Kurt Pan

理论上，量子物理学可以绕过现代加密技术根源上的数学难题。一项新的证明展示了如何做到这一点。研究人员正在重建密码学之塔的基础。

难题通常不受欢迎，但密码学家却喜欢它们。这是因为某些数学难题支撑着现代加密的安全性。任何巧妙的破解技巧都可能毁掉大多数形式的密码学。

几年前，研究人员发现了一种全新的加密方法，它没有这一潜在弱点。该方法利用了量子物理学的独特特性。与早期仅适用于少数特殊任务的量子加密方案不同，这种新方法可以完成更广泛的任务。即使普通"经典"密码学的所有核心问题都能被轻松解决，它也能正常工作。

• https://www.quantamagazine.org/cryptographers-discover-a-new-foundation-for-quantum-secrecy-20240603/

但这一惊人发现依赖于不现实的假设。加州伯克利西蒙斯计算理论研究所的密码学研究员 Fermi Ma 表示，这一结果“更像是一个概念证明，而不是对现实世界的陈述。”

如今，两位密码学家发表的一篇新论文，为量子密码学开辟了一条新路径，摆脱了那些古怪的假设。Ma 说："这篇论文认为，如果某些其他猜想成立，那么量子密码学就一定存在。"

• http://arxiv.org/abs/2409.15248

天空之城

你可以把现代密码学想象成一座由三个基本部分组成的塔。第一部分是塔底深处的基石，由复杂的数学问题构成。塔本身是第二部分——在那里你可以找到特定的密码协议，让你可以发送私人消息、签署数字文档、进行秘密投票等等。

在这两者之间，将这些日常应用固定在数学基石上的，是一种由称为单向函数的构建块构成的基础。它们导致了任何加密方案固有的不对称性。"它是单向的，因为你可以加密消息，但你无法解密它们，"NTT Research 的密码学家Mark Zhandry 说。

20 世纪 80 年代，研究人员证明，建立在单向函数之上的密码学能够确保许多不同任务的安全性。但几十年过去了，他们仍然不确定其基石是否足够坚固。问题在于，这些基石是由一些特殊的难题构成的——技术上称为 NP 问题——其定义特征是很容易检验任何候选解是否正确。（例如，将一个数分解成它的素因数就是一个 NP 问题：对于大数来说很难，但检验起来很容易。）

这些问题中很多看似本质上很难，但计算机科学家却一直无法证明这一点。如果有人发现了一种巧妙的算法，可以快速解决最难的 NP 问题，那么基石就会崩塌，整座塔都会倒塌。

• https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/

不幸的是，你不能简单地把塔搬到别处。塔的地基——单向函数——只能建立在 NP 问题的基石上。

为了在更困难的问题上建起一座塔，密码学家需要一个由非单向函数构成的新基础。这似乎是不可能的，直到几年前，研究人员意识到量子物理学可以提供帮助。

这一切始于 2021 年研究生 William Kretschmer的一篇论文，该论文引发了人们对一个关于量子系统特性的奇怪问题的关注。研究人员很快证明，Kretschmer的问题可以取代单向函数，成为构建新型密码协议塔的基础。次年，Kretschmer等人证明了这种替代方法即使没有困难的 NP 问题也能奏效。突然之间，似乎有可能构建一座更加坚固的密码堡垒了。

• https://arxiv.org/abs/2103.09320
• https://arxiv.org/abs/2112.06369
• https://arxiv.org/abs/2112.10020
• http://arxiv.org/abs/2212.00879

但该在哪里构建它呢？ Kretschmer 所基于的量子问题涉及一种名为"预言机"的假设计算设备，它可以即时回答特定问题。预言机可以成为有用的理论工具，但它们实际上并不存在。 Kretschmer 的证明就像是建造空中楼阁的蓝图。有没有办法把它落地呢？

第二基地

2022 年秋天，这个问题引起了伊利诺伊大学香槟分校和 NTT 研究中心密码学家Dakshita Khurana的关注。 Khurana 和她的研究生  Kabir Tomer 着手构建一座新的密码学之塔。她的第一步是使用量子构建块（而非经典的单向函数）构建一个新的基础。然后，她需要证明这个新的基础能够支撑起一座由其他密码协议组成的塔。一旦她证明了这个基础能够支撑起这座塔，她就必须为整个建筑找到一个坚实的支撑点——一个由现实世界问题组成的基石，这些问题似乎比经典密码学中使用的 NP 问题更难。

Dakshita Khurana着手寻找可以取代单向函数作为量子密码学基础的数学构建块。

第一步， Khurana 和 Tomer 专注于单向函数的量子版本，称为单向状态生成器，它满足使单向函数有用的三个特性。首先，该函数必须运行速度快，以便你可以轻松地为要发送的每条消息生成一个密码学锁和相应的密钥来打开它。其次，每个锁都必须是安全的，如果没有正确的钥匙，要费很大的力气才能打开。最后，每个锁都必须易于用正确的钥匙打开。

• https://eprint.iacr.org/2022/1336

关键的区别在于锁的性质。经典的单向函数生成的数学锁由比特组成——在经典计算机中存储信息的 0 和 1。而量子单向状态生成器则会生成由量子信息单元（称为量子比特）组成的锁。即使所有经典锁都很容易破解，这些量子锁也可能保持安全。 Khurana 和 Tomer 希望从这个新的量子基础入手，并在此基础上构建一座密码协议塔。"这结果相当困难，" Khurana 说。"我们被困了好几个月。"

到2023年7月， Khurana 已经怀孕近九个月，正在计划休育儿假。 Tomer 却束手无策。"我比 Dakshita 悲观得多，"他说。"她总是相信事情会好转。"

随后，他们取得了突破。关键的一步是定义另一个数学构建块，它就像地下室的地板：一个将单向状态生成器的基础与密码协议塔连接起来的结构。当 Khurana 和 Tomer 研究出这个构建块需要具备的属性时，他们发现它类似于一个单向函数，同时具有令人费解的量子和经典特性。与普通的单向函数一样，锁和钥匙都是由经典比特构成的，但生成这些锁和钥匙的过程只能在量子计算机上运行。更奇怪的是，这个新的构建块满足了单向函数的前两个定义属性，但不满足第三个：生成锁和钥匙很容易，而且每个锁都很难破解。但用钥匙打开锁却不容易。

Khurana 和 Tomer 将这些令人费解的新构建块称为单向谜题。直观地看，很难想象它们有什么用处：一把永远用不上的钥匙有什么用呢？但这两位密码学家证明，单向谜题与其他量子技巧相结合，实际上可以实现许多密码协议。如果你能生成原则上可以匹配的锁和钥匙，那么解锁过程效率再低也无所谓了。

• https://arxiv.org/abs/2310.11526

Kabir Tomer 和 Khurana 将新的量子构建块与现实世界的问题联系起来，这些问题比传统密码学中使用的更困难。

"仅仅知道存在某种可以任意慢的算法就足够了，"现任西蒙斯研究所研究员的 Kretschmer 说道。"这非常令人惊讶。"

找到缺失的部分后，他们很快于 8 月 4 日完成了证明。几天后， Khurana 的女儿就出生了。

永久记录

到了 11 月， Khurana 重返工作岗位，准备尝试计划的第二阶段。她和 Tomer 已经证明，许多类型的密码学可以建立在单向谜题之上，而单向谜题又可以建立在由单向状态生成器构成的新量子基础之上。他们最初计划的下一步是将这个量子基础与一个新的基石连接起来——一些相对坚不可摧、甚至比 NP 问题更难解决的数学问题。

但当 Khurana 和 Tomer 努力完成这项任务时，他们决定采取更直接的方法：忘记单向状态生成器，而是将单向谜题直接锚定在数学基石上。

William Kretschmer 证明，从理论上讲，量子密码学无需所有经典加密所必需的单向函数即可保证安全。

从某种角度来看，这似乎是一个奇怪的选择。单向谜题是 Khurana 和 Tomer 在证明的中间步骤中使用的数学怪异之处。

然而，单向谜题也有一些优势。首先，虽然它们是量子的，但它们生成的锁和钥匙却是经典的。 Khurana 认为，这可能使它们更容易与经典数学的基石联系起来。此外，单向谜题生成的钥匙过于笨重，无法真正打开锁。这或许可以更容易地将它们与那些棘手到连验证答案都显得无比困难的问题联系起来。

但哪些具体问题会奏效呢？ Khurana 心中有一个候选方案：计算矩阵（一个数字表格）中条目的特定组合。这个问题被称为矩阵积和式（Permanent）问题，对于大型矩阵来说，求解难度极高，而且没有简单的方法可以检查计算是否正确。矩阵积和式问题还具有其他一些特殊的数学性质，这些性质对密码学家来说很有吸引力。

"这将是构建密码学的一个绝佳问题，" Khurana 说。

矩阵积和式问题也与另一个问题相关，这个问题量子计算机可以轻松解决，但经典计算机似乎无法解决。研究人员正在努力从精确的理论意义上证明这一量子计算优势。 Khurana 和 Tomer 证明，这样的证明也能让他们基于矩阵积和式问题构建安全的单向谜题，从而构建整个量子密码学体系。

• https://www.quantamagazine.org/google-and-ibm-clash-over-quantum-supremacy-claim-20191023/

"他们能够基于这些经过充分研究的假设做到这一点，" Kretschmer 说。"我真的很高兴看到这一点。"

凭借这项新成果， Khurana 和 Tomer 有效地将两个悬而未决的问题简化为一个。如果研究人员能够证明量子计算机在特定任务上确实超越了经典计算机，那么量子密码学的理论基础将自动地比几乎任何经典密码学都更加稳固。

可惜的是，短期内你还无法使用 Khurana 和 Tomer 的新方法发送秘密信息。尽管最近取得了一些进展，量子计算技术还不够成熟，无法将他们的想法付诸实践。与此同时，其他研究人员已经设计出可以更快投入使用的量子密码学方法，但要证明它们真正安全，还需要做更多的工作。

• https://www.quantamagazine.org/quantum-computers-cross-critical-error-threshold-20241209/
• http://arxiv.org/abs/2504.15343

量子密码学已被证明充满惊喜，研究人员最近才开始探索这些可能。"我们只是想了解这个一直存在的新领域，"Zhandry说。