LOADING

加载过慢请开启缓存 浏览器默认开启

PSI 基础：从百万富翁问题到现代隐私集合求交

Cryptography 密码学 PSI MPC 隐私计算 阅读量 0

PSI 基础：从百万富翁问题到现代隐私集合求交

PSI，全称是 Private Set Intersection，中文一般叫私有集合求交。

它解决的问题很直接：两个参与方各自有一批数据，双方想知道哪些元素是共同的，但不想把非交集部分暴露给对方。

举几个现实场景：

  1. 两家公司想找共同客户，但不想把完整客户名单交出去。
  2. 安全厂商想和另一方比对恶意 IP、域名、哈希，但不想暴露自己的完整情报库。
  3. 平台想做广告转化归因，广告方有曝光用户，平台有购买用户，双方只想知道交集或交集规模。
  4. 医疗或基因场景中，机构想寻找共同病例或匹配样本，但不希望泄露所有患者信息。
  5. 通讯录发现好友时，服务端希望知道用户通讯录中哪些人已经注册，但不应该拿到整份通讯录明文。

如果只把数据做一次普通哈希再交给对方，看起来好像可以隐藏原始数据，但很多实际标识符空间很小，比如手机号、邮箱、身份证号、IP、车牌号。攻击者可以提前建立字典，把哈希反查回来。所以 PSI 的意义不是“把集合哈希一下”，而是在协议层面限制双方能学到的信息。

1. 从姚氏百万富翁问题说起

安全多方计算里最经典的引子是姚氏百万富翁问题：

两个百万富翁想知道谁更有钱，但都不想暴露自己的真实财富。

这个问题表面上是在比较两个数字，背后真正表达的是：

Alice 有私有输入 x
Bob 有私有输入 y
双方共同计算 f(x, y)
除了 f(x, y) 的结果，不泄露 x 和 y 的额外信息

百万富翁问题里的函数是：

f(x, y) = x > y ?

PSI 里的函数则是：

f(X, Y) = X ∩ Y

或者只输出交集大小：

f(X, Y) = |X ∩ Y|

这就是 PSI 和 MPC 的关系：PSI 是一个非常典型、非常实用的安全多方计算任务。MPC 研究“怎么在不泄露输入的情况下共同计算函数”，PSI 研究的是其中一个特殊函数：集合求交。

2. PSI 到底要保护什么

设 Alice 的集合是：

X = {x1, x2, x3, ...}

Bob 的集合是：

Y = {y1, y2, y3, ...}

一个理想 PSI 协议希望做到：

  1. Alice 最多知道交集中的元素。
  2. Bob 最多知道交集中的元素。
  3. Alice 不知道 Bob 的非交集元素。
  4. Bob 不知道 Alice 的非交集元素。
  5. 协议不能让任意一方通过构造恶意输入大量套取对方集合。

第 5 点在真实系统中尤其重要。比如一个恶意客户端可以拿手机号全集当作自己的输入集合，那么交集就会变成服务端集合本身。严格来说，这不是密码协议本身能完全解决的，还需要输入规模限制、频率限制、认证、审计、差分隐私、业务侧反滥用策略一起配合。

3. 先看一个不安全的“哈希求交”

最朴素的做法是：

  1. Alice 把每个元素做 H(x) 发给 Bob。
  2. Bob 把每个元素做 H(y)。
  3. Bob 比较哈希值，得到交集。

这个方案有两个问题：

  1. 如果元素空间可枚举，Bob 可以离线暴力枚举 Alice 的元素。
  2. 如果双方直接交换哈希集合，双方可能拿到比交集更多的信息。

所以现代 PSI 往往需要引入公钥密码、OPRF、OT、同态加密、布谷鸟哈希、秘密分享等技术，让“比较相等”这件事可以在隐藏输入的状态下完成。

下面用三个基于 RSA 或公钥思想的方案建立直觉。它们不是生产系统的最终形态，但很适合入门。

4. 方案一：基于 RSA 盲化签名的 PSI

这个方案的核心思想是：Bob 持有 RSA 私钥，Alice 想让 Bob 给自己的元素做一个“签名式映射”，但 Bob 不能看到 Alice 的元素。

RSA 里有：

公钥: (N, e)
私钥: d
签名: s = m^d mod N
验证关系: s^e = m mod N

为了不让 Bob 看到 m = H(x)，Alice 使用盲化：

Alice 选择随机 r
blinded = H(x) * r^e mod N

