⚛️ quantum physics

Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing

本文提出了一种具有显式基数测试功能的量子多方阈值隐私集合求交协议，该协议利用基于旋转的单光子构建和密码学原语，使第三方能够在不解释结果的情况下进行测量，同时仅安全地揭示交集大小是否满足阈值。

原作者： Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

发布于 2026-06-29

📖 1 分钟阅读🧠 深度阅读

原作者： Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

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

想象一群朋友，他们每个人都有一份秘密的电影最爱清单。他们想知道：“我们是否所有人都在至少三部电影上达成了一致？”

如果答案是是，他们想看到那三部电影的清单。
如果答案是否，他们想知道什么都不要知道——甚至连他们实际有多少部共同电影也不想知道。

这就是阈值隐私集合求交（Threshold Private Set Intersection, TPSI）问题。该论文提出了一种新的解决方法，利用量子力学（具体来说是单光子）和巧妙的数学，确保即使是运行实验的人也无法作弊或窥探秘密。

以下是该论文解决方案的拆解说明，将其分解为简单的概念：

1. 旧方法的缺陷

在以往的量子尝试中，小组依赖于一个“裁判”（称为第三方或 TP）来计数匹配项。

缺陷： 裁判会统计匹配的数量，将该数字与阈值（例如“是否等于 3”）进行比较，然后决定告诉小组什么。
风险： 这意味着裁判看到了匹配的确切数量。如果小组只有 2 个匹配项，裁判就会知道这一点。但小组只想知道他们是否达到了标准（3 个或更多），而不是确切的计数。这就像是问法官：“被告是否有罪？”但法官在回答之前，必须先写出一份完整的犯罪传记。

2. 新方案：“蒙面裁判”

作者创建了一个协议，在这个协议中，裁判执行测量，但在关于结果的含义上是被蒙住双眼的。

设置：秘密代码

在实验开始前，参与者（朋友们）之间达成了一个秘密代码。他们还将真实的电影列表与一些“诱饵”假列表（锚点）混合在一起，裁判并不知道这些锚点。

隐藏密钥： 他们使用秘密密钥来打乱电影的位置。对裁判来说，这些列表看起来就像随机噪声。
翻转（The Flip）： 他们约定了一个秘密的“翻转”（就像一个秘密握手）来改变结果的含义。如果灯光显示“开”，根据这个秘密翻转，它实际上可能代表“关”。

量子之舞（旋转）

实验使用光子（光的粒子）作为信使。

裁判准备好一列光子，并将它们发送给第一个朋友。
朋友 1 查看他们的秘密列表。如果他们在特定位置拥有一部特定的电影，他们会对光子进行微小的“自旋”（旋转）。如果没有，则保持原样。他们还会添加一个只有他们和裁判知道的秘密“掩码”旋转。
链式传递： 光子流向朋友 2，然后是朋友 3，以此类推。每个朋友都会根据自己的秘密列表增加自己的自旋。
返回： 光子回到裁判手中。

“隐藏标签”的魔力

当光子返回时，裁判移除自己的掩码并测量光线。

结果： 裁判看到的是“相同”或“相反”的光模式。
关键点： 由于朋友们约定的秘密“翻转”，裁判无法理解这个模式的含义。由于存在一个只有朋友们知道的秘密位（bit），一个“相同”的结果可能意味着“匹配”或“不匹配”。裁判拥有数据，但这些数据对他们来说只是乱码。

3. 最终检查：“盲选”

现在，朋友们和裁判需要决定：“我们达到阈值了吗？”而不让裁判得知确切的计数。

数学技巧（OLE）： 他们使用一种称为**不经意线性评估（Oblivious Linear Evaluation）**的密码学工具。你可以把它想象成一个安全的计算器，裁判输入他们的“乱码”数字，而朋友们输入他们的“秘密密钥”。
混淆电路（Garbled Circuit）： 他们运行一个微型的、锁定的计算机程序（混淆电路）。该程序会在内部进行加总。
输出： 程序仅输出一个比特位：1（是，我们有足够的匹配项）或 0（否，我们没有）。
- 如果答案是 1，朋友们揭示秘密密钥以解码裁判的“乱码”模式，从而看到匹配的电影。
- 如果答案是 0，他们将所有东西丢弃。裁判永远不会得知确切的匹配数量，只知道它没有达到要求。

