## 论文信息
- **标题**: Quantum Rewinding for IOP-Based Succinct Arguments
- **作者**: Alessandro Chiesa, Marcel Dall’Agnol, Zijing Di, Ziyi Guan, Nicholas Spooner
- **机构**: EPFL; Princeton University; Cornell University
- **日期**: 2024-11-08
## 摘要
该论文分析了基于交互式 Oracle 证明（IOPs）和向量承诺（VC）的简洁交互论证在后量子环境下的安全性，并证明了当 VC 满足 collapsing binding 时，交互式 BCS 转换（IBCS 协议）在标准模型中对量子对手具有可证安全性。
## 1. Collapse Binding 定义
向量承诺方案 VC 被称为 collapsing binding，当且仅当对于所有量子可分辨器 $\mathcal{D}$ 和多项式多次查询限制 $q$, 对抗者 $\mathcal{A}$，在以下两种实验 $\mathsf{Collapse}$ 与 $\mathsf{Measure}$ 中测量或不测量承诺密钥后的输出分布相差可忽略：
$
\bigl|\Pr[\mathsf{Collapse}^{\mathcal{A},\mathcal{D}}(1^\lambda)=1] - \Pr[\mathsf{Measure}^{\mathcal{A},\mathcal{D}}(1^\lambda)=1]\bigr| \le \epsilon_\mathsf{VCCollapse}(\lambda)\,.
$
## 2. IBCS 协议定义
给定一个公共随机的 $k$ 轮交互式 Oracle 证明 IOP $(P,V)$ 和 collapsing VC，IBCS 协议的流程如下：
1. **Commit 阶段**: 证明者对 IOP 中每轮对话中的所有查询答案 $\{a_i\}$ 使用 VC 生成承诺 $\mathsf{cm}_i$ 并发送；
2. **Challenge 阶段**: 验证者选取随机挑战 $\{r_i\}$ 并发送；
3. **Open 阶段**: 证明者对所选查询通过 $\mathsf{Open}$ 返回证明 $\pi_i$；
4. **Check 阶段**: 验证者使用 $\mathsf{VC.Check}(pp,\mathsf{cm}_i,Q_i,a_i,\pi_i)$ 逐轮检查。
该协议的经典安全性和通信复杂度已在 [BCS16] 中分析。
## 3. 混合体证明框架 (Hybrids)
为了证明知识健全性，通过定义一系列混合体 $H_0,\dots,H_k$，将初始协议 $H_0$ 转换到只依赖于 VC 开放的协议 $H_k$。关键引理（Lemma 4.1）给出相邻混合体间价值差的上界：
$
\mathrm{val}(H_{\ell-1}) \le \mathrm{val}(H_\ell) + \epsilon_\mathsf{VC}(\lambda,l_{\max},q_{\max},t_\mathsf{VC})
+ \ell \cdot \epsilon_\mathsf{VCCollapse}(\lambda,l_{\max},q_{\max},t_\mathsf{VC})
+ \frac{\epsilon}{k}\,.
$
迭代得：
$
\mathrm{val}(H_0)\le \mathrm{val}(H_k) + k\Bigl(\epsilon_\mathsf{VC}(\dots)
+ \ell\cdot\epsilon_\mathsf{VCCollapse}(\dots)\Bigr) + \epsilon\,.
$
## 4. 量子重绕 (Quantum Rewinding) 关键步骤
论文通过三个 Claim 来分别界定混合体转换的影响：
### Claim 4.5: 重绕不降低成功率
对每轮 $\ell$, 额外的 rewinding 操作引入的失败概率至多 $\frac\epsilon{2k}$：
$
\mathrm{val}(H_{\ell,0}) \le \mathrm{val}(H_{\ell,1}) + \frac{\epsilon}{2k}\,.
$
### Claim 4.6: 测量影响可由 Collapse Binding 控制
在第 $\ell$ 轮测量 oracle 答案带来的成功率下降受 collapsing binding 约束：
$
\mathrm{val}(H_{\ell,1}) \le \mathrm{val}(H_{\ell,2}) + \ell\cdot \epsilon_\mathsf{VCCollapse}(\lambda,\dots)\,.
$
### Claim 4.7: Open 阶段与位置绑定
证明者在第 $\ell$ 轮可能开已有位置或遗漏位置，两种情况分别受 position binding 和重绕次数 $T$ 控制，总体误差上界为
$
\mathrm{val}(H_{\ell,2}) \le \mathrm{val}(H_{\ell,3}) + \epsilon_\mathsf{VC}(\lambda,\dots) + \frac{\epsilon}{2k}\,.
$
## 5. 知识健全性误差界
结合上述不等式，知识健全性错误总和满足：
$
\kappa_\mathsf{IBCS} \le \epsilon + k\Bigl(\epsilon_\mathsf{VC}(\dots) + \ell\cdot\epsilon_\mathsf{VCCollapse}(\dots)\Bigr)\,,
$
其中 $\epsilon$ 是 IOP 的 soundness error, $\kappa$ 是相应 extractor 的 knowledge soundness error。
## 6. 协议效率
在存在线性时间 collapsing hash 函数的假设下，IBCS 协议可以在 $O(\log|C|)$ 轮内完成，并达到通信复杂度 $poly(\lambda,\log|C|)$，是已知 asymptotic 最优的后量子简洁论证方案之一。