⚛️ 量子物理

Quantum Key Exchange from Public Quantum Money

本文通过证明两消息量子密钥交换（2QKE）与高效可验证状态谜题及一次性安全数字签名的等价性，建立了对 2QKE 的首次完整表征，从而证明了 2QKE 有潜力在比单向函数更弱的假设下构建，同时也为公钥不可克隆原语提供了新的下界，并实现了具有新颖“认证冻结”功能的量子公钥加密。

原作者： Eli Goldin, Tomoyuki Morimae

发布于 2026-11-05

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Eli Goldin, Tomoyuki Morimae

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在安全通信领域，两个从未谋面的人经常需要就一个秘密代码达成一致，以保护他们的信息。几十年来，实现这一目标最可靠的方法依赖于那些正向易解但反向极难的数学问题，例如将两个巨大的质数相乘。这种被称为公钥密码学的技术，多年来一直保护着互联网的安全。然而，量子计算机的兴起威胁到了这些数学锁，迫使科学家们寻找新的基础。一种极具前景的替代方案依赖于物理定律本身，特别是量子信息无法被完美复制这一事实。这一原理使得创建“量子货币”成为可能，其中钞票是一种独特的量子态，任何人都可以验证，但无人能够复制。虽然研究人员早已知道如何利用这些物理定律构建安全通信，但在实现高效性方面一直面临挑战。那些仅需交换两条消息的最有效方法，传统上都依赖于那些量子计算机最终可能攻破的复杂数学问题。

一支研究团队现在绘制出了这些两消息量子交换的完整图景，揭示了它们与另一种加密工具之间令人惊讶的联系。他们发现，仅通过两条消息交换秘密密钥的能力，在数学上等同于创建一种特定类型“谜题”的能力。在这种谜题中，发送者创建一个问题的经典描述以及一个相应的量子态作为解。接收者可以轻松检查给定的量子态是否为正确答案，但仅看到问题描述的黑客无法生成有效的答案。研究人员证明，如果你能构建其中一种系统，你就能构建另一种，反之亦然。这种等价关系是一项重大突破，因为它表明两消息量子密钥交换并不一定需要此前被认为必不可少的沉重数学假设。相反，它可以由这些量子谜题构建，而即使这些复杂的数学问题不存在，这些谜题也可能存在。

这一发现对安全通信的未来具有深远意义。研究人员表明，如果这些量子谜题存在，那么两消息密钥交换就是可能的，并且它还附带一个强大的红利：即使面对拥有无限计算能力和时间的攻击者，只要该攻击者在实际交换过程中仅限于标准的量子能力，系统依然保持安全。这种“永久安全性”意味着，即使黑客今天记录了加密对话，并等待数十年直到超级计算机出现，他们仍然无法破解代码。此外，该团队还展示了这些谜题可以由其他量子工具（如仅限一次使用的数字签名）构建。这为构建安全系统创造了一个新的、更低的门槛，表明构建量子密钥交换所需的要求比此前认为的要弱。

该论文还解决了以往设计中的一个实际限制。早期的两消息交换尝试通常要求发送者保留量子存储器以存储脆弱的状态，这在技术上难以维持。新构造允许发送者在步骤之间仅保留经典信息，使该系统在现实世界中的应用变得更加可行。此外，研究人员还将这项工作扩展到如何构建一个包含“认证冻结”功能的量子公钥加密系统。这允许用户发布一份证书，证明他们已经停止生成新密钥，从而确保没有人可以基于该密钥生成超过特定数量的不同有效密文。这为这类系统增加了此前所缺失的问责制和控制层。

通过建立这些等价关系，研究人员阐明了量子密码学的基本极限。他们表明，能够通过两条消息交换密钥并非一个孤立的奇迹，而是与量子谜题和一次性签名的存在有着深刻的联系。这项工作表明，通往超安全、高效通信的路径可能比预想的要短，其依赖的假设可能比目前保护全球经济的假设更为宽松。这些发现不仅提供了一种新的协议，更提供了一个对“什么是可能的”的完整表征，证明了这些系统的安全性是稳固的，并且最严格的安全保证是自然而然实现的，无需额外代价。

技术摘要：基于公共量子货币的量子密钥交换

1. 问题陈述

本文探讨了构建**两消息量子密钥交换（2QKE）**所需的最小计算假设这一基本问题。