Bob 对盲化值做私钥运算：

signed_blinded = blinded^d mod N

展开可以看到：

signed_blinded
= (H(x) * r^e)^d mod N
= H(x)^d * r mod N

Alice 拿回来以后除掉 r：

token_x = signed_blinded * r^-1 mod N
        = H(x)^d mod N

这样 Alice 得到了自己元素对应的 token，但 Bob 没看到 Alice 的元素。

Bob 对自己的集合也计算：

token_y = H(y)^d mod N

最后双方比较 token：

token_x == token_y  <=>  x == y

这个方案的直觉很强：

  1. RSA 私钥指数 d 像一个只有 Bob 掌握的“秘密函数”。
  2. Alice 通过盲化让 Bob 帮自己算这个函数。
  3. 相同输入会得到相同 token，不同输入几乎不会撞上。
  4. Alice 只能比较 token，不能从 token 反推出 Bob 的非交集元素。

但它也有明显缺点：

  1. RSA 指数运算很重，大集合时代价高。
  2. 需要处理恶意输入、重复元素、集合大小泄露等问题。
  3. 如果直接输出交集，还要考虑哪一方获得结果、是否只输出交集大小。
  4. RSA 方案不适合后量子安全要求。

所以它适合理解 PSI 的基本形状，但不是当前大规模工程 PSI 的主流选择。

5. 方案二：基于可交换加密的 DH/RSA 风格 PSI

可交换加密的特点是：双方用各自密钥加密同一个消息时，加密顺序不影响最终结果。

抽象地说：

E_a(E_b(m)) = E_b(E_a(m))

如果用指数运算来理解，可以把元素哈希到群中：

h = H(x)

Alice 用自己的秘密指数 a 处理：

A_x = h^a

Bob 用自己的秘密指数 b 处理：

B_y = H(y)^b

然后双方交换一次，再各自做第二层指数：

Bob 对 Alice 的值再处理: (H(x)^a)^b = H(x)^(ab)
Alice 对 Bob 的值再处理: (H(y)^b)^a = H(y)^(ab)

最后双方比较：

H(x)^(ab) == H(y)^(ab)  <=>  x == y

这个方案的美感在于：

  1. 双方都没有单方面控制最终映射。
  2. 加密顺序可以交换，所以相同元素最终会落到同一个值。
  3. 不同元素在离散对数困难假设下难以反推原文。

但是它仍然有工程问题：

  1. 每个元素至少需要公钥群指数运算。
  2. 大规模集合下计算和通信都很重。
  3. 如果没有额外随机化、认证和证明，恶意参与方可能构造异常元素。
  4. 输出阶段仍然要处理谁拿到交集、是否泄露集合大小、是否允许重复元素。

这个思路经常被用来讲“为什么双方可以在不知道明文的情况下比较相等”。它和后面的 OPRF 思想很接近：把元素映射到一个只有协议双方合作才能得到的伪随机标签。

6. 方案三：基于 RSA/Paillier 同态思想的多项式 PSI

第三类方案更接近早期经典 PSI 论文里的思路：把集合编码成多项式，再用同态加密让对方在密文上计算。

Alice 有集合：

X = {x1, x2, x3}

她构造一个多项式：

P(t) = (t - x1)(t - x2)(t - x3)

这个多项式有一个性质：

如果 y 在 X 中，那么 P(y) = 0
如果 y 不在 X 中，那么 P(y) != 0

Alice 不想把多项式系数明文给 Bob，于是把系数加密后发给 Bob。Bob 使用同态加密在密文上计算 P(y)，再加上随机掩码：

Enc(P(y)) -> Enc(r * P(y) + y)

直觉是：

  1. 如果 y 属于 Alice 的集合，那么 P(y)=0，解密后得到 y。
  2. 如果 y 不属于 Alice 的集合，那么解密后得到一个被随机数扰乱的值。
  3. Alice 解密后只看哪些结果能落回合法元素，从而得到交集。

严格实现会比这个直觉版本复杂得多，需要处理有限域、编码、随机掩码、恶意安全、重复元素、结果泄露等问题。

这类方案的好处是表达力强，可以自然引出：

  1. 同态加密为什么能在密文上计算。
  2. 集合成员关系可以转化成多项式零点判断。
  3. PSI 不只是“加密后比较”，也可以是“把集合变成一个可计算函数”。

