⚛️ quantum physics

On Best-Possible One-Time Programs

本文证明了通用最佳一次性程序编译器的不可能性，进而提出了“可测试一次性程序”这一新范式，通过引入广义单次有效查询安全概念及状态化量子混淆技术，在经典预言机模型下实现了针对任意量子功能的首次最佳可测试一次性程序构造。

原作者： Aparna Gupte, Jiahui Liu, Luowen Qian, Justin Raizes, Bhaskar Roberts, Mark Zhandry

发布于 2026-03-03

📖 1 分钟阅读🧠 深度阅读

原作者： Aparna Gupte, Jiahui Liu, Luowen Qian, Justin Raizes, Bhaskar Roberts, Mark Zhandry

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

这篇论文探讨了一个非常酷但也充满挑战的密码学概念：“一次性程序”（One-Time Programs, OTPs）。

想象一下，你有一个绝密的软件（比如一个自动交易机器人，或者一个只有你能用的签名工具）。你希望把它发给别人，让他们只运行一次，用完就销毁，而且他们绝对不能把软件复制下来，或者偷偷多运行几次来破解你的秘密。

这就好比你想把一把只能开一次门的魔法钥匙交给别人。

这篇论文就像是一群密码学侦探，试图搞清楚：在量子计算机的世界里，我们到底能不能造出这种“完美的一次性钥匙”？如果能，它的极限在哪里？

以下是用通俗语言和比喻对这篇论文核心内容的解读：

1. 核心难题：为什么“完美”的一次性程序不存在？

背景故事：
在经典计算机时代，如果你把软件发给人，他们很容易复制（Ctrl+C, Ctrl+V），所以“一次性”很难实现。早期的想法是依赖硬件（比如一个只能烧录一次的芯片）。后来，有人想利用量子力学的特性（量子态不能被完美复制）来造一次性程序。

论文的发现（坏消息）：
作者首先证明了一个不可能定理：

不存在一种“万能编译器”，能把任何程序都变成“最完美”的一次性程序。

比喻：
想象你有一个“万能魔法盒”，声称能把任何复杂的机器（程序）变成“只能用一次的机器”。
作者发现，如果这个盒子真的存在，它就能帮你破解某些加密系统（比如基于“有损加密”的系统）。
这就好比：如果你能造出一个“绝对防复制的万能钥匙”，那你肯定也能造出一个“能打开所有锁的万能钥匙”，这在逻辑上是行不通的。
结论： 想要一个通用的、能处理所有情况的“完美一次性程序”是不可能的。

2. 转折点：如果我们退一步，能不能做到“可测试”的？

既然“完美”做不到，作者们没有放弃，而是提出了一个更聪明的策略：“可测试的一次性程序”（Testable OTPs）。

什么是“可测试”？
普通的程序发出去后，你没法知道它是不是被偷偷修改了。但“可测试”的程序，就像是一个带自检功能的魔法盒子。

它不仅能运行，还能告诉你：“嘿，我现在的状态还是出厂设置，没被篡改过。”
如果有人试图偷偷多运行一次，或者试图复制它，这个“自检功能”就会失效，程序就会“自爆”或者拒绝工作。

比喻：
想象你送出去一个一次性照相机。

普通一次性相机： 拍完照，你没法知道底片有没有被偷偷多拍几张。
可测试一次性相机： 这个相机里有一个特殊的“状态指示灯”。如果你试图在没拍完之前强行再拍一张，或者试图把胶卷拆下来复制，指示灯就会变红，相机直接锁死。
关键点： 作者证明，只要程序具备这种“自检能力”，我们就能在理论上构建出非常安全的方案。

3. 解决方案：单有效查询（SEQ）安全

作者提出了一种新的安全标准，叫**“单有效查询”（Single Effective Query, SEQ）**。

这是什么意思？

传统的一次性： 物理上只能按一次按钮。
SEQ 的一次性： 即使你在量子世界里，你可以按无数次按钮，但真正有效的、能产生新信息的，只有一次。
- 如果你按了第一次，得到了结果。
- 如果你试图按第二次，系统会“温柔地”把你推回第一次的状态，或者告诉你“没用了”，就像你按了一个没电的按钮。

比喻：
想象你在玩一个**“只有一次的抽奖机”**。

你投币（输入），机器吐出一张彩票（输出）。
如果你试图把彩票塞回去再摇一次，机器会识别出彩票已经被“消耗”了，或者它会把彩票变回原来的样子，让你感觉什么都没发生。
对于外部观察者来说，看起来你只抽了一次奖，尽管你可能按了很多次按钮。

作者证明：只要满足这种"SEQ 安全”，就能实现**“可测试程序中的最佳安全性”**。也就是说，在“可测试”这个范围内，我们已经做到了人类能做到的极限。

4. 未来的希望：带记忆的“量子伪装术”

为了在现实世界（不需要特殊硬件）中实现这个目标，作者提出了一个新的概念：“有状态的量子混淆”（Stateful Quantum iO）。

