技术摘要：利用量子方法减少具有长输出的经典安全计算中的通信量

1. 问题陈述

本文探讨了经典密码学在处理输出长度 ($m$) 显著大于输入长度 ($n$) 时，在安全两方计算 (2PC) 和 安全函数采样 (SFS) 方面面临的一个基本局限性。

在经典安全计算中，基于全同态加密 (FHE) 和简洁论证（succinct arguments）的协议通常实现 $O(n + m)$ 的通信复杂度。虽然相对于评估函数的计算复杂度而言这是高效的，但它仍然线性依赖于输出大小 $m$。作者指出，经典不可能结果（特别是借鉴自 [30] 的技术）证明，在恶意设置下，即使是近似安全性，也无法实现通信复杂度独立于 $m$ 的经典协议。

核心研究问题是：量子密码学能否降低安全计算的通信复杂度，使其与输出长度 $m$ 无关？

2. 方法论与技术方法

作者提出了一系列量子密码协议，这些协议实现的通信复杂度与输入长度 $n$ 及安全参数呈多项式关系，但与输出长度 $m$ 无关。该方法论依赖于通过可验证远程状态准备 (RSPV) 的视角来审视该问题，并利用特定的量子原语。

2.1 核心原语：安全函数采样 (SFS)

作者首先定义并解决了安全函数采样 (SFS) 问题。