在经典设定下，两消息密钥交换在没有结构化公钥假设（Cryptomania）的情况下是不可能实现的，因为它无法仅通过单向函数（OWF）来构建。在量子设定中，虽然 BB84 协议提供了信息论安全性，但它需要超过两条消息。研究表明，统计安全的 2QKE 是不可能的，因此必须依赖计算假设。

在此项工作之前，已知 2QKE 最弱的假设是单向函数（OWF）的存在。Malavolta 和 Walter (2024) 以及 Kitagawa 等人 (2024) 展示了仅基于 OWF 的 2QKE（以及具有量子公钥的量子公钥加密 QPKE）的构建方法。然而，量子密码学的最新进展表明，许多原语（例如承诺、不经意传输）可以基于可能比 OWF 更弱或不可比的假设（如伪随机态、单向谜题或 EFI 对）来构建。

核心开放问题是：能否从比 OWF 更弱的假设构建 2QKE？ 此外，能否从这些更弱的假设构建具有量子公钥的量子公钥加密（QPKE）？

2. 方法论与技术路径

作者通过建立四个不同密码原语之间的存在性等价关系，对 2QKE 进行了完整的表征。其方法论涉及构建一个归约环路：

从一次安全性数字签名（带有量子签名）到持久安全 2QKE：
- 作者改编了先前基于 OWF 构建中所使用的“相干验证”技术，但对其进行了修改以处理量子签名。
- 在标准签名方案中，Alice 可以生成签名的叠加态。然而，在使用量子签名时，签名算法可能是非确定性的或输出混合态。
- 核心创新： 为了解决生成两个量子签名叠加态（ $|0\rangle|\sigma(0)\rangle + |1\rangle|\sigma(1)\rangle$ ）并恢复密钥的问题，作者引入了一种协议：Alice 生成两个签名，应用受控-SWAP 以创建叠加态，并用随机 Pauli 算符对状态进行掩蔽。这使得 Alice 在无需知道签名算法所应用的特定随机化的情况下，能够在 Bob 交互后恢复密钥位。
- 安全证明依赖于签名方案的一次安全性。不同于以往依赖于“强存在不可伪造性”（这在量子签名中定义不明）的证明，本证明使用了“交叉项”论证。它表明，如果攻击者能够区分密钥，那么他们就必须能够伪造一个针对未查询消息的签名，从而与一次安全性相矛盾。
从 2QKE 到高效可验证状态谜题（EV-StatePuzzs）：
- 作者展示了任何 2QKE 协议都可以转化为 EV-StatePuzzle。
- 构建： 谜题生成器（$Samp$）模拟 Alice 的第一阶段 2QKE，将经典消息作为“谜题”，并将量子态（由 Alice 持有）作为“答案”输出。验证者（$Ver$）模拟 Bob 的交互和 Alice 的第二阶段。
- 安全性： 如果攻击者能够解决该谜题（使 $Ver$ 接受），他们实际上可以通过扮演一个获取密钥的恶意 Bob 来破坏 2QKE 的安全性。
- 这确立了 2QKE 不比 EV-StatePuzzs 更难。
从 EV-StatePuzzs 到一次安全性数字签名：
- 作者利用 EV-StatePuzzs 构建了 Lamport 签名的量子类比。
- 构建： 验证密钥由两个谜题（ $s_0, s_1$ ）组成。签名密钥由相应的答案态（ $\psi_0, \psi_1$ ）组成。为了对位 $b$ 进行签名，发送者揭示 $\psi_b$ 。验证过程检查 $\psi_b$ 是否解决了 $s_b$ 。
- 安全性： 对未查询位的签名伪造意味着解决了相应的谜题，这与 EV-StatePuzzle 的安全性相矛盾。
从单次签名（OSS）到带有认证冻结功能的 QPKE：
- 作者从**单次签名（OSS）**构建了一个 QPKE 方案。OSS 是指签名密钥只能签署一条消息且签名是经典的签名方案。
- 挑战： 标准 QPKE 需要多次签名来生成多个公钥。而 OSS 是“一次性”的。
- 解决方案： 作者采用了证书链技术。第 $t$ 个公钥的生成会对第 $t+1$ 个验证密钥进行签名。由于这些签名是经典的，它们可以被复制并包含在后续的公钥中。
- 认证冻结（Certified Freeze）： 引入了一种新颖的功能，即接收者可以发布一个经典证书，证明其已经“冻结”了系统，从而将其绑定到特定有效密文数量的上界。这是通过使用最后一个未使用的签名密钥对特殊的“停止”消息进行签名来实现的。

