⚛️ quantum physics

Certified Randomness without Structure Against Shallow-Query Adversaries

本文无条件地证明了 Yamakawa-Zhandry 可认证随机性协议在面对浅查询量子对手时的安全性，从而在不依赖于尚未证实的 Aaronson-Ambainis 猜想的情况下，建立了可认证的随机性。

原作者： Dakshita Khurana, Bhaskar Roberts, Avishay Tal

发布于 2026-08-26

📖 1 分钟阅读🧠 深度阅读

原作者： Dakshita Khurana, Bhaskar Roberts, Avishay Tal

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

随机性是现代安全的隐形引擎，是让数字锁无法被破解、秘密无法被窃取的不可预测之火花。在经典世界中，真正的随机性是一种奢侈品；计算机是确定性机器，遵循严格的规则，这意味着它们生成的任何数字在原则上都是可预测的，只要你知道起始点。量子力学提供了一条不同的路径。由于测量量子系统的行为本质上是概率性的，量子设备可以产生从根本上不可预测的输出，即使是对一个拥有该设备设置完美知识的观察者而言也是如此。但这产生了一个信任问题：一个无法观察量子态的经典观察者，如何能确定该设备确实在使用这种量子随机性，而不是在伪装？观察者需要一种方法来证明输出是真正的随机，而非伪装成偶然的预定答案。

多年来，研究人员一直试图通过依赖关于某些问题求解难度的复杂数学假设，或者要求量子设备在物理上保持隔离以防止其模拟预期行为来解决这个问题。Yamakawa 和 Zhandry 最近的一项突破性进展提出了一种新方法，使用了“随机预言机”（random oracle）——这是一个类似于完美随机黑盒的理论工具。他们设计了一种协议，要求量子证明者必须在这一黑盒中找到一个隐藏的特定模式。他们表明，量子计算机可以轻松做到这一点，而经典计算机则不能。至关重要的是，他们怀疑任何成功完成此任务的量子计算机都必须产生真正的随机输出，而非仅仅是幸运的猜测。然而，他们关于输出是随机性的证明依赖于一个关于量子加速结构性的深层且未经证实的假设。如果该假设是错误的，随机性的保证就会消失。

Dakshita Khurana、Bhaskar Roberts 和 Avishay Tal 的一篇新论文为一类特定的攻击者消除了这种不确定性。作者证明，只要攻击者在向黑盒索取信息的序列次数上受到限制，Yamakawa-Zhandry 协议就能保证可验证的随机性，而无需任何未经证实的假设。具体而言，他们表明，如果对手只能进行极少量的连续轮次提问——大约是安全参数的对数级别——他们就无法欺骗系统。即使对手在计算速度方面拥有无限的能力，只要他们被限制在如此浅的交互深度内，他们就无法迫使系统输出一个可预测的答案。

研究人员通过分析对手如何与随机预言机交互实现了这一结果。他们引入了“查询权重”（query weight）的概念，用于衡量对手对黑盒特定部分的关注程度。他们证明，对于一个想要以高概率输出正确答案的对手而言，他们必须将大量的这种“关注”集中在他们最终给出的几乎每一个答案部分上。换句话说，他们不能仅仅靠猜测；他们必须彻底检查答案。作者随后证明，一个仅进行少量连续轮次提问的对手，根本无法聚集足够的关注度来锁定一个特定的正确答案。有限的轮次迫使对手将注意力分散得过于稀薄，以至于永远无法锁定一个单一且可预测的解。

这一结果具有重要意义，因为它从第一原理出发确立了协议的安全性，而不是依赖于关于量子计算机运作方式的广泛猜想。作者表明，只要攻击者不允许连续提问过多，这种随机性就不是算法特有的偶然现象，而是问题本身的一个必要特征。虽然他们的证明目前仅适用于具有非常有限连续轮次的对手，但它为量子随机预言模型中的可验证随机性提供了一个坚实的、无条件的基石。它证实了对于这些受限的攻击者而言，量子证明者确实是在掷骰子，而经典验证者可以信任这一结果。

技术摘要：针对浅层查询攻击者的无结构认证随机性

问题陈述
本文解决了在量子随机预言机模型（QROM）中生成“可认证随机性”（certifiable randomness）的挑战。虽然量子力学具有内在的概率性，但经典验证者必须能够信任量子证明者是在真实地利用这种随机性，而非输出一个有偏或预先确定的答案。

Yamakawa 和 Zhandry (YZ24) 最近提出的一个关于量子性的证明方案，其原理是让证明者从一个列表可恢复码（list-recoverable code） $C$ 中找到一个码字 $\mathbf{x}$ ，使得对于所有坐标 $i$ ，满足 $H_i(x_i) = 0$ ，其中 $H$ 是一个随机预言机。诚实的 YZ 算法的一个关键特征是其输出本质上是随机的（即来自有效码字的均匀采样）。YZ 曾设想，任何成功的证明者都必须从高熵分布中进行采样，从而将该协议转化为一种可认证随机性的来源。

