关于隐私集合求交 (PSI) 的认识

XR2025-06-192026-02-03

关于隐私集合求交 (PSI) 的认识

隐私集合求交（Private Set Intersection, PSI）是密码学和数据工程交叉领域中的一个经典问题：两个或多个参与方，如何在不泄露各自私有数据的前提下，计算出他们数据集的交集？

这个需求在现实世界中非常普遍，例如：

广告归因：广告平台和广告主需要知道哪些观看了广告的用户最终完成了购买，但双方都不想直接暴露自己的全部用户列表。
联系人发现：手机应用想知道你的通讯录里有哪些人也注册了该应用，但你不想上传整个通讯录。
安全情报共享：多个情报机构希望找出共同的嫌疑人名单，但各自的名单都是高度机密的。

本文将梳理几种主流的 PSI 实现方案，分析它们的设计思路、性能、安全性，以及各自的适用场景。

核心密码学概念：安全模型

在深入了解各种 PSI 协议之前，我们必须先理解评估其安全性的两个基本模型。这决定了一个协议能抵御什么样的攻击者。

半诚实模型 (Semi-Honest / Honest-but-Curious)
- 定义：这是密码学协议中最常见的威胁模型。在此模型中，参与方会完全遵守协议的每一步指令，如同一个诚实的学生。但是，他们会保留协议执行过程中收到的所有信息（例如，中间计算结果），并试图在协议结束后，通过分析这些信息来推断出超出协议规定泄露范围的、对方的额外隐私。
- 类比：一个“好奇的”合作伙伴。他会按合同办事，但会试图从你给他的文件中分析出你的商业秘密。
- 意义：绝大多数高性能的 PSI 协议（如 OT-PSI）都是在半诚实模型下被证明安全的。这意味着，只要大家都遵守规则，就不可能泄露交集之外的任何信息。
恶意模型 (Malicious)
- 定义：这是一个更强大、更符合现实世界某些场景的威胁模型。恶意攻击者不遵守协议，他们可以采取任何行动来破坏协议或窃取信息，例如：发送伪造的数据、提前中止协议、或者根据自己的输入来改变协议流程。
- 类比：一个“不择手段的”商业间谍。他不仅想分析文件，还可能伪造文件、贿赂你的员工，以达到目的。
- 意义：防御恶意攻击者需要引入更复杂的密码学工具，如**零知识证明 (Zero-Knowledge Proofs)**，来强制验证每一步的正确性。这通常会导致协议性能大幅下降。因此，恶意安全的 PSI 协议通常用在金融、政府等高风险领域。

结论：在选择 PSI 方案时，首先要评估你的安全需求。对于大多数商业合作场景，半诚实模型下的安全通常已经足够。

方案一：基础哈希方案 - 简单但脆弱

最直观的想法是避免明文传输，利用哈希函数的单向性。

核心原理

单向哈希函数：如 SHA-256，可以将任意输入数据转换成一个固定长度的、独一无二的“指纹”。关键在于，从指纹反推出原始输入在计算上是不可行的。

协议流程

约定哈希: A 和 B 双方约定一个标准的哈希函数（如 SHA-256）。
本地计算: A 将自己的数据集内每个元素进行哈希，得到哈希列表 Hash(A)。B 也同样计算出 Hash(B)。
交换与比较: 双方交换哈希列表，然后本地比较 Hash(A) 和 Hash(B)，找出相同的哈希值，这些就代表了原始数据的交集。

实现伪代码 (Python)

import hashlib

def hash_items(items):
    return {hashlib.sha256(item.encode()).hexdigest() for item in items}

# Client A's data
data_A = {"apple", "banana", "cherry"}
# Client B's data
data_B = {"banana", "date", "grape"}

# 1. Both parties hash their data
hashed_A = hash_items(data_A)
hashed_B = hash_items(data_B)

# 2. They exchange these hashed sets
# 3. B finds the intersection of the hashed sets
intersection_hashes = hashed_A.intersection(hashed_B)

# B might send these back to A for final confirmation, or if hashes are identifiers,
# the process might end here.
print(f"Intersection Hashes: {intersection_hashes}")

分析

