⚛️ quantum physics

Separating Quantum Indistinguishability Obfuscation from Falsifiable Assumptions

本文通过证明，在特定 QMA 间隙问题存在的前提下，量子不可区分混淆（qIO）与针对 QMA 的见证加密无法通过受限的经典黑盒归约从标准的、可证伪的密码学假设中得出，从而确立了构建这两类原语的障碍。

原作者： Mohammed Barhoush, Tomoyuki Morimae, Ramis Movassagh

发布于 2026-08-27

📖 1 分钟阅读🧠 深度阅读

原作者： Mohammed Barhoush, Tomoyuki Morimae, Ramis Movassagh

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

在密码学领域，最终目标通常是隐藏程序的内部运作机制，同时保持其功能完整。想象一下，如果有一段软件执行复杂的计算；理想的工具应该是将代码彻底混淆，使其无法被逆向工程，但程序仍能为需要使用它的人完美运行。这种被称为“混淆”（obfuscation）的概念，长期以来一直是计算机科学家的圣杯。虽然研究人员在混淆经典计算机程序方面取得了显著进展，但量子计算的兴起引入了一个新的前沿。量子程序运行在量子力学的奇异规则之上，信息可以同时存在于多种状态中，这使得它们更难受到保护。一种被称为“量子不可区分混淆”（quantum indistinguishability obfuscation）的特定保护类型，旨在使这些量子程序变得难以理解，作为高级安全系统（如见证加密，witness encryption）的基础——这种加密允许数据被锁定在一个陈述之后，只有当特定的秘密证明存在时，才能解锁该陈述。

多年来，科学界一直试图利用标准且易于理解的数学假设来构建这些量子安全工具。这些假设就像现代加密技术的基石；它们是那些被认为难以解决的问题，例如在巨大的草堆中寻找特定的钥匙。如果一种新的安全工具可以建立在这些已知的难题之上，它就被认为是值得信赖的。然而，来自 IonQ 和京都大学的研究人员的一项新研究表明，这条路径可能已被封死。他们已经证明，只要安全证明遵循某种特定的逻辑结构，任何这种特定且强大的量子安全形式都无法从这些标准的、可测试的数学假设中构建出来。这一发现并不意味着这种安全工具不可能构建，而是说，如果它存在，它必须依赖于一个与我们目前用于保护数字世界的基石截然不同的基础。

研究人员将调查重点放在了涉及 QMA 类问题的见证加密的一个特定场景上。简单来说，QMA 问题是指如果你被给予一个特殊的量子证据（称为“见证”，witness），答案可以被快速验证，但寻找该证据却极其困难。研究人员提出了一个直截了当的问题：我们能否仅使用标准的数学假设，构建一个基于某个陈述来加密数据的系统，使得只有拥有正确的量子见证的人才能解密？为了回答这个问题，他们采用了一种严谨的证明方法，这种方法就像是一个逻辑陷阱。他们设想了一个场景，其中安全证明试图将该加密系统的安全性与一个标准的数学假设联系起来。然后他们证明，如果这种联系存在，将会导致矛盾。

他们发现的核心在于一个巧妙的模拟。他们证明了，如果一个标准的数学假设成立，那么就可能创建一个“伪造”的攻击者，这个攻击者可以像真实的、拥有无限能力的攻击者一样破解加密系统，而无需真正知道秘密。在密码学领域，如果一个系统可以被一个看起来与真实攻击者完全一致的伪造攻击者破解，那么该系统就被认为是极不安全的。研究人员证明，对于他们研究的这种特定类型的量子加密，这个伪造的攻击者总是可以用一个标准的数学假设来构建。这意味着，如果该加密系统确实是安全的，那么底层的数学假设就必须是错误的。既然我们相信这些标准假设是正确的，那么逻辑结论就是，该加密系统无法建立在这些假设之上。

