⚛️ quantum physics

Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM

本文证明了在量子随机预言模型下，依赖于量子安全单向函数的完美完备量子密钥协商协议是不可能实现的，因为无论协议的轮复杂度或其他参数如何，窃听者总能利用多项式次数的经典预言查询以确定性方式恢复共享密钥。

原作者： Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu

发布于 2026-08-05

📖 1 分钟阅读🧠 深度阅读

原作者： Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu

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

秘密守护者与神奇黑盒

想象一下，你正试图建立一个秘密俱乐部，两个朋友爱丽丝（Alice）和鲍勃（Bob）想要商定一个秘密密码，且不让任何人知道这个密码是什么。他们可以大声地交谈，但不能低声耳语。为了让这一切奏效，他们两人都可以使用一个神奇的、巨大的“黑盒”来回答问题。如果你向这个盒子提出一个特定的问题，它会给出一个随机答案；但如果你再次询问完全相同的问题，它会给出完全相同的答案。这就是现代密码学的核心：利用一个共享的、不可预测的工具，从公开的对话中创造出一个私密的秘密。

几十年来，科学家们一直在思考，当这两个朋友使用超先进的量子计算机时，这种设置是否真的安全。量子计算机就像拥有一种超能力，让你可以通过“叠加态”（一种高级的说法，意为“同时进行”）来一次性询问黑盒许多个问题。核心问题在于：爱丽丝和鲍勃能否利用这些量子超能力，创造出一个即使是盯着他们公开对话的超级聪明的窃听者也无法破解的秘密？这篇论文深入探讨了这个问题，特别是在这样一种场景下：朋友们仅使用普通的经典词汇进行交谈，但在进行数学运算和向黑盒提问时则使用量子魔法。

并非不可破解的完美秘密

这篇论文对在这种特定量子设定下实现完美、不可破解的秘密这一想法，给出了一个令人惊讶且明确的“否定”。作者们是一组研究人员，他们通过数学证明，如果朋友们被允许进行任意次数的往返对话，那么利用量子计算机和随机黑盒来创建一个完美的、绝对安全的密钥协议是不可能的。

以下是他们发现的故事：

设定：一场捉迷藏游戏
想象爱丽丝和鲍勃正在玩一个游戏。他们从各自私有的、秘密的笔记开始。他们轮流向对方发送消息。这些消息只是普通的文本，比如“你好”或“天空是蓝色的”。然而，在发送消息之前，他们都会运行一个量子程序，向“神奇黑盒”（随机预言机）提出一系列问题。他们可能会问盒子：“问题 X 的答案是什么？”或者“那问题 Y 呢？”他们可以以量子叠加态的方式提出这些问题，这意味着他们实际上是在同时询问数百万个问题。根据这些答案，他们试图达成一个最终的秘密密钥。

游戏的规则是“完美完备性”（perfect completeness）。这意味着，如果黑盒正常工作，爱丽丝和鲍勃必须 100% 地得到完全相同的密钥。这里没有误差的空间。如果他们得到的密钥不同，协议即宣告失败。

反派：窃听者
现在，想象有一个名叫伊芙（Eve）的恶棍。伊芙正在监视爱丽丝和鲍勃发送的所有消息。她没有改变任何东西，她只是在倾听。她也可以访问同一个神奇黑盒。核心问题是：伊芙能否仅仅通过监听对话并向黑盒提出她自己的问题，就推导出那个秘密密钥？

之前的研究表明，如果爱丽丝和鲍勃只进行两次对话（两轮协议），伊芙可以轻易破解代码。但如果他们交谈十次呢？或者一百次呢？他们能否通过漫长的对话来隐藏这个秘密？

突破：不可能的盾牌
这篇论文证明了，无论爱丽丝和鲍勃交谈多少次，或者他们的对话变得多么复杂，伊芙总能获胜。作者构建了一种特定的方法，让伊芙能够以 100% 的确定性恢复秘密密钥。

以下是他们的证明过程，使用了一个简单的类比：