优点：实现极其简单，计算速度飞快，网络通信只有一轮。
缺点：安全性极低。如果元素的空间有限且已知（如手机号、身份证号、日期），攻击者可以轻松构建一个“彩虹表”，通过预计算的哈希值反推出原始输入。即使对每个元素加盐（Salt），也只能增加暴力破解的难度，无法从根本上解决问题。

结论：该方案仅适用于内部系统或完全可信的环境，绝对不能用于对抗任何有动机的外部攻击者。

方案二：布隆过滤器 - 高性能的概率方案

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，它以牺牲一小部分准确性为代价，换取了巨大的性能和空间优势。

核心原理

位数组与哈希函数: 布隆过滤器由一个很长的位数组（初始化全为0）和多个独立的哈希函数组成。
添加元素: 当你向过滤器中添加一个元素时，你会用所有哈希函数对这个元素进行计算，得到多个不同的位置索引，然后将位数组中这些位置的比特值设为 1。
查询元素: 查询一个元素是否存在时，你用同样的哈希函数再次计算出所有位置索引。只有当所有这些位置的比特值都为 1 时，过滤器才报告“元素可能存在”。只要有一个位置是 0，那么该元素绝对不存在。
假阳性 (False Positive): 当一个本不存在的元素，其哈希到的所有位置恰好都被其他元素置为 1 时，就会发生误判。假阳性率可以通过调整位数组大小和哈希函数数量来控制。

协议流程

阶段一：A 构建并发送过滤器
- 数据量较小的一方（A），根据自己的数据集创建一个布隆过滤器。
- A 将这个紧凑的位数组发送给数据量较大的一方（B）。通信量极小，一个几MB的过滤器就能代表上亿条数据。
阶段二：B 查询并返回候选集
- B 遍历自己的数据集，用与 A 相同的哈希函数去查询收到的布隆过滤器。
- B 将所有在布隆过滤器中显示“可能存在”的元素，构成一个候选交集。这个集合由于假阳性的存在，会比真实交集更大。
- B 将这个候选集的原始 ID（或其哈希）发回给 A。
阶段三：A 确认最终交集
- A 收到候选集后，在自己的原始数据中进行精确匹配，剔除掉所有假阳性成员，得到最终的真实交集。

分析

优点:
- 性能极高：计算哈希和位操作非常快，是所有方案中速度最快的之一。
- 通信效率极高：A 只需要发送一个紧凑的位数组，通信成本是其最大亮点。
缺点:
- 有误报：必须有一个额外的交互步骤（B -> A）来剔除误报结果。
- 安全性有限：过滤器本身虽然不是明文，但仍然泄露了关于数据集的统计学特征。如果 B 是恶意的，它可以利用过滤器测试它猜测的元素是否存在于 A 的集合中。因此，它只在半诚实模型下提供有限的隐私保护。

结论：在追求极致性能、能接受多轮交互、且安全要求不是最高级别的场景下，布隆过滤器是业界大规模数据求交的常用方案。它是性能和隐私之间一个出色的工程平衡。

方案三：基于公钥密码学的安全方案

为了实现数学上可证明的安全性（即除了交集本身，不泄露任何额外信息），我们需要引入公钥密码学工具。这些方案通常在半诚实模型下是安全的。

3.1 基于 Diffie-Hellman 的 PSI

该方案巧妙地利用了 Diffie-Hellman 密钥交换协议的交换律，构建了一个优雅的 PSI 协议。

前置知识：Diffie-Hellman 密钥交换
该协议的核心是让两个互不信任的人（Alice 和 Bob）通过公开信道协商出一个共享的秘密密钥。

双方约定公共参数 g 和 p。
Alice 生成私钥 a，计算公钥 A = g^a mod p，发送给 Bob。
Bob 生成私钥 b，计算公钥 B = g^b mod p，发送给 Alice。
Alice 计算共享密钥 S = B^a mod p = (g^b)^a mod p。
Bob 计算共享密钥 S = A^b mod p = (g^a)^b mod p。
由于幂运算的交换律，双方得到了完全相同的密钥 S，而窃听者无法从公开的 A 和 B 中计算出它。

协议流程
此 PSI 协议将每个数据项都视作一次独立的密钥交换。