什么是“混淆”（Obfuscation）？
就是把程序的源代码变成一堆乱码，让人看不懂，但功能还能用。
什么是“有状态”？
普通的程序像一本死书，翻来翻去内容不变。但“有状态”的程序像是一个有记忆的智能助手。它会根据你之前的操作改变自己的行为。

比喻：

普通混淆： 把一本食谱的页码打乱，但菜谱内容不变。
有状态混淆： 把食谱变成一本活页书。如果你第一次看“做蛋糕”，书里会记录“蛋糕已做”。如果你第二次想看“做蛋糕”，书会自动把这一页变成“蛋糕已做，无法再做”，或者变成别的菜谱。
为什么这很重要？ 作者发现，如果我们能造出这种“会随时间改变记忆的活页书”，我们就能完美地实现“可测试的一次性程序”。

总结：这篇论文到底说了什么？

打破幻想： 别指望有一个“万能的一次性程序编译器”能解决所有问题，这在数学上是不可能的（就像别指望有永动机一样）。
找到出路： 如果我们接受程序必须具备“自检能力”（可测试），那么问题就迎刃而解了。
新标准： 提出了"SEQ 安全”作为衡量标准，证明只要达到这个标准，就是目前能做到的“最安全”。
未来方向： 要实现它，我们需要一种新的技术——“有状态的量子混淆”。这就像给程序装上“记忆”和“自毁机制”，让它能随着使用次数自动改变行为。

一句话总结：
虽然造不出“完美无缺”的一次性程序，但作者们找到了一条**“带自毁功能的智能程序”**之路，这条路在理论上是通的，并且为未来的量子安全软件指明了方向。就像虽然造不出“绝对防弹”的盾牌，但我们造出了“被击中一次就自动消失”的盾牌，这也足够安全了。

这篇论文《On Best-Possible One-Time Programs》（关于最佳可能的一次性程序）由 Aparna Gupte 等人撰写，深入探讨了量子一次性程序（One-Time Programs, OTPs）的安全界限、不可能性结果以及可行的替代方案。

以下是对该论文的详细技术总结：

1. 研究背景与问题定义

背景：
一次性程序（OTPs）旨在允许用户仅对程序进行一次输入评估，除此之外不泄露任何关于程序的其他信息。

经典设定： 在纯软件模型中，由于程序可被复制，OTPs 无法实现，必须依赖硬件假设（如硬件令牌）。
量子设定： 尽管量子力学禁止克隆（No-Cloning），但 Broadbent, Gutoski 和 Stebila (BGS13) 指出，通过“温和测量”（Gentle Measurement），攻击者仍可对确定性功能进行多次评估。因此，即使有量子信息，确定性功能的 OTPs 仍需硬件假设。
近期进展： 最近的研究（如 GLR+25, GM24）在无需硬件假设的情况下，为具有高熵输出的随机化功能构建了 OTPs。

核心问题：
现有的安全定义（如 CSEQ）是否代表了 OTPs 能达到的最强安全界限？是否存在一种通用的“最佳可能”（Best-Possible）一次性编译器，即对于任何功能，该编译器都能实现理论上能达到的最强安全性？

2. 主要贡献与结果

论文的主要贡献分为三个部分：不可能性证明、引入“可测试”子类并证明其可行性、以及提出新的混淆概念。

2.1 最佳可能一次性编译器的不可能性 (Impossibility of Best-Possible OTPs)

定义： 作者定义了“最佳可能一次性编译器”（Best-Possible OTP Compiler），灵感来自 Goldwasser 和 Rothblum 的“最佳可能混淆”（Best-Possible Obfuscation）。其核心思想是：如果存在任何程序 $P$ 能实现功能 $f$ ，那么最佳编译器生成的程序 $\text{OTP}^*(f)$ 应该与 $P$ 在计算上不可区分（即泄露的信息最少）。
结果： 论文证明了通用的最佳可能一次性编译器不存在。
假设： 该结果基于**损耗加密（Lossy Encryption）**方案的存在性（例如基于 LWE 或弱伪随机群作用）。
证明思路：
1. 构造两个功能族 $D$ （损耗模式）和 $E$ （注入模式）。
2. $D$ 的输出分布与输入无关（统计上独立），而 $E$ 是注入的（输入不同输出不同）。
3. 由于损耗加密的公钥在两种模式下计算不可区分， $D$ 和 $E$ 也是计算不可区分的。
4. 然而，为了实现最佳安全性， $D$ 的 OTP 必须表现为常数函数（不泄露输入信息），而 $E$ 的 OTP 必须表现为注入函数（保持正确性）。
5. 攻击者可以通过在输入上运行叠加态并测量输出是否坍缩，来区分常数函数和注入函数。
6. 如果存在最佳编译器，它必须能区分 $D$ 和 $E$ 以采取不同的策略，但这与 $D$ 和 $E$ 的不可区分性矛盾。
结论： 即使对于随机化经典功能，也不存在通用的最佳可能 OTP 编译器。

2.2 可测试一次性程序与 SEQ 安全性 (Testable OTPs and SEQ Security)

鉴于通用最佳可能性的不可能，作者引入了一个自然的子类：可测试一次性程序（Testable OTPs）。

