⚛️ quantum physics

Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM

本文在涉及经典查询与通信的特定受限设定下，建立了量子随机预言机模型（QROM）中针对量子密钥协商的首个无条件攻击，从而证明了在此类条件下，针对经典消息的不完全完备量子公钥加密是不可能的。

原作者： Fuyuki Kitagawa, Ryo Nishimaki, Agi Villanyi, Takashi Yamakawa

发布于 2026-08-19

📖 1 分钟阅读🧠 深度阅读

原作者： Fuyuki Kitagawa, Ryo Nishimaki, Agi Villanyi, Takashi Yamakawa

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

在数字世界中，两个陌生人经常需要就一个秘密代码达成一致，以便安全地进行通信，尽管他们从未谋面，且是在任何人都可以监听的渠道上交谈。几十年来，这种方式的标准做法依赖于一个数学谜题：一个人创建一个难题，另一个人解决它，而这个解法就成为了他们的共享密钥。试图窃听的监听者必须解决同一个谜题，但经典物理定律表明，他们需要比诚实参与者多付出极大的工作量，从而保证了秘密的安全。然而，量子计算机的兴起——它们能以经典机器无法实现的方式处理信息——让这一假设受到了质疑。科学家们长期以来一直在思考，量子力学是否允许两个人创建一个即使面对拥有无限计算能力的窃听者也完全安全的密钥，或者这种系统是否存在某种基本的安全极限。

一组研究人员现在通过证明一种特定类型的量子密钥共享系统在根本上无法实现安全，向回答这个问题迈出了重要一步。他们关注的是这样一种场景：爱丽丝（Alice）和鲍勃（Bob）试图达成一个密钥，而第三者伊芙（Eve）在旁监听。在他们的模型中，爱丽丝和鲍勃可以使用强大的量子计算机，并且可以发送存在于脆弱量子态中的消息，但有一个限制条件：在对话的早期阶段，爱丽丝被限制只能针对一个共享的随机源提出简单的经典问题。研究人员证明，在这些条件下，一个拥有无限计算能力的窃听者总能破解该系统。他们表明，只要诚实参与者进行的尝试次数在可控范围内，窃听者就能在可控的尝试次数内获知秘密密钥。这一发现排除了在如果密钥生成过程依赖于那些早期的简单问题时，为短消息创建安全的量子公钥加密系统的可能性，即便该系统的其余部分使用了先进的量子技术。

研究人员通过开发一种新的攻击者学习方法构建了他们的证明。将爱丽丝和鲍勃之间的对话想象成一系列步骤，他们在其中通过向一个巨大的随机字典提问来生成密钥。在第一步中，爱丽丝提出几个问题并向鲍勃发送一条消息。研究人员展示了攻击者可以通过观察这条初始消息，然后系统地猜测爱丽丝可能提出了哪些问题。通过专注于那些最有可能的问题，攻击者可以重建爱丽丝所使用的字典的部分映射。一旦建立了这个映射，攻击者就可以模拟爱丽丝的整个过程，包括她最终的量子计算，从而推导出秘密密钥，而无需知道完整的字典。这种技术之所以奏效，是因为一旦初始问题确定，系统的其余部分就会以一种可预测的方式运行，从而可以被攻击者复制。

这种攻击不仅仅是一种理论上的可能性；研究人员还提供了一个攻击者如何实施攻击的具体配方。他们证明，如果诚实参与者对随机源进行的查询次数是合理的，那么攻击者也可以在类似的查询次数内恢复密钥。攻击成功的概率与诚实参与者成功达成密钥的概率直接相关。如果爱丽丝和鲍勃达成密钥的概率不是微乎其微的，那么攻击者也能以很高的概率成功。这是一个强力的否定性结果：它确立了你无法在这种特定设定下构建一个安全的系统。研究人员还将这一逻辑扩展到了更复杂的、包含多轮对话的情景中，即在最后的量子步骤之前，爱丽丝和鲍勃交换许多消息。他们发现，只要早期的所有消息和问题都是经典的，攻击者仍然可以破解系统，无论对话进行了多少轮。