各自准备: A 和 B 各自生成一个私钥（随机数 a 和 b）。
A 方计算与发送: A 对自己的每个元素 x，先哈希到椭圆曲线上的一个点 H(x)，然后用私钥 a 计算“公钥” P_x = a * H(x)。A 将所有 P_x 组成的列表发送给 B。
B 方计算与发送: B 收到列表后，用自己的私钥 b 对列表中的每个元素进行二次“加密”，得到 S_x = b * P_x = b * a * H(x)。同时，B 对自己的每个元素 y 计算 P_y = b * H(y)。B 将所有 P_y 组成的列表发送给 A。
A 方计算: A 收到 B 发送的 P_y 列表后，用自己的私钥 a 对每个元素计算，得到 S_y = a * P_y = a * b * H(y)。
找出交集: 此时，如果 A 和 B 有一个共同元素 z，那么在 A 的本地，她计算出了 S_z = a*b*H(z)；在 B 的本地，他计算出了 S_z = b*a*H(z)。由于交换律，这两个值是相等的。A 将自己计算出的 S_y 集合与 B 发回的 S_x 集合（A可以在本地重新计算）求交，即可找出交集对应的秘密值，从而确定交集。通常，为了不让 B 也知道交集，最后一步比较只在 A 方进行。

分析

优点：安全性高，基于成熟的公钥密码体系，无误报。在半诚实模型下是安全的。
缺点：计算开销大，涉及大量的椭圆曲线点乘运算（比模幂更快，但仍是重计算），比简单哈希慢得多。通信成本也较高，需要交换两轮数据。

结论：一个优雅的、教科书式的 PSI 方案。适合中等大小数据集，或作为理解更复杂协议的起点。

3.2 基于不经意传输 (OT) 的 PSI

这是当前兼顾顶级安全和顶级性能的黄金标准，是现代隐私计算框架（如 FATE, SecretFlow）的核心。它虽然复杂，但理解其构件是理解现代密码学的关键。

核心构件一：不经意传输 (Oblivious Transfer, OT)

是什么：一个两方协议，其中发送方 (Sender) 有 N 个消息 (m_1, m_2, ..., m_n)，接收方 (Receiver) 有一个索引 i。协议结束后，接收方只得到了消息 m_i，而发送方完全不知道接收方取走了第几个消息。
“邮局信箱”类比: Bob 想从邮递员 Alice 那里拿到 N 封信中的第 i 封，但他不想让 Alice 知道他取了哪封。Bob 有一把只能打开第 i 号信箱的钥匙。他把这把锁（已打开状态，但钥匙不给 Alice）交给 Alice。Alice 拿到后，用它和其他 N-1 把她自己准备的锁，分别锁上对应的 N 封信，然后把所有 N 个信箱都交给 Bob。Bob 只能用自己的钥匙打开第 i 号信箱，拿到信件。Alice 始终不知道 Bob 的选择。
**不经意传输扩展 (OTe)**：基础的 OT 协议执行一次开销很大。OTe 技术可以用很少的“种子”OT 实例，以极低的成本生成海量的 OT 实例，这使得 OT 在大数据场景下变得实用。

核心构件二：布谷鸟哈希 (Cuckoo Hashing)

是什么：一种特殊的哈希表，它为每个元素分配两个或多个备选存储位置。
“布谷鸟占巢”类比: 想象一排鸟巢（一个大数组）和一群布谷鸟（数据项）。每只鸟都有两个固定的巢可以去（由两个哈希函数 h1(x), h2(x) 决定）。当一只新鸟飞来，它检查第一个家 h1(x)。如果空着，就住进去。如果被占了，它就把里面的“原住民”踢出去，自己住进去。被踢出去的鸟，现在飞向它的另一个备选家 h2(x)… 这个过程会像链式反应一样继续下去，直到所有鸟都找到家。
在PSI中的作用: 服务端（大数据方）将自己的数据存入布谷鸟哈希表。这样，客户端（小数据方）想查询一个元素 x，它就明确地知道 x 只可能存在于 h1(x) 和 h2(x) 这两个位置。这避免了全表扫描，将查询范围缩小到常数级别，是 OT-PSI 高性能的关键。