可能性的地图： 爱丽丝和鲍勃每次交谈时，本质上都在缩小一张包含黑盒所有可能答案的巨大地图。因为他们使用量子数学，他们可能答案的“形状”是受限的。作者表明，爱丽丝和鲍勃所使用的函数的数学“次数”（degree，一种复杂度的度量）受限于他们向黑盒提问的次数。
不相交的拼图： 因为爱丽丝和鲍勃必须达成完全相同的密钥，他们的数学路径必须完美交汇。作者证明，对于任何特定的对话记录，爱丽丝和鲍勃最终可能得到的密钥就像地图上的岛屿。这些岛屿是“不相交的”（disjoint），这意味着它们互不重叠。如果爱丽丝认为密钥是“苹果”，那么如果他们要达成一致，鲍勃就不能认为密钥是“香蕉”。
侦探的技巧： 作者发现，由于这些“岛屿”在数学上如此独特且数量有限，伊芙不需要去猜测。她可以使用一种聪明的搜索策略。想象伊芙有一份所有可能密钥的列表。她将列表平分为两半，然后向黑盒提出几个特定的问题，以观察哪一半包含了真正的密钥。
制胜的一步： 论文显示，伊芙可以非常高效地完成这个拆分过程。尽管爱丽丝和鲍勃可能提出了大量的量子问题，但伊芙只需要提出数量级的经典问题（即她是一个一个提出的，而不是在叠加态下）就能找到密钥。具体来说，如果爱丽丝和鲍勃分别提出了 $q_A$ 和 $q_B$ 个问题，伊芙只需要提出大约 $(q_A + q_B)^5$ 个问题即可找到密钥。

结论
这项结果最令人兴奋的部分在于，它适用于任何轮数的协议。无论爱丽丝和鲍勃交谈了一分钟还是一年，都无关紧要。无论秘密密钥有多长，都无关紧要。论文证明，如果通信是纯粹经典的，且目标是完美完备，那么“量子叠加”的“盾牌”无法保护秘密密钥。

作者不仅是在暗示这可能发生，他们还提供了一个严密的数学证明。他们表明，对于每一个符合这些规则的可能协议，都存在一种特定的、确定性的方式让窃听者破解它。窃听者不需要成为天才；他们只需要遵循证明中所提供的配方，而这个配方涉及向黑盒提出可控数量的问题。

简而言之，这篇论文关闭了关于“增加对话次数”或“更多量子魔法”可以拯救这种特定模型下完美完备密钥协议的希望之门。如果你想要一个在这个设定下能 100% 免受被动窃听者威胁的秘密，这篇论文给出的答案是：这根本无法构建。看来，当你被迫向世界大声喊出你的线索时，宇宙对你能隐藏秘密的程度是有极限的。

技术摘要：在 QROM 中实现完美完备的多轮密钥协商之不可能性的证明

问题陈述
本文探讨了量子随机预言模型（QROM）中量子密钥协商（QKA）的基本极限。具体而言，它研究了两个参与者（Alice 和 Bob）是否能够仅通过经典通信、执行局部量子计算并对随机预言进行量子查询，从而建立一个具有完美完备性（概率为 1）的共享密钥。该设定处于量子计算与经典通信（QCCC）模型下。核心问题在于：如果协议是以量子安全单向函数（OWF）以黑盒方式构建的，那么对于一个观察经典传输记录并拥有相同预言访问权限的被动窃听者，此类协议是否能够保持安全。

此前的工作已经建立了针对经典协议和特定量子情况的隔离，但在通用的多轮 QCCC 协议方面仍存在空白。值得注意的是，Austrin 等人（CRYPTO 22）在依赖于一个未经证实的“多项式兼容性猜想”的情况下，提出了一个多项式查询攻击；而 Li 等人（CRYPTO 26）则无条件地解决了两轮协议的情况。本文旨在不依赖任何未经证实的猜想，为任意轮数的协议填补这一空白。

方法论
作者结合了量子查询复杂度理论、布尔函数的多项式分析以及决策树复杂度，构建了一个无条件的攻击。其核心方法论如下：

