隐私集合求交（PSI）：密码学中的隐私保护交集计算

摘要：隐私集合求交（Privacy-Preserving Set Intersection，简称PSI）是安全多方计算（MPC）的核心原语之一，由Kissner和Pierre于2005年正式提出。它允许两个参与方在不暴露各自集合中非交集元素的前提下，安全地计算集合交集。本文从安全模型、协议构造、性能分析与工程应用四个维度系统阐述PSI技术。

---

一、问题定义与安全模型

1.1 PSI的形式化定义

设 Alice 持有集合 $A = \{a_1, a_2, \ldots, a_m\}$，Bob 持有集合 $B = \{b_1, b_2, \ldots, b_n\}$，其中所有元素均来自一个公开的大域 $\mathcal{U}$。PSI协议的目标是：

• Alice 最终获得 $A \cap B$
• Bob 最终获得 $A \cap B$
• Alice 无法获知 $B \setminus A$ 中的任何元素
• Bob 无法获知 $A \setminus B$ 中的任何元素

形式化地，令 $f(A, B) = A \cap B$，PSI是一个两方协议，输出满足上述隐私约束。

1.2 安全模型

PSI的安全模型主要基于半诚实（semi-honest）模型和恶意（malicious）模型两种假设：

安全模型	假设条件	安全性含义
半诚实模型	参与方忠实执行协议，但试图从消息中学习额外信息	模拟不可区分性（Simulatability）
恶意模型	参与方可能偏离协议，任意操控输入和行为	需额外引入零知识证明或一致性验证

在半诚实模型下，协议安全性通过模拟器（Simulator）来定义：对于任意参与方的视图（View），存在一个模拟器能够仅利用该方的输入和输出生成一个计算上不可区分的仿真视图。

---

二、OT-Based PSI：最经典的两方PSI方案

2.1 基本思想

基于不经意传输（Oblivious Transfer, OT）的PSI是最早被提出的方案之一，由Kissner和Pierre在2005年提出，其核心思路如下：

• Bob将其集合 $B$ 中的每个元素通过加密方式"标记"
• Alice通过OT协议选择性地获取自己集合中元素的加密对应值
• 若Alice的元素在Bob的集合中，则解密后可得到特定标记；否则得到随机值

2.2 协议步骤

预处理阶段：

• Bob选择一个大素数 $p$ 和生成元 $g$，计算 $h = g^x \mod p$，其中 $x$ 为随机选取的指数，$(p, g, h)$ 作为公钥公开
• 对于 $B$ 中每个元素 $b_j$，Bob计算 $e_j = h^{b_j} \mod p$，并将 $\{e_1, e_2, \ldots, e_n\}$ 发送给Alice

查询阶段：

• 对于 $A$ 中每个元素 $a_i$，Alice发起一次OT协议：

- Alice拥有选择比特 $k_i = 1$（表示"我请求查询 $a_i$"） - Bob拥有两个消息 $(e_j, r_j)$，其中 $r_j$ 是随机数 - Alice通过OT获得 Bob 根据 $k_i$ 选择的消息

• Alice收到加密后的值后，利用同态性质判断 $a_i$ 是否在 $B$ 中

结果输出：

• Alice根据解密结果确定交集 $A \cap B$，并通过额外OT将结果告知Bob

2.3 安全性质分析

• Bob的隐私：Alice通过OT只能获取她所选元素的对应值，无法获取其他元素的信息
• Alice的隐私：Bob在OT协议中无法得知Alice选择了哪些元素（选择比特的隐私）
• 复杂度：通信复杂度为 $O(m + n)$，计算复杂度为 $O(m \cdot \text{OT})$，其中 OT 表示一次不经意传输的计算开销

2.4 协议优化

原始的OT-based PSI存在效率瓶颈。后续研究提出了多项优化：

基于扩展OT的PSI（Ishai et al., 2003）：

• 利用 OT Extension 技术，将少量基础OT扩展为大量OT
• 大幅降低通信和计算开销
• 已成为现代PSI实现的标准做法

基于哈希的PSI（Ristenpart and Yummel, 2011）：

• 使用密码学哈希函数替代同态加密
• 协议交互轮数更少
• 适合大规模集合场景

---

三、HE-Based PSI：同态加密方案

3.1 基本思想

基于同态加密（Homomorphic Encryption, HE）的PSI方案利用 paillier 等加法同态加密方案的特性，允许在加密数据上直接进行集合操作。

3.2 协议流程（以Paillier为例）

Bob的预处理：

• Bob生成Paillier密钥对 $(pk, sk)$
• 对于 $B$ 中每个元素 $b_j$，Bob计算 $E(pk, b_j)$
• Bob将所有加密值发送给Alice

Alice的查询：

• Alice对于 $A$ 中每个元素 $a_i$，计算：

$$c_i = E(pk, 1) \cdot \prod_{j=1}^{n} E(pk, b_j)^{r_{ij}} \mod N$$ 其中 $r_{ij}$ 是随机数，用于隐藏查询意图

• Alice将 $c_i$ 发送给Bob

Bob的解密与返回：

• Bob解密 $D(sk, c_i)$，根据解密结果判断 $a_i \in B$
• Bob将结果返回给Alice（通过OT或其他方式）

3.3 安全性分析

• Paillier加密具有语义安全性，Alice无法从 $E(pk, b_j)$ 推断出 $b_j$
• 随机数 $r_{ij}$ 隐藏了Alice的查询模式
• Bob需要额外引入零知识证明以确保Alice的行为诚实（在恶意安全模型下）

3.4 优缺点对比

特性	OT-based PSI	HE-based PSI
通信量	$O(m \cdot \lambda)$ bit	$O(n \cdot \lambda)$ bit（$\lambda$ 为安全参数）
计算量	Alice侧较重	Bob侧较重（解密开销）
交互轮数	较多	较少（可做到2轮）
扩展性	良好（OT扩展）	受限于同态加密计算成本
恶意安全	需额外证明	需额外验证

