⚛️ quantum physics

Tight Parallel Repetition for Private-Coin Arguments

在假设同态加密存在的条件下，本文证明了在后量子设定下，交互式论证的并行重复对于标准验证者和阈值验证者均能实现紧致的指数级健全误差降低，从而使得构建首个具有常数轮次、且具有可忽略误差的 QMA 简洁论证成为可能。

原作者： Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner

发布于 2026-10-01

📖 1 分钟阅读🧠 深度阅读

原作者： Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner

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

在密码学领域，存在着一种持续的张力，即安全性与效率之间的权衡。想象这样一个系统：用户想要证明自己知道某个秘密——比如密码或私钥——而无需实际泄露该秘密本身。这就是交互式证明（interactive proofs）的领域。在这些系统中，证明者试图通过一系列问题与回答来使验证者相信其掌握了知识。如果证明者是诚实的，他们会轻松成功；如果他们试图欺骗，系统设计旨在使他们成功的概率变得极小。为了让这种概率变得微乎其微，密码学家经常使用一种称为“并行重复”（parallel repetition）的技术。与其只运行一次测试，不如同时运行许多个测试副本。其逻辑很简单：如果一个作弊者在单轮测试中成功撒谎的机会是百分之一，那么在并行运行一百轮时，他在所有轮次中都成功撒谎的机会应该在天文数字般地低。

然而，只有当验证者的问题是随机且公开的时，这种逻辑才完全成立。当验证者将问题保密直到被提问的那一刻时——这种设置被称为“私有硬币协议”（private-coin protocol）——情况就会变得复杂得多。一个聪明的证明者可以跨不同的并行轮次对他们的答案进行关联，利用从一轮中获得的信息来帮助他们在另一轮中进行欺骗，从而有效地抵消了重复本应提供的安全提升。几十年来，研究人员一直难以证明在并行重复这些私有硬币测试时，确实能提高其安全性，尤其是当证明者可能正在使用量子力学中那些奇特且反直觉的定律时。

一组研究人员现在为一类特定且强大的密码学工具解决了这个长期存在的问题。他们证明了，通过将这些私有硬币测试封装在一种称为“同态加密”（homomorphic encryption）的特殊加密技术中，并行重复可以如预期般发挥作用，即使是面对量子对手也是如此。同态加密是一种允许计算机在不解密的情况下对加密数据进行计算的方法。在这种新方法中，验证者以加密形式发送其秘密问题。证明者无法读取问题，必须在数据仍处于锁定状态的情况下计算出答案。研究人员证明，这种特定的设置强制任何欺骗策略都以数学上紧致且可预测的速率失败。他们的工作表明，安全误差以最优速率下降，这意味着无论攻击者使用的是经典计算机还是量子计算机，系统都会随着每个新增的并行副本而变得呈指数级难以破解。

这一发现的意义不仅在于改进单个协议。它为构建用于 QMA 的常数轮简洁论证（constant-round succinct arguments）提供了坚实的基础。QMA 是一个著名的复杂度类 NP 的量子等价物，它处理的是那些解可以被快速验证但可能极难寻找的问题。此前，创建针对这些量子问题的有效且安全的证明需要极其强大且未经证实的密码学假设。而这种新方法仅依赖于“量子同态加密”的存在，这是一个已被其他成熟数学问题所支持的概念。这意味着，实现量子计算的安全、高效验证已触手可及，且所依赖的假设要合理且被广泛接受得多。

研究人员通过开发一种新的方法来分析面对这些加密挑战时的欺骗性证明者的行为，从而实现了这一目标。在经典计算中，一种常用的分析此类系统的技巧是“回溯”（rewinding）证明者：运行测试，观察证明者是否成功，然后将时间回溯到另一个路径尝试。这种技巧在量子世界中并不适用，因为测量量子系统会改变它，而且你无法在不破坏信息持有量的情况下简单地回溯量子态。该团队通过使用“量子奇异值变换”（quantum singular value transformation）绕过了这一障碍。他们没有进行回溯，而是操纵量子态，使其有效地将证明者的策略旋转回起始点，从而在不破坏量子相干性的情况下测试不同的场景。这使得他们能够证明，加密方案成功防止了证明者在并行轮次之间对答案进行关联。

结果是一个这样的系统：验证者可以确信，如果证明者通过了一定阈值的轮次，他们几乎可以肯定是在说实话。研究人员表明，即使证明者被允许使用“阈值策略”（即他们只需要在并行副本中的一定数量上取得成功，而非全部成功），这一结论依然成立。这种灵活性对于现实应用至关重要，因为在这些应用中，要求每一项都完美成功可能过于苛刻。该证明是严谨的，适用于任何具有多项式轮数的协议，确保了随着交互复杂度的增加，安全性不会下降。