协议流程 (高度简化)
我们将参与方称为客户端 C (数据量小)和服务端 S (数据量大)。目标是客户端得到交集，服务端一无所知。

服务端准备 (离线):
- S 将自己的数据集 Y 存入一个布谷鸟哈希表中。表的每个槽位要么是 y，要么是空。
- S 对布谷鸟哈希表中的每个位置，都填充一个随机生成的秘密值。
交互与查询 (在线):
- C 对于自己的每个元素 x，也用相同的哈希函数计算出它在布谷鸟表中的所有可能位置（如 h1(x), h2(x)）。
- C 作为 OT 协议的接收方，S 作为发送方，双方执行 OTe 协议。C 将上一步计算出的所有位置作为查询索引。
- 通过 OTe，C “不经意地”从 S 获取了它想查询的所有位置上的秘密值。整个过程 S 不知道 C 查询了哪些位置，C 也不知道其他位置的值。
客户端计算 (离线):
- 为了找出交集，协议有一个巧妙的设计：客户端不仅获取秘密值，还能通过另一个函数 F 计算出自己元素的“期望秘密值”。
- 客户端检查取回的秘密值中，是否存在一个与它为 x 计算出的期望值相匹配。如果匹配，x 就属于交集。
- 客户端在本地完成所有匹配，最终得到完整的交集，而服务端对结果一无所知。

  sequenceDiagram
    participant Server as 服务端 (大数据集 Y)
    participant Client as 客户端 (小数据集 X)

    Note over Server: 阶段一：离线准备 (Cuckoo Hashing)
    Server->>Server: 1. 将数据集 Y 存入布谷鸟哈希表
    Server->>Server: 2. 为哈希表中每个槽位填充随机秘密值

    Note over Client,Server: 阶段二：在线交互 (OTe)
    loop 对客户端每个元素 x
        Client->>Client: 3. 计算 x 的两个查询地址 h1(x), h2(x)
    end
    Note over Client,Server: 4. 执行 OTe 协议批量查询
    Client->>Server: 作为接收方，将 h1(x), h2(x)... 作为选择比特
    Server-->>Client: 作为发送方，返回加密的秘密值

    Note over Client: 阶段三：本地计算
    Client->>Client: 5. 将获取的秘密值与本地期望值比对
    Client->>Client: 6. 找出所有匹配成功的元素，构成交集

分析

优点：通过复杂的密码学工程，实现了极高的安全（半诚实模型）和极高的性能，通信轮次少（基本一轮），计算速度远超其他公钥方案。
缺点：实现极为复杂，个人难以从零开始正确构建，必须依赖成熟的、经过同行评审的密码学库。

结论：这是业界前沿的选择，适用于对安全和性能都有着严苛要求的大规模场景。

3.3 关于同态加密 (HE) 的说明

同态加密允许在密文上进行计算，得到的结果解密后与在明文上计算的结果相同。

核心原理

一个函数 f 和加密算法 Enc，满足 Dec(f(Enc(a), Enc(b))) = f(a, b)。
实现思路: A 将自己的集合 {x} 每个元素加密 Enc(x) 并发送给 B。B 利用同态性质，在密文上执行一个“比较”操作，找出哪些 Enc(x) 与自己的某个 Enc(y) 相等。这个过程非常复杂，远不止是简单的 == 比较。
优点：安全性极高，理论上可以支持非常复杂的数据分析。
缺点：性能极差。同态运算比明文运算慢数个数量级，且密文膨胀严重。对于简单的集合求交任务，其开销远大于专用的 OT-PSI 等协议，如同“用大炮打蚊子”。

结论：HE 是解决更复杂隐私计算问题的强大工具（如隐私联邦学习中的模型聚合），但对于单纯的 PSI 任务，通常不是性价比最高的选择。

PSI 协议变种

标准的 PSI 解决的是“找出交集成员”的问题，但在现实中，我们常常有更细化的需求。