4. 为什么这是安全的（安全性）

论文证明了三个主要的安全性点：

没有窃听者： 如果有人试图拦截光子，那些“诱饵”灯（窃听者不知道的）会发生变化，从而提醒所有人线路被监听了。
裁判是诚实但好奇的： 即使裁判试图作弊或使用高级量子技巧来猜测秘密，数学也能确保他们无法区分真实的匹配项和噪声。他们对数据的含义确实是盲目的。
朋友之间无法作弊： 即使两个朋友联手监视第三个朋友，他们也无法通过这种方式获取第三个朋友的列表，因为有秘密掩码和光子旋转方式的存在。

5. “玩具模型”证明

为了展示这确实可行，作者使用 IBM 的量子计算机模拟器（Qiskit）构建了一个小型模拟。

他们模拟了 3 个朋友及其较小的列表。
他们加入了“噪声”（模拟现实世界的缺陷）。
结果： 系统正确识别出朋友们有 2 部电影共同，这低于他们的阈值（3 部）。系统显示“否”，且朋友们没有学到任何东西。
他们随后展示了，如果他们有 3 个匹配项，系统将正确显示“是”并揭示清单。

总结

这篇论文介绍了一种**量子多方阈值 PSI（Quantum Multi-Party Threshold PSI）**协议。

目标： 仅当小组规模足够大时，才揭示共享的秘密。
创新点： 它将测量的行为（由裁判执行）与解释的行为（由小组执行）分离开来。
机制： 它利用旋转的光子和秘密“翻转”来创建裁判无法读取的“隐藏标签”，从而确保确切的匹配计数保持私密。
结果： 小组仅能得知关于阈值的简单“是/否”结论，并且只有在结果为“是”时，他们才能看到实际的共有项。

技术摘要：具有显式基数测试的量子多方阈值隐私集合求交

问题陈述
隐私集合求交（PSI）允许各方在不泄露非交集元素的情况下计算其私有集合的交集。阈值 PSI（TPSI）扩展了这一概念，即仅当交集的基数（元素个数）达到或超过公开阈值 $\tau$ 时，才揭示交集。虽然存在经典的 TPSI 协议，但现有的量子 TPSI 协议（例如 [MSD+24, LZY+26, WLS+26]）通常依赖于第三方（TP）进行最终测量并解释结果。在这些方案中，TP 恢复出精确的交集基数，然后将其与 $\tau$ 进行比较。这种方法偏离了理想的 TPSI 范式，因为它将精确的基数统计量暴露给了 TP，而不是仅揭示一比特谓词 $\mathbb{1}[|\bigcap X_i| \ge \tau]$ 。这造成了功能性失配，并导致权威集中——即 TP 既作为量子资源提供者，又作为私有数据的语义解释者。

方法论
作者提出了一种多方量子 TPSI（MP-QTPSI）协议，该协议将测量角色与语义解释角色解耦。协议涉及 $n$ 个参与者（ $P_1, \dots, P_n$ ）和一个半诚实的第三方（TP）。