通过建立这些紧致界限，这篇论文填补了我们对量子密码学理解中的空白。它证实了同态加密与并行重复的结合是放大安全性的强大工具。这不仅仅是一个理论上的好奇心；它为用户以高置信度和低开销验证复杂量子计算铺平了道路。这项工作表明，未来安全的量子通信不需要魔法或未经证实的奇迹，而是需要将已知的密码学原则谨慎地应用于量子领域。研究人员提供了一条清晰的路径，表明只要拥有正确的工具，我们就能构建出即使面对最先进的量子攻击也能保持安全的系统。

技术摘要：私有币参数下的紧致并行重复

1. 问题陈述

并行重复（Parallel repetition）是用于通过执行多个独立的协议副本以放大证明系统可靠性的基本技术。虽然顺序重复（Sequential repetition）可以直观地降低可靠性误差，但并行重复要微妙得多，因为不诚实的证明者可以在所有执行过程中关联其策略，从而可能阻止接受事件保持独立。

对于公有币交互式论证（其中验证者的消息是均匀随机的），并行重复已被充分研究：它在针对经典和量子多项式时间证明者时，都能实现可靠性误差的指数级降低。然而，对于私有币论证（其中验证者的消息依赖于秘密随机性），情况则完全不同。Bellare, Impagliazzo, 和 Naor [BIN97] 的先前工作表明，通用的私有币论证在进行并行重复后，即使是在面对经典对手时，其可靠性也不一定会降低。

为了在经典设定中规避这一负面结果，人们开发了两种通用的方法：随机终止法 [Hai09] 和同态加密（HE）法 [CL10]。HE 方法通过让验证者对其消息进行加密，并让证明者对这些消息进行同态计算，将私有币协议转换为一种“计算可模拟”的协议。

差距所在： 虽然 HE 方法已知对经典证明者有效，但目前尚不清楚是否能在后量子设定（即不诚实的证明者是量子多项式时间算法）中实现紧致的并行重复界限。将先前的经典归约扩展到量子设定非常困难，因为：

经典归约通常依赖于重写（Rewinding）（运行一个证明者，检查结果，然后将输入修改后重写到之前的状态），由于无克隆定理以及跨重复之间的潜在纠缠，这在量子态上通常是不可行的。
标准的 HE 语义安全性确保了密文的可区分性，但经典的证明通常通过使用虚拟密文将证明者的状态置于一个“有利”事件上，然后切换到真实的密文。目前尚不清楚由此产生的量子态是否仍然适用于真实密文的后续过程。

2. 方法论与技术路径

作者提出了一种全新的归约策略，通过利用**量子奇异值变换（QSVT）**和相干状态切换技术来避免标准的重写。

2.1 同态加密 (HE) 转换

作者遵循 Chung 和 Liu [CL10] 的转换方法。给定一个私有币交互式论证 $(P, V)$ ，他们构建了一个加密协议 $(\hat{P}, \hat{V})$ ：

验证者 $\hat{V}$ 模拟 $V$ ，在每一轮中都在一个新的 HE 密钥下对其消息进行加密。
证明者 $\hat{P}$ 在加密的消息上同态地评估 $P$ 的策略。
至关重要的是，针对后量子设定，作者使用了“对经典友好”的量子同态加密（QHE）（即对经典消息的解密仍为经典），以确保验证者保持高效。

2.2 归约策略

该论文的核心是一个归约过程，它将针对加密协议的 $k$ 重并行重复的不诚实证明者 $B$ ，转化为针对单副本原始协议的不诚实证明者 $A$ 。

经典分析（基准）：
作者首先为经典设定建立了一个新的、更紧致的分析。归约法在一个坐标（例如索引 $i$ ）中嵌入一个外部验证者，并在内部模拟其余 $k-1$ 个坐标。

相关性消除： 遵循 [CHS05, CL10]，归约包含一个预处理步骤，以确保嵌入坐标中的证明者成功与其它的坐标不呈负相关。
虚拟消息 vs 真实消息： 归约最初在嵌入坐标中使用加密的虚拟消息 (0)。它采样内部验证者的随机性，直到证明者接受其余 $k-1$ 个副本。然后，它尝试将虚拟加密“交换”为真实的验证者消息。

量子分析（创新点）：
将此扩展到量子证明者需要克服无法重写的难题。