3. 核心贡献与结果

论文确立了以下主要定理和推论：

定理 1.1（等价性）： 以下四个原语是存在性等价的：
1. 持久安全 2QKE。
2. 标准 2QKE。
3. 高效可验证状态谜题（EV-StatePuzzs）。
4. 带有量子签名和签名密钥的一次安全性数字签名。
对假设强度的意义： 由于 EV-StatePuzzs（以及相关的原语如伪随机态）可能比 OWF 更弱（即使相对于经典预言机满足 $P=NP$ ，它们也可能存在），因此 2QKE 潜在地比 OWF 更弱。这提供了对 2QKE 的首次完整表征。
推论 1.3（免费的持久安全性）： 如果 2QKE 存在，则持久安全 2QKE 存在。这意味着在两消息设定下，实现针对计算无界攻击者的安全性是“免费”的；除了构建标准 2QKE 所需的假设外，不需要额外的假设。
推论 1.4（Alice 无需量子存储器）： 所构建的 2QKE 允许 Alice 在第一阶段和第二阶段之间无需量子存储器；她的内部状态可以是完全经典的。
定理 1.8 (基于 OSS 的 QPKE)： 如果单次签名（OSS）存在，则具有量子公钥的持久安全 QPKE 存在。
- 由于 OSS 被认为与 OWF 不可比，这表明 QPKE 可以基于比 OWF 更弱或不可比的假设来构建。
- 该构建包括认证冻结功能，允许接收者公开验证其解密能力的限制。
下界： 结果意味着单次签名、量子闪电（Quantum Lightning）和公钥量子货币微型方案蕴含了 EV-StatePuzzs，从而蕴含了持久安全 2QKE。这为这些不可克隆原语提供了新的、非平凡的下界。

4. 重要性与主张

本文声称提供了关于 2QKE 所需计算假设的首次完整表征。通过将 2QKE 与 EV-StatePuzzs 以及带有量子签名和签名密钥的一次性签名联系起来，作者证明了 2QKE 不一定需要完整的 OWF 能力。

关于这项工作重要性的关键主张包括：

向 Minicrypt/Microcrypt 的下降： 结果表明 2QKE 和 QPKE 有潜力从“Cryptomania”（需要 OWF）降至“Minicrypt”甚至“Microcrypt”（基于 EV-StatePuzzs 或 OSS 等更弱的假设）。
持久安全性： 标准 2QKE 与持久安全 2QKE 之间的等价性是一个重要的结构性结果，表明更强的安全概念在实现上并不一定更难。
认证冻结： 在 QPKE 中引入“认证冻结”功能是一项新颖的贡献，它提供了一种机制，让接收者可以公开承诺其解密容量的限制，这在以往的上下文中尚未被定义。

作者对下界的紧密程度保持谦逊。他们明确指出，证明 2QKE 蕴含公钥量子货币微型方案将非常困难（因为这将意味着 OWF 蕴含此类货币），因此 2QKE 与这些不可克隆原语之间的等价关系尚未被证明是双向的。

5. 局限性与开放问题

经典 Bob 消息： 所构建的 2QKE 要求 Bob 向 Alice 发回一个量子态。是否可以从比 OWF 更弱的假设构建一个 Bob 发送经典消息的 2QKE，仍然是一个开放问题。
Alice 的安全性： 在基础的 2QKE 构建中，Eve 可以获取 Alice 的密钥或强制 Alice 和 Bob 的密钥不匹配。作者在第 7 节中通过添加一个短的经典标签（使用 AMD 码）解决了这个问题，但这需要额外的经典通信轮次或特定的协议修改。
来自 EV-StatePuzzs 的多次签名： 作者指出，他们不知道如何从 EV-StatePuzzs 构建多次安全性数字签名。因此，从 EV-StatePuzzs 构建标准 QPKE（即单个公钥加密多条消息）仍然是一个开放问题。他们的 QPKE 构建依赖于 OSS 并且是带状态的（秘密密钥随使用而增长或变化）。