技术摘要：可验证且具抗共谋性的多方量子隐私集合运算

1. 问题陈述

隐私集合运算（Private Set Operations, PSO），包括隐私集合求交（PSI）和隐私集合求并（PSU），是安全多方计算（SMC）的基础。虽然存在经典的密码学解决方案，但量子算法（如 Shor 算法）的出现威胁到了当前的数论方案。因此，研究重点已转向量子 PSI（QPSI）。

然而，现有的量子 PSO（QPSO）协议面临显著的局限性：

• 威胁模型： 大多数现有的 QPSI 方案假设存在半诚实的受信第三方（TP），或者依赖于 TP 不会与任何参与者共谋的假设。
• 抗共谋性： 先前的多方 QPSI（MP-QPSI）协议通常无法抵御 TP 与部分参与者之间的共谋，或者只能容忍单个参与者的损坏。
• 可验证性： 许多方案缺乏验证 TP 是否正确执行了预设量子电路的机制，这使得系统容易受到恶意偏差的影响。

2. 方法论

作者提出了一种结合了**可验证量子全同态加密（vQFHE）与阈值全同态加密（TFHE）**的多方量子隐私集合求交（MP-QPSI）协议。该协议在一个涉及 $n$ 个持有数据的参与者、一个强大的量子 TP 以及一个受信权威（TA）的模型中运行。

核心组件

1. 阈值密钥管理 (TFHE)：

   • 解密密钥通过 $(t, n)$-阈值秘密共享方案在 $n$ 个参与者之间进行分配。
   • 解密需要至少 $t$ 个参与者的协作。这确保了无论是损坏的参与者子集，还是 TP 与少于 $t$ 个参与者的共谋，都无法恢复密钥或获取私有输入。

2. 可验证量子评估 (vQFHE)：

   • 协议利用 TrapTP 构建（源自 [ADS+17]）作为 vQFHE 层。
   • 加密： 参与者使用 CSS 码将私有集合编码为量子态，附加陷阱比特（$|0\rangle$ 和 $|+\rangle$），应用随机置换，并使用量子一次性密码（QOTP）对结果进行掩码。QOTP 的密钥在 TFHE 下加密，并通过消息认证码（MAC）进行认证。
   • 评估： TP 对加密的量子态执行多方 AND 电路（$C_{\text{AND}}$）的同态评估。TP 同态地更新加密的 QOTP 密钥，并消耗“小工具”（gadgets，即魔术态）来处理非 Clifford (T) 门，遵循花管模型（garden-hose model）。
   • 验证： TP 生成一个经典传输日志（transcript）。参与者和 TA 通过检查 MAC、门阵列以及陷阱码测量值来验证此日志，以确保 TP 没有偏离目标电路。

3. 协议流程：

   • 阶段 1（准备）： TA 生成密钥，采样置换，准备 T 门小工具，并分发秘密份额。
   • 阶段 2（加密）： 参与者将集合编码为量子态，应用陷阱和 QOTP，并将加密后的状态和密钥发送给 TP。
   • 阶段 3（评估）： TP 执行同态 $C_{\text{AND}}$ 电路，更新密钥并记录传输日志。
   • 阶段 4（验证与解密）： 参与者执行经典验证（MAC、门和传输日志检查）以及阈值解密以恢复 QOTP 密钥。TA 执行量子验证（陷阱检查）并解密最终状态，以广播交集结果。

3. 核心贡献

• 多方扩展： 作者通过将 vQFHE 与 TFHE 相结合，将其扩展到多方场景，使 $n$ 个参与者能够在不泄露私有数据的情况下计算集合交集。
• 抗共谋性： 与先前的 QPSI 方案不同，本协议能够抵御 TP 与最多 $t-1$ 个参与者的共谋。阈值机制确保了只要损坏的参与者人数少于 $t$，密钥和私有输入就是安全的。
• 针对恶意 TP 的可验证性： 协议提供了语义安全性和可验证性。通过结合经典传输验证和量子陷阱码检查，它可以检测出恶意 TP 是否偏离了预设电路（例如，修改门阵列或输出）。
• 模块化框架： 该构建被呈现为一个模块化框架。作者展示了如何：
  • 降低电路复杂度（例如，使用 CCCZ 门代替 $C_nX$ 以减少 T 门数量）。
  • 通过将 AND 电路替换为通过开放控制操作实现的 OR 电路，将功能扩展到量子隐私集合求并（QPSU）。
  • 更换底层的 vQFHE 实现，以实现不同的效率/安全性权衡。

4. 结果与分析

• 正确性： 作者使用 IBM 量子平台和 Qiskit 验证了逻辑多方 AND 门。模拟确认了输出分布符合逻辑 AND 操作的理想真值表。
• 安全性证明：
  • 隐私性： 证明了协议对于 TP 在量子态方面具有信息论安全性（由于 QOTP 和最大混合态），并在经典数据方面具有计算安全性（由于 TFHE 和 MAC）。
  • 共谋： 定理 3 证明，任何规模小于 $t$ 的损坏参与者组成的联盟与 TP 共谋，也无法获得除交集结果之外的信息。
  • 可验证性： 在语义安全模型 ($\kappa$-SEM-VER) 下，证明了协议是可验证的。混合论证表明，TP 的任何偏差都会以极高的概率被检测到。
• 性能：
  • 通信复杂度： 量子通信成本为 $O(n\kappa L)$，其中 $n$ 是参与者数量，$\kappa$ 是安全参数，$L$ 是集合大小。
  • 对比： 与现有方案（如 [SMZ+15], [ZLS+20], [HZZ24]）相比，所提协议是唯一支持具备 PSI 和 PSU 能力的多方场景，同时提供对 TP-参与者共谋及恶意 TP 行为的抵抗能力的方案。

5. 意义与主张

本文声称通过解决困扰现有 QPSI 方案的“TP-参与者共谋”差距，在量子安全计算领域取得了重大进展。

• 鲁棒性： 通过集成 TFHE，该协议实现了此前在量子 PSI 中缺失的抗共谋水平，确保了即使 TP 和部分参与者串通时依然安全。
• 信任最小化： 可验证性层使得系统即使在 TP 是恶意的情况下也能安全运行，从而消除了对 TP 诚实性的需求，仅需对其计算能力有要求。
• 灵活性： 模块化设计允许该框架被适配用于不同的集合运算（并集、基数）以及针对不同的硬件约束进行优化（例如，减少 T 门复杂度）。

作者承认，虽然该协议提供了强大的安全性，但它继承了基于 TrapTP 的 vQFHE 所带来的经典开销。建议未来的工作探索无小工具（gadget-free）的 T 门处理，并进一步优化以降低经典通信成本。