这项工作的意义对于量子密码学的未来至关重要。它明确了可能性的边界。虽然量子计算机提供了保护信息的新方法，但它们并不提供一种能让所有形式的密钥协商都安全的“魔力护盾”。具体而言，如果一个系统依赖于经典密钥生成阶段，它对于强大的窃听者来说仍然是脆弱的。研究人员还将他们的发现应用于一种被称为量子公钥加密的特定加密类型，在这种加密中，公钥被用于加密消息。他们表明，如果密钥生成过程仅使用经典查询，那么即使加密和解密步骤是完全量子的，这样的系统也无法抵御拥有无限资源的攻击者。这意味着，为了实现真正的安全，这些系统的密钥生成过程本身必须涉及量子查询，而这是一个实现难度大得多的要求。

这项研究并非声称破解了所有形式的量子密码学，也不暗示所有的量子通信都是不安全的。相反，它划定了一条精确的分界线。它证明了在早期交互为经典情况的特定世界里，实现不可破解的密钥协商是一个不可能完成的任务。研究人员通过结合两种强大的数学技术实现了这一点：一种技术可以识别攻击者可能采取的最优路径，另一种技术允许攻击者重新编程随机源以匹配其模拟过程。通过将这些技术编织在一起，他们创造了一个场景，使得攻击者对系统的观察与诚实参与者的观察变得无法区分，从而能够窃取秘密。这项工作为密码学家提供了一个重要的指南，告诉他们哪里不应该寻找安全性，并将他们引向可能仍持有真正安全钥匙的、更为复杂的全量子方法。

技术摘要：迈向 QROM 中不完全完备密钥协商的不可能性

1. 问题陈述

本文研究了在量子随机预言模型（QROM）下，**量子计算、经典通信（QCCC）密钥协商协议的安全性。具体而言，它调查了不完全完备（imperfectly complete）**协议的可行性，即诚实方以仅为逆多项式概率（ $\alpha > 0$ ）而非确定性达成有效密钥的协议。

先前的研究已在各种限制条件下，确立了完美完备的 QCCC 密钥协商和量子公钥加密（QPKE）的无条件不可能结果。然而，对于诚实方拥有不受限量子预言访问权限的“不完全完备”协议的情况，研究仍处于开放状态。Austrin 等人（2022）确定的一个重要障碍表明，如果“模拟猜想（Simulation Conjecture）”成立，则经典攻击者无法破解此类协议。本文通过在特定方式下限制诚实方的预言访问，绕过了对该猜想的需求，从而实现了针对计算能力不受限的量子攻击者的无条件攻击。

2. 方法论与技术路径

作者结合**重查询学习（heavy-query learning）和随机重编程（random reprogramming）**技术，构建了无条件攻击。其核心策略是构造一个拦截通信的攻击者（Eve），该攻击者学习诚实方所做的“重”预言查询集，然后根据该部分预言对诚实方的视图进行条件重采样，从而恢复密钥。

2.1 两消息攻击

第一种设定考虑了一个两轮协议，其中：

Alice 在第一轮中仅对预言进行经典查询，并向 Bob 发送一个经典消息（ $m_1$ ）。
Bob 可以执行任意量子计算，进行量子查询，并发送一个量子消息（ $\Psi$ ）。
Alice 可以在最后一轮进行量子计算并进行量子查询。

攻击机制：

重查询学习： 在收到 $m_1$ 后，Eve 使用一种学习算法（基于 Austrin 等人和 Katz & Sela）来识别“重”输入——即在给定 $m_1$ 的条件下，Alice 在第一轮中可能查询的值。她通过查询这些重输入来构建一个部分预言 $h$ 。
条件重采样： 由于 Alice 的第一轮查询是经典的，一旦 $m_1$ 和回答的轨迹 $h$ 固定，Alice 的剩余量子态仅取决于这些经典变量。因此，Eve 可以从条件分布 $\omega_{m_1, h}$ 中采样一个新的视图 $(T'_A, S'_A)$ 。
重编程： Eve 拦截 Bob 的量子消息 $\Psi$ 。她在采样状态 $S'_A$ 和 $\Psi$ 上运行 Alice 的最终算法，并使用一个重编程后的预言 $H[T'_A]$ ，该预言在其定义域内与采样的轨迹 $T'_A$ 一致，而在其他地方表现得像原始预言。
分析： 安全性损失由随机重编程引理（Random Reprogramming Lemma）（Katz & Sela）界定。由于 Alice 查询定义在 $Dom(h) $之外的点概率很小（受参数$ \delta$ 控制），重编程不会显著改变量子算法的接受概率。