• 目标： 客户端采样一个随机输入 $x \in \{0, 1\}^n$ 并将 $f(x)$ 发送给服务器。服务器获知 $f(x)$，但无法获知关于 $x$ 的更多信息（即使是恶意的），且客户端无法获知关于服务器内部状态的信息。
• 量子策略： 协议被构建为 RSPV 的一个变体。
  • 玩具协议 (Toy Protocol)： 客户端向服务器发送一个叠加态 $\frac{1}{\sqrt{2}}(|x_0\rangle + |x_1\rangle)$。服务器评估 $f$ 以获得 $\frac{1}{\sqrt{2}}(|x_0\rangle|f(x_0)\rangle + |x_1\rangle|f(x_1\rangle)$，然后返回输入寄存器。客户端进行测量以使状态坍缩。
  • 安全机制： 为了防止恶意服务器存储 $x$，协议采用了 Hadamard 基测试。客户端挑战服务器在 Hadamard 基下进行测量。作者证明，如果服务器以高概率通过这些测试，则其状态必须处于“基-相位对应”（basis-phase correspondence）形式，这意味着它除了 $f(x)$ 所暗示的信息外，无法持有关于 $x$ 的信息。
  • 前向简洁性 (Forward-Succinctness)： 初始构建将客户端到服务器的通信减少为简洁的 $O(n)$。
  • 完全简洁性 (Full Succinctness)： 为了减少服务器到客户端的通信（最初是长输出），作者采用了一种基于简洁知识论证 (succinct arguments of knowledge) 和坍缩哈希函数 (collapsing hash functions) 的编译器。这使得服务器能够证明其持有该关系的有效见证（witness），而无需直接揭示长输出，从而有效地“删除”了长通信。

2.2 向通用两方计算 (2PC) 的推广

基于 SFS 协议，作者构建了适用于双方都有私有输入和输出的通用 2PC 协议。

• 安全函数值准备 (SFVP)： 他们首先改进了 SFS，允许客户端选择输入 $x$（而不是由其采样）。这是通过使用 Yao's garbled circuits (混淆电路) 实现的。客户端使用 SFS 来采样“电路编码”（混淆电路），然后以经典方式发送“输入编码”。
• 恶意客户端安全性： 为了确保针对恶意客户端（可能发送任意输入）的安全，作者引入了 SFVP2。该协议结合了：
  • 统计绑定承诺 (Statistically-binding commitments)。
  • 坍缩哈希函数 (Collapsing hash functions)。
  • 简洁零知识知识论证 (Succinct Zero-Knowledge Arguments of Knowledge, succinct-ZK-AoK)。
  • “切分并选择”（cut-and-choose）放大技术，以确保客户端持有已承诺的有效输入。
• 完整 2PC 协议： 最终的 2PC 协议包括：
  1. 一个 2PC 步骤，用于生成共享随机性和承诺。
  2. Alice 和 Bob 使用 SFVP2 来交换各自函数的混淆电路。
  3. 解密以获取输出。
• 经典信道变体： 作者进一步构建了一个仅使用经典信道的协议。该协议通过假设存在 噪声陷阱无缝函数 (Noisy Trapdoor Claw-Free Functions, NTCF)，用现有的 RSPV 协议（针对特定状态族，如 BB84 态和叠加态）取代了量子通信步骤（发送叠加态）。

2.3 假设

这些协议依赖于以下密码学假设：

• 坍缩哈希函数 (Collapsing Hash Functions)： 一种量子化的抗碰撞哈希函数（例如，由 LWE 或量子随机预言模型所暗示）。
• 噪声陷阱无缝函数 (NTCF)： 特别用于经典信道变体，以实现在无需量子通信的情况下进行 RSPV。
• 单向函数 (One-Way Functions)： 由坍缩哈希函数隐含，用于 Yao's 混淆电路和承诺。

3. 主要贡献与结果

3.1 通信复杂度的量子优势

本文确立了在具有长输出的安全计算的通信复杂度方面的量子优势。

• 定理 1.2 (非正式)： 假设存在坍缩哈希函数，存在一个 SFS 量子协议，其通信复杂度为 $poly(n, 1/\epsilon)$，且与输出长度 $m$ 无关。
• 定理 1.3 & 1.4 (非正式)： 类似的简洁协议对于通用 2PC 同样存在，无论是通过量子通信还是通过经典通信（假设存在 NTCF）。
• 经典不可能结果： 本文证明（定理 1.1），在单向函数的假设下，没有任何经典协议能在恶意设置下实现通信复杂度独立于 $m$ 的 SFS。这证实了量子优势不仅仅是更好的经典算法问题，而是一种根本性的分离。

3.2 协议构建

• SFS 协议： 一个具有近似安全性的完全简洁的 SFS 协议。
• SFVP 和 SFVP2： 用于准备安全函数值的协议，其中输入由客户端选择，并针对恶意服务器和恶意客户端均提供安全性。
• 通用 2PC 协议： 一种用于通用安全两方计算的简洁通信协议。
• 经典信道 2PC： 利用 RSPV 和 NTCF，实现与相同简洁度、仅使用经典通信的协议。

3.3 技术创新

• 对 RSPV 框架的改编： 作者改编了来自 [57] 的框架以处理 SFS 的特定约束，引入了新的“状态形式”（基诚实态、基-相位对应态）来证明完备性。
• 两方关系的简洁测试： 一种新的原语（[8] 中编译器的变体），允许客户端使用简洁通信验证服务器关于关系 $R(x, w)$ 的主张，其中 $x$ 最初是私有的。
• 放大技术： 使用顺序重复和“切分并选择”将近似安全性（preRSPV）放大为完全安全性（RSPV/SFS）。

4. 重要性与主张

本文声称发现了一种新型的量子优势。与以往（如 QKD、不可克隆性或 CVQC）通常侧重于信息论安全或验证的优势不同，这项工作展示了量子力学如何允许在安全计算中实现一种在经典情况下根本无法实现的通信效率。

• 突破输出长度壁垒： 主要意义在于克服了经典安全计算中的“输出长度依赖性”。在经典世界中，为了实现针对恶意攻击者的安全性，必须支付与输出大小成正比的通信成本。本文提出的量子协议绕过了这一点，使通信成本仅取决于输入大小和安全参数。
• 近似安全性： 作者明确指出，其协议实现的是近似安全性（具有误差容限 $\epsilon$）。他们承认实现忽略不计的安全性损失仍是一个开放问题，并且目前的结果仅限于近似安全性。
• 实用性： 本文并未声称具有即时的实用性。作者指出，这些协议依赖于坍缩哈希函数和 NTCF 等假设，且未深入分析量子操作的计算开销。重点在于理论可行性和量子优势的存在。

5. 局限性与开放问题

作者谦逊地概述了几个局限性和开放问题：

• 近似安全性 vs. 忽略不计的安全性： 当前的构建仅实现近似安全性。克服这一点以实现忽略不计的安全性损失是一个挑战。
• 假设： 协议依赖于特定的量子假设（坍缩哈希函数、NTCF）。将这些假设弱化为后量子单向函数或扩展到量子电路是开放的研究方向。
• 通信下界： 作者指出，对于非安全协议，通信量可以小于输入长度。他们质疑安全协议是否可以在不增加安全开销的情况下，接近函数本身的通信复杂度 ($O(CC(f))$)。
• 实际实现： 本文并未提出实验实现方案，而是专注于理论构建和概念证明。

总之，这项工作提供了一个理论框架，证明了量子密码学可以从根本上改变安全计算的通信复杂度格局，特别是在处理具有长输出的函数时，能够实现经典密码学中受限的简洁协议。