技术摘要：实验性非对称相对论零知识证明及其无条件安全性

问题陈述

零知识证明（ZKP）对于建立数字经济（如加密货币和智能合约）中的信任与隐私至关重要。然而，经典的 ZKP 协议依赖于计算假设（例如单向函数的存在），这使其容易受到未来量子攻击的影响。虽然量子 ZKP 提供了一种潜在的替代方案，但它们面临着显著的实现障碍，包括由于不可克隆定理导致的量子重写（rewinding）复杂化问题，以及无条件安全的量子比特承诺（bit commitment）的不可能性。

相对论 ZKP（RZKPs）通过利用狭义相对论原理（特别是无信号原则）取代计算假设，从而成为了一种解决方案。最近的一项突破展示了一种针对图三着色问题的对称 RZKP。然而，该对称协议在确保量子完备性（quantum soundness）（即针对共享量子纠缠的证明者进行安全性保障）时，面临着极高的效率瓶颈。为了实现量子完备性，对称协议需要 $O(|E|^4)$ 的轮数复杂度（其中 $|E|$ 是边的数量），这导致在处理现实规模的图时，运行时间过长且随机性成本巨大。

方法论

作者提出并实验实现了一种非对称相对论 GMW ZKP 协议，旨在克服以往对称方法中的效率限制，同时保持对量子相关证明者的无条件安全性。

协议设计

该协议涉及两个空间分离的证明者-验证者对（$P_1-V_1$ 和 $P_2-V_2$），并在 $m$ 个交互轮中运行，以证明一个图 $G(V, E)$ 是三可着色的，而不泄露着色信息。

1. 准备阶段： 证明者 $P_1$ 和 $P_2$ 共享一个随机颜色置换 $\pi$ 和一组随机值 $B = \{b_k\}$。
2. 查询阶段： 验证者 $V_1$ 向 $P_1$ 发送随机查询 $X = \{x_k\}$。
3. 承诺阶段： $P_1$ 计算承诺 $A = \{a_k\}$，其中 $a_k = x_k \cdot y_k - b_k$（其中 $y_k$ 为颜色）并将其发送给 $V_1$。
4. 挑战阶段： 验证者 $V_2$ 选择一条随机边 $C = \{i, j\}$ 并将其发送给 $P_2$。
5. 揭示阶段： $P_2$ 向 $V_2$ 揭示颜色 $Y(C)$ 及相应的数值 $B(C)$。
6. 检查阶段： 验证者检查相对论约束（通过验证时间延迟 $|t_1 - t_4| < \tau$ 和 $|t_2 - t_3| < \tau$ 来确保 $P_1$ 与 $P_2$ 之间不存在信号传递，其中 $\tau = d/c$）以及逻辑一致性（确保颜色各不相同且与承诺匹配）。

理论分析

作者解决了量子完备性的挑战。在经典协议中，比特承诺是强绑定的，但在相对论性比特承诺中，仅保证“和绑定”（sum-binding）。作者证明了恶意量子证明者在无效边上成功作弊的概率受限于非局域 CHSH$_{Q(2)}$ 博弈的量子值。通过将协议的完备性误差与该博弈联系起来，他们推导出了量子完备性误差 $\delta$ 的严格上界。

实验实现

团队使用以下设备实现了一个概念验证实验：

• 硬件： 用于低延迟处理的现场可编程门阵列（FPGA）以及用于时间同步的高精度 GPS 时间同步服务器（配备原子钟）。
• 设置： 两个证明者-验证者对之间的距离为 300 米（对应于时间间隔 $\tau = 1000$ ns）。
• 图结构： 一个具有 $|V| = 588$ 个顶点和 $|E| = 1097$ 条边的三可着色图。
• 执行： 实验在约 0.22 秒内完成了所有必要的交互轮。

核心贡献

1. 高效的非对称协议： 作者设计了一种非对称相对论 GMW ZKP，将轮复杂度从之前量子安全对称协议中的 $O(|E|^4)$ 降低到了 $O(|E|)$。这是通过在 GMW 框架内使用双证明者相对论性比特承诺实现的，使得证明和一致性检查可以在单轮中同时进行。
2. 量子完备性证明： 他们通过将纠缠证明者的作弊概率与非局域 CHSH$_{Q(2)}$ 博弈联系起来，提供了严谨的量子完备性证明，在不依赖计算假设的情况下建立了完备性误差的上界。
3. 实验实现： 他们成功在 300 米的间隔下执行了该协议，证明了所需的运行时间和随机性成本对于实际部署是可行的。

结果

• 轮复杂度： 协议需要 $m = 2k|E|$ 轮以达到 $e^{-k}$ 的完备性误差。对于实验参数（$|E|=1097, k=100$），这产生了大约 $2.2 \times 10^5$ 轮。
• 运行时间： 整个实验在 0.22 秒内完成。相比之下，之前的量子安全对称协议 [23] 要达到相同的安全水平，处理该图大约需要 $6.72 \times 10^4$ 年。
• 随机性成本： 实验的总随机性成本为 430.81 MB。对称协议 [23] 完成相同任务则需要大约 $5.92 \times 10^9$ GB（5.92 EB）。
• 安全性： 时间差 $|t_1 - t_4|$ 和 $|t_2 - t_3|$ 一致测量在 1000 ns 阈值以下，即使考虑到 GPS 同步误差，也满足了相对论无信号约束。

重要性与主张

论文声称，这项工作展示了将狭义相对论与量子理论相结合的强大潜力，从而创建出无需依赖计算硬度假设、且能抵御量子攻击的无须信任（trustless）密码系统。

关于其重要性的关键主张包括：

• 实际可行性： 将轮复杂度从 $O(|E|^4)$ 降低到 $O(|E|)$，将 RZKP 从理论构想转变为适用于合理规模图的实际可部署技术。
• 无条件安全性： 该协议仅基于无信号原则提供量子完备性和零知识属性，使其对未来的量子计算进展具有鲁棒性。
• 可扩展潜力： 虽然非对称特性使得一个证明者-验证者对（$V_1-P_1$）承担了更高的计算负载，但作者认为这种权衡对于实现可行的运行时间是必要的。他们指出该协议可以在智能手机等日常设备上实现。
• 未来应用： 作者强调了该框架在对隐私敏感的领域（如区块链、智能合约、匿名电子投票和在线拍卖）中的潜在应用。他们还提到将该框架扩展到用于身份验证的知识零知识证明（ZKPoK）的可能性。

作者对扩展性挑战保持谦逊，承认在光纤网络中实际部署仍面临诸如验证证明者精确位置以及管理计算负载等障碍，并将其视为未来研究的开放性问题。