隐私集合如何交集计算

wen 网络安全 2026-07-16 1

本文目录导读：

隐私集合如何交集计算

这是一个关于密码学和安全多方计算（MPC）的经典问题。隐私集合交集（Private Set Intersection, PSI） 指的是，在双方（或多方）各自持有隐私集合的情况下，共同计算它们的交集（即共有的元素），但不泄露任何一方不属于交集的私有元素。

你有一个列表,我有一个列表，我们想知道有哪些名字是重复的，但不能让对方知道各自独有的名字。

要实现这一目标,不能简单地把列表发给对方，下面介绍几种主流的隐私集合交集计算方法，从简单到复杂。

核心思想

所有PSI协议都依赖于密码学工具来“混淆”数据，同时保留一个可以用来比较是否相等的“指纹”。

这是最直观的方法,但不是严格意义上的安全，因为哈希值可能被暴力破解。

双方约定：使用同一个密码学哈希函数，例如SHA-256。
Alice操作：用自己的密码学哈希函数（如SHA-256）和一个双方共享的盐值（Salt，用于防止彩虹表攻击），计算自己集合中每个元素的哈希值 H(x || salt)。
Bob操作：用相同的盐值，计算自己集合中每个元素的哈希值 H(y || salt)。
发送与比较：双方交换哈希值列表，然后各自找出哈希值相同的项，这些哈希值对应的原始元素就是交集。

缺点：

适用场景：非敏感数据、双方完全信任对方不会暴力破解、或者元素空间极大且不可枚举。

这是目前工业界和学术界最主流、最高效的PSI方案，它解决了哈希方案的安全问题。

核心工具：不经意伪随机函数（Oblivious PRF）

PSI流程（以“离线-在线”模式为例）：

准备阶段（Alice）：
- Alice生成一个OPRF密钥 k。
- Alice用k计算自己集合中每个元素a的OPRF值：PRF(k, a)，然后她将计算出的所有值 {PRF(k, a1), PRF(k, a2), ...} 发送给Bob。
在线阶段（Bob）：
- Bob对于自己集合中的每个元素b，通过OPRF协议与Alice交互，在不泄露b给Alice的情况下，获得PRF(k, b)。
- Bob现在手里有两份数据：
  - Alice的OPRF值列表 {PRF(k, a)}
  - 自己的OPRF值列表 {PRF(k, b)}
- Bob计算这两份列表的交集（即找出相同的OPRF值），那些能找到相同OPRF值的b，就是交集元素，Bob可以告诉Alice结果。

为什么安全？

优点：高效（现代方案只需几轮通信，计算量小）、安全（基于标准密码学假设）、可扩展到百万级数据。

这是一种历史悠久的方案,适合理解概念。

双方生成密钥：Alice生成自己的私钥a，Bob生成自己的私钥b，他们共享同一个大素数群G和生成元g。
Alice计算：对于自己集合中的每个元素x，计算 Hash(x)^a（将x映射到群G中的一个点，再做私钥a次幂），发送给Bob。
Bob计算：
- 对于自己集合中的每个元素y，计算 Hash(y)^b，发送给Alice。
- 也计算自己收到的来自Alice的每个值 (Hash(x)^a)^b = Hash(x)^(a*b)。
Alice计算：对于自己收到的来自Bob的每个值 Hash(y)^b，计算 (Hash(y)^b)^a = Hash(y)^(a*b)。
比较：
- Alice现在拥有 {Hash(x)^(a*b)}（来自自己的元素）
- Bob现在拥有 {Hash(y)^(a*b)}（来自自己的元素）
- 双方交换这些经过双重哈希（实际上是双重指数）后的结果。Hash(x)^(a*b) = Hash(y)^(a*b)，则意味着 x = y，即交集元素。

缺点：计算量大（公钥运算很慢）、通信复杂度高（需要传输O(n)个群元素）、不适用于大规模集合。

开源库：很多密码学库实现了PSI协议，
- libPSI (来自 EMP-toolkit)
- Cryptographic-Set-Intersection (来自 MIT)
- OpenMined 的 PySyft
云服务：如 AWS Clean Rooms、Google Ads Data Hub 等提供了基于PSI的隐私数据匹配服务。
技术趋势：目前最前沿的PSI方案基于 OPRF (KKRT, PSZ, etc.) 或 基于VOLE的PSI，可以实现对亿级数据的秒级匹配。

一句话总结：隐私集合交集计算通过密码学工具（如OPRF、公钥加密）让双方在不暴露私有元素的前提下比较“指纹”，从而找出共有元素，对于大多数实际需求，OPRF-based PSI 是当前的最佳选择。