缺点也很明显：

  1. 同态计算和密文体积通常比较重。
  2. 多项式阶数随集合规模增长，直接方案不适合超大集合。
  3. 真实系统需要大量编码、分桶、批处理和参数优化。

所以它更适合作为理解同态 PSI 的入口。

7. 三个方案放在一起看

方案 核心技术 直觉 优点 主要问题
RSA 盲化签名 PSI RSA 盲签名 / OPRF 雏形 Bob 帮 Alice 计算秘密映射，但看不到输入 容易理解，协议形状清晰 RSA 运算重，不适合大规模
可交换加密 PSI DH/RSA 风格指数运算 双方各加密一层，顺序可交换 相同元素最终标签一致 公钥运算多，恶意安全复杂
同态/多项式 PSI 同态加密 + 多项式零点 集合成员判断变成 P(y)=0 表达力强，可扩展到更多功能 密文计算和编码代价高

它们共同说明了 PSI 的核心闭环：

把元素变成隐私保护标签
让相同元素得到可匹配的标签
让不同元素和非交集元素保持隐藏
控制输出范围
再把效率、安全模型和工程约束补齐

8. 为什么前沿 PSI 不停往 OPRF、OT、VOLE 走

现代 PSI 的目标不是“能不能做”，而是：

  1. 千万级、亿级集合能不能跑。
  2. 互联网带宽下能不能跑。
  3. 移动端或浏览器端能不能跑。
  4. 恶意参与方能不能防。
  5. 只输出交集大小、带 payload、模糊匹配、多方求交能不能做。
  6. 云上跑的时候计算成本和流量成本能不能接受。

因此，很多高性能 PSI 都在减少昂贵的公钥运算，把大量工作转成对称密码、哈希、OT 扩展、VOLE 相关技术。

8.1 OPRF：把 PSI 看成“双方合作计算秘密标签”

OPRF 是 Oblivious Pseudorandom Function，中文可以叫不经意伪随机函数。

它的目标是：

客户端输入 x
服务端持有密钥 k
客户端得到 F_k(x)
服务端不知道 x
客户端不知道 k，也不能计算其他输入的 F_k

这和 PSI 很契合：

  1. 双方把各自元素都映射成 F_k(element)。
  2. 相同元素得到相同标签。
  3. 非交集元素看起来像随机值。
  4. 客户端不能绕过协议随意查询大量元素时，还需要额外限制和认证。

Chase 和 Miao 在 CRYPTO 2020 的工作就围绕轻量级 OPRF 构造 Internet setting 下的 PSI，关注中等带宽网络里的计算和通信平衡。Microsoft Research 的介绍里也强调了这类协议在 30-100 Mbps 等网络条件下的效率优势。

8.2 OT 扩展：用少量公钥操作换大量对称操作

OT 是 Oblivious Transfer，不经意传输。最常见的 1-out-of-2 OT 可以理解为：

Sender 有 m0, m1
Receiver 选择 b
Receiver 只得到 mb
Sender 不知道 b
Receiver 不知道另一个消息

很多 PSI 协议把“元素是否相等”的判断转成大量 OT 相关操作。直接做 OT 很贵，因为基础 OT 往往依赖公钥密码。OT 扩展的思想是：

先做少量基础 OT
再用对称密码和矩阵扩展出大量 OT

这就是前沿 PSI 高效起来的关键之一。你之前写过 OTE，正好可以把它接到 PSI：PSI 不是孤立知识点，OTE 是很多高性能 PSI 协议背后的效率来源。

8.3 布谷鸟哈希：先把比较范围压小

如果 Alice 和 Bob 都有很多元素，直接两两比较是：

O(n * m)

这完全不可接受。

布谷鸟哈希和分桶技术的作用是：把元素放进桶里，让协议只在对应桶或少量候选位置上比较。这样可以把“全局两两比较”变成“局部候选比较”。

高性能 PSI 里经常会看到：

  1. Cuckoo hashing
  2. simple hashing
  3. stash
  4. binning
  5. padding

这些看起来像数据结构细节，但其实非常关键。它们决定了通信量、误判概率、桶溢出概率和实现复杂度。

8.4 VOLE / PCG：把相关随机性预处理出来

更靠近当前研究前沿的一条线是 VOLE-based PSI。

VOLE 可以粗略理解为一种能高效生成相关随机性的工具。很多现代 MPC/PSI 协议把大量在线计算拆成：

离线阶段：生成相关随机材料
在线阶段：用这些材料快速完成真实输入上的计算