量子阶段（隐藏标签构建）：
- 设置： 参与者通过无需第三方的量子会议密钥协商（QCKA）建立主密钥，以导出位置隐藏密钥 $k$ 、隐藏标签翻转向量 $\mathbf{b}$ 和旋转份额 $\Delta_i$ 。TP 与每个参与者建立用于旋转掩码 $T_i$ 的成对密钥。
- 编码： 参与者在其集合中加入正锚点集（positive anchor sets），并应用位置隐藏映射 $x \mapsto kx \mod M$ 。他们将集合编码为指示向量 $Y_i$ 。
- 交互： TP 制备单光子序列并应用初始盲化旋转。序列按顺序经过各个参与者。每个参与者 $P_i$ 根据其数据（$0 $或$ \pi/n $）、其成对掩码$ T_i $以及其旋转份额$ \Delta_i$ 应用旋转。
- 测量： TP 移除其已知的掩码并测量序列。由于关联的聚合旋转，测量结果仅在所有参与者都持有该元素（交集）或均不持有该元素（非交集）的位置是确定性的，但这些结果的语义含义（哪个标签对应“交集”）被隐藏翻转向量 $\mathbf{b}$ 所屏蔽。TP 获得隐藏标签指示向量 $z_S$ （相同）和 $z_O$ （相反），但若没有参与者侧的信息，则无法对其进行解释。
经典阶段（基数测试）：
- 掩码一致性测试： 协议将隐藏测量转换为掩码标签一致性测试。参与者持有参考标签 $\rho$ 以及针对真实域和锚点域的选择器掩码。
- 不经意线性评估（OLE）： TP 与参与者使用基于 OLE 的不经意内积（OIP）来计算一致性计数（不一致项 $d_{\mathcal{R}}$ 和 $d_{\mathcal{A}}$ ）的加法份额，而无需向彼此揭示向量。
- 阈值决策： 一个轻量级的混淆电路用于评估谓词 $\text{flag} = 1 \iff (d_{\mathcal{A}} = 0) \land (d_{\mathcal{R}} \le |\mathcal{R}| - \tau)$ 。该电路仅输出布尔结果，确保精确的基数不会被泄露给 TP。
- 重构： 如果 $\text{flag}=1$ ，TP 广播隐藏向量，参与者使用其参考标签和逆密钥 $k^{-1}$ 来重构交集。

核心贡献

显式基数测试： 该协议是第一个严格遵循基数测试范式的量子 TPSI 协议，它仅输出阈值谓词 $\mathbb{1}[|\bigcap X_i| \ge \tau]$ ，而不向 TP 揭示精确的基数。
隐藏标签量子设计： 通过利用参与者侧的关联聚合旋转和隐藏翻转向量，该协议确保了 TP 的测量结果在语义上是被屏蔽的。TP 仅作为测量方，无法将结果映射到特定的集合元素或基数。
安全性： 协议证明了其对于外部窃听者（通过诱骗光子）、半诚实 TP（无法获知集合及基数）以及合谋参与者（由于成对掩码和未知的盲化旋转，无法推断他人的集合）的安全性。
篡改检测： 引入隐藏锚点集以进行一致性检查（ $d_{\mathcal{A}}=0$ ），从而能够检测 TP 是否修改了报告的测量向量。

结果

正确性： 理论证明表明，该协议能正确编码交集模式，且经典子协议能正确评估阈值条件。
模拟： 作者在 IBM Qiskit 平台上使用玩具模型（ $n=3$ ，定义域大小为 8）实现了量子阶段。模拟包含了去极化、相位阻尼和读取误差。噪声模拟结果（表 3）与理论概率高度吻合，成功通过了锚点检查和阈值测试，并重构了正确的交集 $\{1, 3\}$ 。
复杂度： 量子通信成本为 $\mathcal{O}(n(\ell M + \delta))$ ，计算成本与之类似，其中 $M$ 是增强后的定义域大小， $\ell$ 是重复次数， $\delta$ 是诱骗光子的数量。

意义与声明
论文声称其主要意义在于解决了现有量子 TPSI 协议中的“功能差距”。通过将量子测量角色与语义解释角色分离，所提出的协议符合理想的经典 TPSI 定义，即阈值决策是一个直接的谓词，而非基于已揭示统计量的后处理步骤。作者强调，其构造仅依赖于单光子旋转和轻量级的经典后处理步骤（OLE 和混淆电路），避免了其他近期工作中使用的量子同态加密（QHE）的复杂性。他们断言，这种设计为需要 TP 不学习交集大小的多方环境提供了一种更具隐私保护性的方案。论文最后指出，该框架具有灵活性，未来可能扩展到基于权重或比例的阈值，尽管目前是在半诚实 TP 模型下运行。