相干后选择（Coherent Post-Selection）： 与在经典中采样随机性并丢弃失败的情况不同，归约将嵌入坐标的加密随机性准备在叠加态中。它相干地测量内部验证者是否接受，从而有效地“后选择”在证明者于 $k-1$ 个内部副本上成功的事件。
利用 QSVT 进行状态旋转： 挑战在于，在后选择之后，证明者的状态与加密寄存器发生了纠缠。为了将密文从 $|Enc(0)\rangle$ $∣ E n c (0)⟩$ 切换到 $|Enc(q)\rangle$ $∣ E n c (q)⟩$ （其中 $q$ $q$ 是真实消息），作者采用了量子奇异值变换（QSVT）。
- 他们定义了两个子空间： $\mathcal{A}$ （内部验证者接受的状态）和 $\mathcal{B}$ （加密寄存器持有 $|Enc(0)\rangle$ 的状态）。
- QSVT 允许归约将状态从接受子空间 $\mathcal{A}$ 旋转回干净的加密子空间 $\mathcal{B}$ ，从而有效地“撤销”了由后选择引起的纠缠。
密文交换： 一旦状态被旋转回 $\mathcal{B}$ ，归约会将 $|Enc(0)\rangle$ 与 $|Enc(q)\rangle$ 进行交换。随后，它应用逆 QSVT 将状态旋转回接受子空间 $\mathcal{A}$ ，此时已以真实消息为条件。
不可区分性： 作者证明了这一过程在忽略不计的误差范围内保持了证明者的状态。他们利用 HE 的语义安全性来论证，即使归约执行了相干操作，证明者也无法区分这种交换。一个关键的技术引理（引理 4.3）表明，如果一个区分器无法区分加密随机性的分布，那么它也无法区分经过基于 QSVT 的交换过程后的最终量子态。

2.3 阈值验证者

结果被推广到了阈值验证者，即当 $k$ 次执行中至少有 $t$ 次接受时，验证者才接受。归约通过适配“相关性降低”策略来处理证明者在子集执行中成功的案例，确保界限对任何阈值 $t$ 均成立。

3. 核心贡献与结果

3.1 紧致并行重复定理

主要结果（定理 1.1）确立了：对于任何具有可靠性误差 $\epsilon$ 的私有币交互式论证，其 HE 转换后的 $k$ 重并行重复将可靠性误差降低至：

直接积 ( $t=k$ )： $\epsilon^k + \text{negl}(\lambda)$ 。
阈值 ( $t$ )： $\Pr[\sum_{i=1}^k X_i \ge t] + \text{negl}(\lambda)$ ，其中 $X_i$ 是独立同分布的 Bernoulli( $\epsilon$ ) 变量。

这些界限是信息论意义上紧致的（在忽略不计的因子内），并且在面对量子多项式时间 (QPT) 证明者时依然成立。

3.2 对先前工作的改进

后量子安全性： 不同于以往仅限于经典证明者的结果，这项工作实现了针对量子证明者的紧致界限。
更紧致的界限： 新的分析改进了即使在经典设定中已知的界限（例如 [CL10, HS11]），特别是对于阈值验证者，之前的界限会随轮数增加而退化。
轮数无关性： 阈值结果提供了一个独立于协议轮数复杂度的界限，只要轮数为多项式级别。

3.3 对 QMA 的应用

作为直接推论（推论 1.2），作者构造了第一个具有极小完备性和可靠性误差的常数轮简洁 QMA（Quantum Merlin-Arthur）论证。

假设： 该构造仅依赖于量子同态加密 (QHE) 的存在，而 QHE 是由容错学习误差问题 (LWE) 的后量子硬度所暗示的。
意义： 先前的此类论证构造需要比 LWE 更强的假设，即后量子不可区分混淆 (iO)。

4. 意义与主张

本文声称解决了关于私有币论证在量子设定下并行重复的一个长期悬而未决的问题。通过开发一种利用 QSVT 实现的相干替代方案来取代经典的重写技术，作者证明了同态加密可以有效地“打破”不诚实的证明者在并行执行中可能利用的相关性。

其意义在于：

基础密码学： 确立了即使在面对量子对手时，并行重复对私有币协议也是紧致有效的，这一结果此前因缺乏量子重写技术而被认为难以实现。
效率： 在标准密码学假设（通过 QHE 实现的 LWE）下提供了常数轮的简洁 QMA 论证，无需使用更为复杂的 iO 假设。
方法论进步： 引入了一种技术（通过 QSVT 实现的相干密文交换），该技术可能在需要无需完整重写即可进行状态操作的量子密码学场景中具有更广泛的应用。

作者对“忽略不计”的加性误差的必要性保持谦逊，指出信息论下界表明此类因子很可能是必要的 [DJMW12]。他们还指出，他们针对非均匀对手的归约需要多个副本的证明者初始状态，他们认为这对于在量子设定中增加成功概率是必要的。