走向更高效的抗泄露增强型私有集合并集

为何共享列表会威胁隐私

许多组织保存着敏感列表——例如可疑 IP 地址、客户编号或医学研究参与者名单——它们希望与另一方的名单合并，但又不想泄露自己的数据。一种称为“私有集合并集”的工具恰好能做到这一点：它允许双方得知合并后的唯一项目列表，而不会获知更多信息。本文表明，即便是最先进的该工具实现，在运行过程中也可能悄悄泄露额外信息，并提出了一种新设计，在保持其优点的同时大幅降低这些隐性风险和计算成本。

私有集合并集试图保护的内容

设想两家公司在比较网络攻击黑名单。每家公司都希望得到由任一方发现的所有可疑 IP 地址的完整列表，以便更好地防护网络。同时，每家公司用于检测的方式——以及因此产生的精确黑名单——都是商业机密。如果能推断出对方拥有哪些地址或不拥有哪些地址，就可能揭示这些检测方法。传统的私有集合并集协议已经能隐藏列表之间的直接重合，但近期研究发现，它们在计算过程中或通过内部数据结构中项目排列的模式，仍可能泄露线索。

快速早期方法中的隐性泄露

早期可扩展方案依赖一种做法：先逐项检查来自一方的每个元素是否出现在另一方中，然后用这些答案只输出“新的”项目。后来的工作表明，这一过程本质上会在协议完成前泄露两份列表共享了多少项目。一个好奇的参与者可以通过中止并用稍作调整的输入重复运行协议，逐步得知哪些具体项目重合。其他快速方案使用哈希——根据哈希函数将项目放入箱（bins）中——来组织数据。一旦一方得知了另一方哪些项目是独有的，就可交叉比对已填充和空箱的模式，推断出哪些自己的项目肯定不在对方列表中，这是一种“基于哈希”的泄露。

用随机伪装锁住项目

新协议同时应对上述两类问题。在任何哈希发生之前，每一方先运行一个密码学交换，将每个项目变为看似随机的令牌。关键性质是：来自双方的相同项目会被映射为相同的令牌，而不同项目产生无关的令牌——且双方都不会学到将令牌还原为真实值的秘密密钥。这些伪装后的令牌随后被放入基于哈希的表中，并经过一系列精心设计的随机化步骤，实质上决定令牌是否匹配，但不泄露哪个令牌位于哪个箱中。每次运行都使用新的随机性，防止攻击者在多次执行间关联信息。

用更聪明的数据结构降低成本

如果协议过于沉重而无法在规模上使用，仅有安全性并不够。因此作者们重设计了最昂贵的组件之一：一个以前依赖批量密码学原语来同时比较许多项目的内部模块。他们将其替换为一个“双向”不可知密钥值存储（oblivious key-value store），这是一种紧凑结构，允许一方以编码的方式存储键-值对，使另一方能够查询而不学到除键是否存在以外的任何信息。通过让两个这样的编码相互配合，协议能在避免对空箱或虚假箱进行工作时识别出两边令牌的对齐情况。这一改变大幅减少了网络上传输的数据量和计算时间，尤其在处理大型列表时效果显著。

实验在实践中显示的效果

为检验其构想，作者实现了该协议并在相同、更严格的隐私目标下与现有最佳增强型私有集合并集设计进行了比较。在各种列表规模和网络条件下，他们的方法在通信量上通常减少了约 1.1 到 3 倍，运行时间加速约 1.0 到 1.7 倍。重要的是，这些收益在加入防止基于哈希泄露的额外密码学层后仍然成立，而早期高效方案忽视了这一点。结果表明，更强的保护并不必然伴随巨大的性能代价。

这对现实世界数据共享意味着什么

简言之，这项工作展示了双方如何在合并敏感列表的同时，大幅限制彼此能推断出的对方数据——即便是来自协议运行过程中的微妙副作用。通过在哈希前对项目进行伪装并采用更节省的内部结构，新设计关闭了已知的泄露通道，并在处理非常大数据集时仍保持足够快。这使得在不暴露自身数据模式的前提下，公司和机构在联合黑名单、客户 ID 或其他标识符时更具现实可行性。

引用: Liu, Q., Bae, J. & Lee, JW. Towards an improved efficient leakage-resilient enhanced private set union. Sci Rep 16, 10134 (2026). https://doi.org/10.1038/s41598-026-40531-5

关键词: 私有集合并集, 数据隐私, 密码学协议, 安全数据共享, 泄露抗性