2.2 多轮攻击

第二种设定将结果扩展到具有任意轮数的协议，前提是存在经典通信前缀（classical-communication prefix）：

在前缀期间，所有的消息和预言查询均为经典。
参与方可以保留量子态并执行局部量子计算。
最后一轮涉及来自 Bob 的可能为量子的消息以及 Alice 的最终量子计算。

攻击机制：

经典模拟： Eve 将经典前缀视为一个辅助的经典协议。由于她是计算能力不受限的，她可以精确模拟 Alice 和 Bob 的经典视图，包括他们的条件剩余态。
Barak-Mah Mahmoody 学习器： Eve 应用 Barak-Mahmoody 学习器（最初用于经典协议）来学习模拟的经典视图，从而学习一个部分预言 $h$ ，并确保在给定 $h$ 的条件下，Alice 和 Bob 的视图近似独立（乘积态）。
重采样与耦合： Eve 在给定 $h$ 的条件下为 Alice 和 Bob 采样独立的视图。然后，她通过采样一个基础预言给 Bob，并为 Alice 重编程该预言，从而将这些视图与一个一致的预言耦合。
最终攻击： Eve 拦截最终的量子消息，并在采样状态上运行 Alice 的最终算法，使用重编程后的预言。

3. 主要贡献与结果

3.1 主要定理

定理 1.1（两消息攻击）： 对于任何 Alice 的第一阶段查询和消息均为经典的协议，存在一个计算能力不受限的量子攻击者，其恢复 Bob 密钥的概率 $> \alpha/2$ ，且使用的查询次数为 $O(\text{poly}(q, 1/\alpha))$ 。该攻击者在 Bob 回应之前进行经典查询，在之后进行量子查询。
定理 1.2（多轮攻击）： 对于具有任意长度经典查询前缀的协议，存在类似的攻击。查询复杂度取决于前缀查询的总数，但与轮数无关。
定理 1.3（QPKE 攻击）： 这些结果意味着，对于经典消息（长度为多项式）的量子公钥加密（QPKE），即使加密、解密和密文都是量子的，在面对进行多项式次查询的计算能力不受限的攻击者时，也无法实现 IND-CPA 安全，前提是其密钥生成过程采用经典查询。

3.2 具体应用

源自 OSP 的不完全正确 PKE： 本文将结果应用于由 Bartusek 和 Khurana (CRYPTO 2025) 提出的隐匿状态准备（Oblivious State Preparation, OSP）衍生的 PKE 方案。研究表明，如果 OSP 发送方仅进行经典随机预言查询，则生成的 PKE 在 QROM 中是不安全的，特别是当底层的 OSP 协议是忽略不计地不正确（negligibly incorrect）（即不完全完备）时。
经典窃听： 如果整个协议（包括 Bob 的响应）都是经典的，则攻击退化为被动经典窃听攻击。

4. 重要性与主张

本文声称通过在以下受限设定下提供首次无条件攻击，在实现不完全完备 QCCC 密钥协商之不可能方面取得了进展：在这些设定中，诚实方在后期拥有不受限的量子预言访问权限。

克服模拟障碍： 作者指出，针对不完全完备 QCCC 的完全通用的经典攻击需要证伪“模拟猜想”。通过将诚实方的早期查询限制为经典，这项工作绕过了该障碍，从而实现了无需假设该猜想为假的无条件攻击。
限制的紧密性： 结果强调了一个关键的权衡：攻击依赖于早期的预言查询是经典的。如果前缀查询是量子的，参与方将与预言发生纠缠，从而阻碍此处使用的“重采样”技术。作者明确指出，将这些结果扩展到前缀中的量子查询需要新的技术，并将其作为未来的工作。
安全概念： 本文定义了一个特定的安全概念（拦截密钥恢复），它比标准的 CC1QM 安全更强，因为它仅要求攻击者恢复密钥，而不要求模拟一个有效的状态给 Alice。然而，这足以破坏所衍生的 QPKE 方案的 IND-CPA 安全性。

总之，本文证明了在不完全完备方案中，初始阶段使用经典预言访问是 QROM 中的致命弱点，即使协议的其余部分是完全量子的，也会使其在面对不受限量子攻击者时变得不安全。