定义： 一个 OTP 是“可测试”的，如果它的输出不仅包含程序状态 $|\tilde{P}\rangle$ ，还包含一个反射预言机（Reflection Oracle） $R = I - 2|\tilde{P}\rangle\langle\tilde{P}|$ 。这使得用户可以验证程序状态是否被破坏（即是否仍为初始纯态）。
关键洞察： 之前的不可能性证明依赖于混合态（Mixed States）实现，这些实现仅在平均意义上正确，但单个纯态分量不正确。可测试性要求输出是定义良好的纯态，从而排除了这种反例。
SEQ 安全性（Single Effective Query）： 作者推广了 Gupte 等人提出的 CSEQ 概念，定义了适用于任意量子通道（Quantum Channels）的 SEQ 安全性。
- 核心机制： 引入一个“自伴实现”（Self-adjoint implementation）接口。该接口允许一次有效查询，但如果输出被“有意义地”扰动（导致无法恢复到初始状态），后续查询将失效。
主要定理：
1. SEQ 蕴含最佳可能安全性： 对于可测试程序类，任何满足 SEQ 安全性的编译器都是该类中的“最佳可能”编译器。
2. 构造性结果： 在经典预言机模型（Classical Oracle Model）中，可以构造出针对所有量子功能的 SEQ 安全 OTPs。这是首个针对任意量子通道（超越经典随机化功能）且无需硬件假设的正面结果。

2.3 面向纯模型构建：状态化量子混淆 (Stateful Quantum iO)

为了在纯模型（Plain Model，即无预言机）中实现最佳可能可测试 OTPs，作者提出了新的混淆概念。

问题： 标准的量子混淆（如针对幺正算符的 iO）通常假设程序是无状态的或行为在多次查询中不变。但 OTPs 本质上是状态化的（查询后行为改变）。如果两个程序仅在第一次查询时等价，但在后续查询中表现不同，标准的混淆定义无法处理。
新定义：状态化量子不可区分混淆（Stateful Quantum iO, sqiO）
- 定义要求：如果两个状态化量子程序在任意多项式长度的查询序列上产生相同的输出分布，则它们的混淆版本应不可区分。
- 这避免了之前针对“单次查询等价”定义的不可能性结果。
结果：
1. sqiO 蕴含最佳可能可测试 OTP： 如果存在 sqiO，则可以构造最佳可能的可测试 OTP。
2. 存在性： 在经典预言机模型中，可以构造 sqiO（利用量子认证方案和理想幺正混淆）。
意义： 这为在纯模型中构建最佳可能 OTP 提供了一条可行的路径（尽管 sqiO 在纯模型中的构造仍是一个开放问题，但在预言机模型中已解决）。

3. 技术细节与方法论

不可能性证明技术： 利用损耗加密（Lossy Encryption）的两种模式（注入 vs 损耗），结合量子叠加态测试（检测纠缠/坍缩），展示了最佳编译器在区分不可区分功能时的内在矛盾。
SEQ 接口设计： 设计了包含计数器 $C$ $C$ 和私有寄存器 $P$ $P$ 的自伴单元 $S(U)$ $S (U)$ 。
- 第一次查询：翻转 $C$ ，应用 $U$ 。
- 后续查询：如果 $P$ 未恢复初始态（即被扰动），则 $C$ 不翻转，接口表现为恒等变换，从而阻止进一步的有效查询。
反射预言机的作用： 在证明 SEQ 蕴含最佳可测试安全性时，反射预言机 $R$ 用于在模拟器中“重置”程序状态，确保模拟器可以模拟 SEQ 接口，即使面对的是不同的实现 $P'$ 。
状态化混淆的必要性： 论文指出，对于采样程序，仅考虑单次查询的等价性会导致混淆方案成为最佳 OTP，从而触发不可能性。因此，必须考虑多轮查询的等价性（状态化）。

4. 结论与意义

理论界限的厘清： 论文确立了通用“最佳可能”OTP 的不可能性，即使对于随机化功能也是如此。这划定了量子 OTP 安全性的理论天花板。
新的安全范式： 提出了“可测试 OTP"和"SEQ 安全性”作为更现实且可达到的安全目标。SEQ 安全性成为了量子 OTP 领域的“虚拟黑盒”（VBB）类比，尽管它允许某些特定的攻击（如温和测量导致的多次评估），但它提供了清晰的安全上限。
架构创新： 将 OTP 的研究从单纯的“单次执行”扩展到包含“状态演化”和“可测试性”的框架，为设计更复杂的量子密码原语（如一次性签名、NIZK）提供了理论基础。
未来方向： 论文将“状态化量子混淆（sqiO）”确立为在纯模型中实现最佳可测试 OTP 的关键。这为后续研究指明了方向：要么构造纯模型下的 sqiO，要么寻找其他绕过不可能性的途径。

总结：
这篇论文通过严谨的不可可能性证明和巧妙的构造性结果，重新定义了量子一次性程序的研究方向。它表明，追求绝对的“最佳可能”通用编译器是徒劳的，但通过引入“可测试性”和“状态化混淆”，我们可以在预言机模型中实现理论上的最佳安全性，并为纯模型中的构建提供了清晰的路线图。