这样做的好处是：在线阶段更快、更适合真实业务交互。近几年的 volePSI、silent VOLE、PCG 等关键词，经常出现在高性能 PSI 和 MPC 系统里。

8.5 后量子 PSI：RSA 和 DH 不是终点

前面三个入门方案都依赖 RSA、离散对数或同态加密类假设。量子计算一旦能运行大规模 Shor 算法，RSA 和传统 DH 都会受到威胁。

所以 PSI 的一个前沿方向是后量子安全：

  1. 基于格的 PSI。
  2. 基于 LPN/LWE 假设的 OPRF 或 OT 扩展。
  3. 避免传统 RSA/DH 的协议设计。
  4. 在安全性、通信量、实现复杂度之间重新权衡。

后量子 PSI 现在还不是所有工程场景的默认选项，但如果系统有长期机密性要求，或者数据生命周期很长，就需要关注这一方向。

9. 一个学习闭环：从问题到协议到工程

学 PSI 不建议一开始就啃最新论文，可以按这个闭环推进：

  1. 先理解姚氏百万富翁问题：目标是“计算结果，不泄露输入”。
  2. 再理解 PSI 功能：集合求交或交集大小。
  3. 用 RSA 盲化签名理解“秘密标签”。
  4. 用可交换加密理解“相同元素经过双方处理后仍能匹配”。
  5. 用同态多项式理解“集合成员关系可以变成函数计算”。
  6. 接着看 OPRF：现代 PSI 经常把元素变成 F_k(x)。
  7. 再看 OT/OTE：为什么高性能协议能把公钥操作摊薄。
  8. 最后看布谷鸟哈希、VOLE、恶意安全、后量子和系统实现。

这一条线走下来，PSI 就不再是一堆协议名字，而是一组不断解决瓶颈的设计选择。

10. 入门练习

题 1：为什么普通哈希求交不安全

Alice 和 Bob 想比较手机号集合。他们约定把手机号做 SHA256(phone) 后交换哈希集合。

请回答：

  1. 这个方案会泄露什么？
  2. 为什么手机号特别容易被字典攻击？
  3. 加盐是否能解决双方求交问题？为什么？

提示：如果双方各自加不同的盐，相同手机号的哈希还会相同吗？

题 2：RSA 盲化签名 PSI 的推导

设 Bob 的 RSA 公钥是 (N, e)，私钥是 d。Alice 对元素 x 计算 m=H(x)，选择随机数 r，发送：

z = m * r^e mod N

Bob 返回：

u = z^d mod N

请推导 Alice 为什么可以通过 u * r^-1 mod N 得到 m^d mod N。

题 3：可交换加密为什么能比较交集

Alice 的秘密指数是 a，Bob 的秘密指数是 b。元素哈希后为 h。

请解释为什么：

(h^a)^b = (h^b)^a

并说明这个等式对 PSI 有什么用。

题 4：多项式 PSI 的成员判断

Alice 集合是：

X = {2, 5, 9}

构造：

P(t) = (t - 2)(t - 5)(t - 9)

请计算：

P(5)
P(7)

并说明为什么 P(y)=0 可以表示 y 属于 Alice 的集合。

题 5：前沿方向判断

下面场景分别更适合关注哪类 PSI 技术？

  1. 两方各有千万级用户标识，要求互联网环境下低成本运行。
  2. 只需要知道交集大小，不需要知道具体交集元素。
  3. 多家机构共同找交集，参与方超过两个。
  4. 数据需要长期保密，担心未来量子计算威胁。

可以从 OPRF、OT/OTE、PSI-CA、多方 PSI、VOLE-based PSI、后量子 PSI 中选择关键词。

参考资料

  1. Andrew C. Yao, Protocols for Secure Computations, 1982.
  2. Michael J. Freedman, Kobbi Nissim, Benny Pinkas, Efficient Private Matching and Set Intersection, EUROCRYPT 2004.
  3. Benny Pinkas 等，Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF, CRYPTO 2020.
  4. Microsoft Research: Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF
  5. Microsoft Research: Efficient Batched Oblivious PRF with Applications to Private Set Intersection
  6. SecretFlow PSI 文档
  7. SecretFlow PSI/PIR GitHub 仓库
  8. David Evans, Vladimir Kolesnikov, Mike Rosulek, A Pragmatic Introduction to Secure Multi-Party Computation
  9. 近年 volePSI、silent VOLE、PCG、post-quantum PSI 相关论文和实现。