这一结果具有重要意义，因为它为我们如何接近量子安全设定了一个硬性限制。这项研究并不是说量子不可区分混淆是无法实现的；它只是说，我们无法使用几十年来一直为我们提供帮助的标准、可测试的假设来构建它。研究人员仔细定义了其证明的边界。他们的结论适用于一类特定的安全证明，即测试过程遵循某些规则，例如使用标准的、非自适应的查询。他们还指出，其结果专门针对输出经典信息的系统，例如标准的数字比特。这留下了另一种可能性，即输出量子态的混淆器可能仍然可以基于标准假设构建，尽管这仍然是一个开放性的问题。

该研究引入了一个新概念来支持其论点：即通过两条消息的经典通信进行验证的内容与使用量子见证进行验证的内容之间存在差距。他们假设，存在某些量子问题，即使借助一个强大的预言机（oracle），也无法通过仅仅两轮的经典对话来解决或验证。这一假设得到了当前领域知识的支持，即目前已知最好的验证量子计算的方法需要超过两轮的消息传递。通过利用这一差距，研究人员得以构建他们的逻辑陷阱，证明了连接标准假设与这种特定量子安全工具之间的桥梁无法建成。

最终，这项工作为未来的研究提供了指路明灯。它告诉密码学界，如果他们希望构建这些先进的量子安全工具，必须超越多年来一直依赖的标准假设。他们可能需要寻找新的、或许更奇特的数学基础，或者接受这些工具依赖于更难测试和验证的假设。这篇论文并没有关闭量子混淆的大门，但它坚定地关闭了其中一条广受期待的路径。通过排除这种可能性，研究人员澄清了领域格局，迫使科学家们重新思考他们的策略，并可能去寻找全新的方式来保障量子的未来。

技术摘要：将量子不可区分混淆与可证伪假设分离

1. 问题陈述

本文探讨了从标准的可证伪假设（falsifiable assumptions）构建**量子不可区分混淆（qIO）**以及 **QMA 的见证加密（Witness Encryption, WE）**这一基础性挑战。虽然经典 IO 已能基于一些基础假设进行构建（尽管这些假设在量子攻击下已被破解），但 qIO 的地位仍未定论。目前尚未有在纯模型（plain model）下基于标准假设构建 qIO 的方案，也缺乏解释这种缺失现象的已知不可能结果。

具体而言，作者研究了 WE for QMA（以及由此衍生的 null-qIO）的安全性是否可以基于任何可证伪假设。可证伪假设被定义为：存在一个高效的挑战者，能够判定对手是否获胜（即通过交互式游戏）。文中指出，WE for QMA 本质上是不可证伪的，因为验证对手的成功（例如，证明一个语句不在该语言内，或证明两个电路是空电路）在计算上是困难的。因此，作者提出了问题：我们能否从标准的、可证伪的假设出发来构建 qIO（或 WE for QMA）？

2. 方法论

作者采用了由 Gentry 和 Wichs 最初为经典 SNARG 引入，并由 Alagic 等人和 Barhous et al. 扩展到量子环境的可模拟对手范式（simulatable-adversary paradigm）。其核心策略是证明：如果存在黑盒归约（black-box reduction），则会导致关于特定假设难度的矛盾。

该方法论通过以下技术步骤展开：