---

四、GC-Based PSI：混淆电路方案

4.1 基本思想

混淆电路（Garbled Circuit, GC）由Yao在1986年提出，可将任意布尔电路转换为"混淆"版本。将PSI问题转化为一个布尔电路后，双方可通过GC协议安全计算交集。

4.2 电路构造

PSI可构造为一个电路 $C$：

• 输入：Alice的集合 $A$（作为Alice的输入线）和Bob的集合 $B$（作为Bob的输入线）
• 输出：对于每个 $a_i \in A$，输出位 $y_i = 1$ 当且仅当 $a_i \in B$

电路由比较器和AND门组成： $$y_i = \bigvee_{j=1}^{n} (a_i = b_j)$$

其中每个比较操作可以通过 $O(\log |U|)$ 位进行。

4.3 性能特征

• 优势：理论复杂度最优，通信量可做到 $O(\min(m, n) \cdot \lambda)$
• 劣势：常数因子较大，实际实现中不如OT方案高效
• 适用场景：小规模集合、低延迟要求的场景

---

五、多方可扩展PSI（Scalable PSI）

5.1 问题扩展

上述方案均为两方PSI。在实际应用中，常需要多方参与的场景，如：

• 多个企业联合进行客户重叠检测
• 多个政府机构共享黑名单信息
• 多方协同的风险评估

5.2 主流方案

基于OT的多方PSI（Cohen and Pietrzak, 2008）：

• 将两方PSI推广到多方场景
• 通信复杂度为 $O(k \cdot \min(|S_1|, \ldots, |S_k|))$，其中 $k$ 为参与方数量
• 通过OT Extension技术在多方场景下仍保持效率

基于HE的多方PSI（Bagga and Evans, 2020）：

• 利用全同态加密（FHE）或层级同态加密（Levelled HE）
• 所有参与方同时上传加密集合
• 服务器执行聚合计算后返回结果
• 服务器无法获知任何信息（可证明安全）

5.3 开源实现

目前业界主流的PSI开源实现包括：

• PSI-PRIME：基于OT Extension的高效两方PSI
• Differential Privacy PSI：结合差分隐私的多方PSI
• Microsoft SEAL：支持同态加密的PSI实现

---

六、典型应用场景

6.1 广告行业的用户重合度分析

广告主A和广告主B希望知道两者的目标用户群体有多少重合，但不愿泄露各自的完整用户列表。PSI可以安全地计算： $$\text{重合用户数} = |U_A \cap U_B|$$ 且双方无法获知非重合用户的任何信息。

6.2 跨机构黑名单共享

银行、支付平台、电商平台等机构希望共享黑名单（如欺诈用户、恶意商家），但不愿公开完整的黑名单数据。PSI允许：

• 机构A查询某用户是否在机构B的黑名单中
• 双方无法获知对方的完整黑名单

6.3 医疗数据协作研究

多家医院希望联合进行疾病研究，共享患者数据但不泄露患者隐私。PSI可用于：

• 识别多医院中具有相同疾病特征的患者集合
• 保护各医院的患者隐私

6.4 跨境数据传输合规

在GDPR等数据保护法规下，跨国企业需要在不传输原始数据的前提下验证用户身份。PSI提供了一种"数据可用不可见"的解决方案。

---

七、性能基准与选型建议

7.1 性能对比（参考ePrint 2015/267）

方案	集合大小	通信量	计算时间
OT-based PSI	$10^4$ 元素	~10 MB	~2秒
OT-based PSI	$10^6$ 元素	~1 GB	~5分钟
HE-based PSI	$10^4$ 元素	~500 KB	~10秒
HE-based PSI	$10^5$ 元素	~5 MB	~30秒

7.2 选型指南

场景特征	推荐方案
小规模集合（$< 10^4$），低延迟要求	OT-based PSI
大规模集合（$> 10^6$），可接受分钟级延迟	HE-based PSI
多方场景	OT Extension-based 多方PSI
服务端协助模型	FHE-based PSI

---

八、总结与展望

隐私集合求交（PSI）作为安全多方计算的核心原语，已在广告、金融、医疗等多个领域展现出应用价值。随着OT Extension、同态加密等基础技术的不断进步，PSI的性能瓶颈正在逐步突破。

未来研究方向包括：

• 恶意安全模型的进一步优化：减少零知识证明的开销
• 与差分隐私的融合：在PSI中提供额外的隐私保障
• 硬件加速：利用GPU/FPGA加速OT和同态加密计算
• 标准化：推动PSI协议的行业标准制定

---

参考文献

• Kissner, L., & Pierre, J. M. (2005). Privacy-Preserving Set Operations. *Financial Cryptography 2005*. ePrint 2005/186
• Ostrovsky, R., & Raab, M. (2005). Private Set Intersection. *Cryptology ePrint Archive*. ePrint 2005/055
• Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A. (2003). Cryptography with Polynomial Communication Complexities. *CRYPTO 2003*. ePrint 2003/074
• Cohen, G., & Pietrzak, K. (2008). Simple Protocols for Secure Computation. *IACR ePrint Archive*. ePrint 2008/279
• Bagga, P., & Evans, G. (2020). Practical Two-Party and Multi-Party Private Set Intersection. *IACR ePrint Archive*. ePrint 2020/788
• Ristenpart, T., & Yummel, D. (2011). Practical Private Set Intersection from Local Differential Privacy. *arXiv:1106.6329*
• Freedman, M. J., Nissim, K., & Pinter, R. (2004). Efficient Private Set Intersection. *Cryptology ePrint Archive*. ePrint 2004/225