此前，YZ 仅在 Aaronson-Ambainis (AA) 猜想下证明了这一设想，该猜想是一个结构性假设，即量子加速需要输入域中存在潜在结构。然而，AA 猜想在一般情况下尚未得到证明。作者提出了疑问：能否在不依赖于 AA 猜想的情况下，无条件地建立 YZ 协议的可认证随机性保证？

方法论与技术路径
作者针对一类特定的攻击者提供了无条件安全性证明：这类攻击者对随机预言机的自适应查询轮数最多为 $o(\log \lambda)$ （但在每一轮内可以进行多项式次并行查询）。证明策略依赖于“查询权重”（query weight）分析以及涉及预言机重编程（oracle reprogramming）的计数论证。

查询权重与交换引理（Swapping Lemma）：
核心分析工具是“查询权重”，定义为量子攻击者的查询寄存器在各查询层中测量特定符号 $(i, x_i)$ 的累积概率。作者利用了交换引理，该引理用于界定当预言机在特定输入集上被重编程时，攻击者量子态的变化量，其变化量取决于这些输入上的总查询权重。如果攻击者对一组输入分配的权重很小，那么在这些输入上重编程预言机对攻击者输出分布的影响就会微乎其微。
第一步：低熵攻击者必须“重度查询”其答案：
作者证明，如果一个攻击者以高概率输出一个正确的码字 $\mathbf{x}$ ，则它必须在其几乎所有的符号上分配非忽略不计的查询权重。
- 论证： 如果一个攻击者以高概率输出 $\mathbf{x}$ ，但对其中许多符号分配的权重很小，那么可以通过将这些低权重符号的哈希值从 0 翻转为 1，构造出一组“坏”预言机。根据交换引理，攻击者的行为在这些坏预言机上基本保持不变，这意味着即使 $\mathbf且 \mathbf{x}$ 不再是有效的解，攻击者仍会输出 $\mathbf{x}$ 。通过计数论证可以得出，这类“坏”预言机的数量远多于“好”预言机，除非攻击者重度查询该答案，否则会导致矛盾。
第二步：低深度攻击者无法重度查询一个正确的答案：
核心贡献在于证明，一个具有有限自适应深度（ $D = o(\log \lambda)$ ）的攻击者，在掌握足够多的关于预言机的信息之前，无法在特定的正确码字上集中足够的查询权重。
- 引导论证（Bootstrapping Argument）： 与单次查询中权重固定的情况不同，自适应查询允许权重依赖于之前的预言机响应。作者引入了一系列增长阈值 $t_0 < t_1 < \dots < t_D$ 。他们识别出一个关键层 $q^*$ ，在该层中，攻击者首次在码字的 $(1-\zeta)n$ 个符号上积累了实质性的权重。
- 重编程策略： 在第 $q^*$ 层之前，攻击者在至少 $\zeta n$ 个符号上尚未达到阈值。作者对这些低权重符号进行重编程。利用阈值的递推关系，他们证明了重编程引起的扰动足够小，使得攻击者在新的预言机下仍然会“重度查询”该码字，尽管此时该码字已不再有效。
- 计数： 通过结合码特的列表可恢复性（限制了与任何给定列表一致的码字数量）以及由不同“好”对生成的坏预言机集合的互斥性，他们证明了攻击者成功地重度查询一个正确码字的概率是微不足道的。

主要贡献与结果

无条件安全性： 本文证明了 Yamakawa-Zandry 协议的（可认证）最小熵属性是无条件的，消除了对未证明的 Aaronson-Ambainis 猜想的依赖。
定理 1.1（非正式描述）： 对于任何查询深度 $D(\lambda) = o(\log \lambda)$ 和最小熵界限 $h_\infty(\lambda) = o(\lambda^{c/2})$ ，该协议满足 $(D, h_\infty)$ -可认证最小熵。这意味着，任何进行 $o(\log \lambda)$ 轮自适应查询并导致验证者以显著概率接受的攻击者，其采样的分布必须具有 $\Omega(\lambda^{c/2})$ 比特的最小熵。
技术局限性： 该证明目前局限于 $o(\log \lambda)$ 个自适应轮数。作者指出，其阈值引导技术要求阈值随轮数呈双指数增长；当轮数达到 $O(\log \lambda)$ 时，阈值将超过计数论证所需的界限。

意义
本文证明了 Yamakawa-Zandry 协议的随机性并非仅仅是其特定算法的人为产物，而是任何针对浅层查询攻击者的成功策略所必须具备的特征。这为 QROM 中的认证随机性提供了更坚实的理论基础，其基础仅在于底层搜索问题的难度以及列表可恢复码的结构性质，而非广泛且未经证实的关于量子加速本质的猜想。这项工作缩小了已知量子查询复杂度与针对有限自适应深度的实际密码协议安全性之间的差距。

类似论文