修改后的安全游戏： 作者将 WE 的安全游戏重新定义为交互式的。与以往分离研究中对手将实例 $x$ 作为静态输入不同，在此处，对手必须首先提交一个实例 $x$ （它声称 $x$ 不在语言 $L$ 中），然后尝试解密该 $x$ 生成的密文。这种交互性对于实现分离至关重要，但也增加了模拟的复杂性。
QMA–QCIP[2] 间隙假设： 该不可能结果依赖于一个新的假设：存在一个 QMA–QCIP[2] 间隙问题。该问题假设存在一个 QMA 语言 $L$ $L$ ，满足：
1. “是”实例（Yes-instances）可以带有见证（witnesses）被高效采样。
2. “否”实例（No-instances）可以被采样（可能效率较低）。
3. 即便拥有一个 QCIP[2] Oracle（一个可以判定任何基于经典信道的两消息交互式证明值的 Oracle），没有任何高效量子算法能够区分这两个分布。
受限归约： 该不可能结果适用于受限的量子黑盒归约。这些归约必须满足：
1. 非自适应地查询对手。
2. 保留安全参数（不允许使用更小参数的查询）。
3. 以经典方式查询对手。
4. 仅针对诚实生成的密文（由诚实加密算法在随机比特上生成的密文）进行查询。
通过隐藏测试进行模拟： 为了模拟一个破坏 WE 的无界对手，作者利用 QCIP[2] Oracle 构建了一个模拟器。一个关键的技术创新是使用隐藏植入密文（hidden planted ciphertexts）。模拟器将真实的密文与测试密文（其明文是已知的）交织在一起并进行打乱。QCIP[2] 协议中的验证者如果发现任何测试密文的回答错误，则会拒绝。这迫使最优证明者（Oracle 的输出）必须表现为一个贝叶斯解密器（Bayesian decryptor）（即对所有密文，包括真实的密文，都输出最可能的明文），以避免被拒绝。这使得高效的模拟器能够模仿无界对手的行为。

3. 主要贡献与结果

主定理（定理 2）： 假设存在 QMA–QCIP[2] 间隙问题，则 WE for QMA 的安全性无法通过受限的量子黑盒归约基于任何可证伪的密码学假设。
关于 Null-qIO 的推论： 由于 null-qIO 蕴含 WE for QMA（如 Bartusek 和 Malavolta 所证），同样的结论也适用于 null-qIO。
一致性安全性（Uniform Security）： 不同于以往依赖非均匀建议（non-uniform advice，即硬编码对手行为）的分离研究，本结果排除了即使是仅针对**均匀对手（uniform adversaries）**安全的实现可证伪假设的归约。这是因为 WE 游戏的交互性质阻止了将对手的指数级行为压缩进非均匀建议中。
技术障碍： 本文确立了：如果你相信一个可证伪假设是成立的，那么不存在以所述形式的安全性证明来将其作为 WE for QMA 的基础。

4. 局限性与范围

论文明确说明了其结果的边界：

密文类型： 该不可能结果仅适用于使用经典密文的 WE。它并未排除混淆器或密文为量子态的 qIO 或 WE。作者指出，现有的伪确定性量子电路和幺正程序（unitary programs）的构建方案输出的是量子态，因此属于本文分离范围之外。
归约限制： 结果仅限于非自适应、保持参数且仅查询诚实生成密文的归约。移除这些限制仍是一个开放性问题。作者认为这些限制对于 WE 是自然的，但也承认提升这些限制是主要的研究挑战。
经典 IO： 这些技术不适用于经典电路的经典 IO。由于经典 IO 蕴含 NP 的 WE，而对于 NP，一个 QCIP[2] Oracle 可以直接判定该语言（因为见证是一个单消息证书），这意味着不存在间隙问题。
假设有效性： 该分离是以 QMA–QCIP[2] 间隙问题的存在性为条件的。虽然目前的领域现状（例如 Mahadev 的协议需要四条消息，以及之前的黑盒分离研究）支持了这一点，但本文并未为这个特定的间隙提供具体的实例化或 Oracle 分离证明。

5. 意义

本文为从标准假设构建 qIO 和 WE for QMA 提供了结构性的障碍。它表明，构建这些原语的困难不仅仅是缺乏巧妙的构造方法，更可能是根本性的，即无法通过标准的黑盒技术将非可证伪的原语建立在可证伪的假设之上。

通过引入 QMA–QCIP[2] 间隙问题，并在交互式安全游戏（而非以往研究中的单次游戏）的模拟对手范式下展示分离，作者扩展了量子密码学中不可能结果的前沿。这项工作强调了见证加密的交互性质创造了独特的挑战，使得无法直接应用以往的非交互式分离技术，从而必须使用诸如“隐藏测试协议”这类新工具来强制实现最优证明者行为。

最终，本文得出结论：除非 QMA–QCIP[2] 间隙假设是错误的，或者人们转向超越受限黑盒归约（或转向非可证伪假设）的方法，否则从标准假设构建 qIO 很可能是不可行的。