传输概率的多项式分解：
通过固定完整的经典传输记录 $t$ 和预言真值表 $z$ ，Alice 和 Bob 输出特定密钥 $a$ 和 $b$ 的概率被证明可以分解为 $A_{t,a}(z) \cdot B_{t,b}(z)$ 。此处， $A$ 和 $B$ 是代表 Alice 和 Bob 局部执行概率的非负函数。
- 利用量子多项式方法（特别是 [BBC+01] 中的引理 2.2），作者限制了这些函数的度数： $\deg(A_{t,a}) \le 2q_A$ 且 $\deg(B_{t,b}) \le 2q_B$ ，其中 $q_A$ 和 $q_B$ 分别是诚实参与者进行的量子查询次数。
基于完美完备性的不相交密钥支持集：
完美完备性条件（ $Pr[K_A = K_B] = 1$ ）意味着对于任何有效的传输记录 $t$ 和预言 $z$ ，对于所有不同的密钥 $k \neq \ell$ ，乘积 $A_{t,k}(z)B_{t,\ell}(z)$ 必须为零。
- 通过定义 $C_{t,k}(z) = A_{t,k}(z)B_{t,k}(z)$ ，作者证明了这些多项式的支撑集在布尔立方体 $\{0,1\}^N$ 上是两两不相交的。
- 这种不相交性结合非零 $d$ 次多项式在至少 $2^{N-d}$ 个点上非零的特性（引理 2.1），将候选密钥的数量 $|K_t|$ 限制在至多 $2^d$ 以内，其中 $d = 2(q_A + q_B)$ 。
不相交多项式的决策树：
其关键的技术贡献是一个确定性程序（引理 3.5），用于在已知其中一个多项式非零的承诺下，识别给定两个不相交支持集的多项式 $p$ 和 $q$ 中哪一个在特定预言 $z$ 处非零。
- 该程序使用递归决策树。在每一步中，它识别出一组 $O(d^3)$ 个预言位，查询这些位要么能确定答案，要么能严格降低其中一个多项式的度数。
- 这种降低依赖于应用于由输入平方差构造的派生多项式 $r$ 的离散马尔可夫不等式（引理 2.3）。
- 该决策树的深度被证明为 $O(d^4)$ 。
二分查找策略：
窃听者在候选密钥集 $K_t$ （大小 $\le 2^d$ ）上执行平衡二分查找。在每一层，候选集被分为两半，并形成相应的多项式之和（ $P$ 和 $Q$ ）。由于它们的支撑集是不相交的，因此有且仅有一个 $P(z)$ 或 $Q(z)$ 为非零。决策树（步骤 3 中的工具）用于确定哪一半包含了正确的密钥。
- 通过至多 $d$ 层二分查找以及每层 $O(d^4)$ 次查询，总查询复杂度为 $O(d^5)$ 。

主要贡献与结果

无条件不可行性： 本文证明了在 QROM 中，无法以黑盒方式从量子安全单向函数（OWF）构建完美完备的有限轮次 QCCC 密钥协商协议。这一结果是无条件的，消除了先前工作 [ACC+22] 所需的“多项式兼容性猜想”。
查询复杂度界限： 作者构建了一个能够以概率 1 恢复共享密钥的窃听者，该窃听者仅需 $O((q_A + q_B)^5)$ $O ((q_{A} + q_{B})^{5})$ 次经典预言查询。
- 该界限与通信轮数、传输长度、密钥长度以及预言域大小无关。
- 至关重要的是，尽管诚实参与者可能使用叠加态查询，但窃听者仅需要经典查询。
泛化性： 该结果将之前关于两轮协议 [LLLL26] 的发现推广到了任意轮次，并允许参与者在通信阶段之间保持任意量子态，这涵盖了先前无条件结果未涉及的情景。

意义与主张
本文声称为多轮、完美完备的 QKA 在 QROM 中的安全性提供了一个明确的否定回答。

理论影响： 它在 QCCC 设置下，在量子安全单向函数与完美完备密钥协商之间建立了严格的黑盒分离。
方法论进步： 该证明引入了多项式度数降低和决策树复杂度在密钥恢复问题中的创新应用，特别处理了诚实参与者使用量子叠加态而攻击者受限于经典查询的情况。
局限性： 作者明确指出，其证明依赖于完美完备性。将此结果扩展到具有不完美完备性（即参与者可能以微小概率无法达成一致）的协议需要完全不同的思路，本文并未涵盖此部分。
归属： 文中指出，核心证明由 GPT-5.6 Sol Ultra 在一次对话中发现，人类作者负责验证、完善及最终的阐述。

综上所述，本文表明在 QROM 中，经典通信与完美完备性的结合不足以保护密钥协商免受高效经典窃听者的攻击，无论轮数多少或局部量子计算的复杂度如何。

秘密守护者与神奇黑盒

并非不可破解的完美秘密

技术摘要：在 QROM 中实现完美完备的多轮密钥协商之不可能性的证明

类似论文