PSI-Cardinality (交集基数计算)
- 目标：只计算交集的大小 |X ∩ Y|，不暴露任何交集成员。
- 场景：两家公司想知道他们有多少共同客户，但不想知道具体是哪些客户。
- 实现：通常比标准 PSI 更高效，因为需要泄露的信息更少。可以基于布隆过滤器（A 发送过滤器，B 查询后返回一个计数值）、或专用的密码学协议构建。
Labeled PSI (带标签的 PSI)
- 目标：一方（通常是客户端 A）拥有数据集 X，另一方（服务端 B）拥有带标签的数据集 {(y, l_y)}。协议结束后，A 得到与交集相关的标签 { (x, l_x) | x ∈ X ∩ Y }。B 除了数据集大小外，一无所知。
- 场景：广告归因。广告平台（B）有（用户ID, 转化价值）数据，广告主（A）有（用户ID）数据。通过 Labeled PSI，广告主可以知道自己哪些用户产生了转化，以及具体的价值，而平台方无需暴露所有用户的价值信息。
- 实现：通常是 OT-PSI 的一个扩展。
Multi-Party PSI (多方 PSI)
- 目标：三个或更多参与方，共同计算他们数据集的交集 X1 ∩ X2 ∩ ... ∩ Xn。
- 场景：多个安全机构希望找出他们共同的嫌疑人名单，但任何两方之间都不想暴露自己的私有名单。
- 实现：复杂度显著提高。常见的方法有两类：
  1. 基于中心协调者：所有参与方都与一个（可信或不可信的）中心服务器进行两方 PSI。
  2. 去中心化：参与方形成一个环，例如 P1 -> P2 -> ... -> Pn -> P1，每一方都将自己与上一方计算的中间结果传递给下一方，最终完成计算。

方案对比与选择

方案	安全模型	性能	通信成本	核心原理	实现复杂度	核心场景
简单哈希	不安全	极高	中	单向哈希	低	内部或完全可信环境
布隆过滤器	弱/半诚实	极高	极低	概率数据结构	中	性能敏感，能接受额外交互
DH-PSI	半诚实	中	高	密钥交换	高	安全要求高，数据集不大，教学
OT-PSI	半诚实	高	中	不经意传输	极高	兼顾高性能和高安全的前沿选择
HE-PSI	半诚实	极低	极高	同态加密	极高	学术研究或复杂计算场景

如何选择？一份决策指南

第一步：评估安全威胁与信任模型
- 你的对手是会遵守规则的“好奇宝宝”（半诚实），还是可能作弊的“破坏者”（恶意）？
- 对于绝大多数商业应用，半诚实安全已经足够。如果需要对抗恶意攻击，你需要寻找明确支持Malicious Secure的库，并接受显著的性能下降。
第二步：明确你的输出需求
- 你真的需要交集的具体成员吗？还是只需要它的数量（-> PSI-Cardinality）？
- 你是否需要在求交的同时，从对方获取关联数据（-> Labeled PSI）？
- 参与方是两个还是多个（-> Multi-Party PSI）？
第三步：评估性能、成本与数据规模
- 性能和通信成本是唯一瓶颈：数据量巨大，但安全要求不高，且可以容忍多一轮交互来消除误报 -> 布隆过滤器。
- 安全是首要考虑，但数据规模不大：数据集在十万到百万级别，希望有一个可靠、易于理解的强安全方案 -> DH-PSI。
- 安全和性能缺一不可：数据规模在百万级以上，需要半诚实安全保证，并且对性能有很高要求 -> OT-PSI (并使用现有库)。
第四步：考虑工程实现
- 对于所有公钥方案，永远不要自己从零实现。密码学实现中的任何微小错误都可能导致灾难性的安全漏洞。
- 优先使用封装好的高级库：如 OpenPSI, FALCON-PSI，它们提供了易于使用的接口。
- 需要极致定制或研究：可以深入更底层的库，如 libOTe。

未来展望

隐私集合求交是一个活跃的研究领域，仍在不断演进。

**抗量子密码 (Post-Quantum PSI)**：当前主流的公钥方案（DH, OT）都基于传统数论难题，在未来可能受到量子计算机的威胁。学术界正在积极研究基于格密码（Lattices）等抗量子困难问题的 PSI 新范式。
**硬件加速 (Hardware Acceleration)**：为了进一步突破性能瓶颈，研究者们正在探索使用 GPU、FPGA 等专用硬件来加速底层复杂的密码学运算（如OTe、椭圆曲线点乘），以满足更大规模、更低延迟的实时计算需求。