隐私集合交集（PSI）算法分析与实验对比

一、什么是隐私集合交集（PSI）？ 隐私集合交集（Private Set Intersection, PSI）是一种经典的安全多方计算技术。

其目标是：

在不泄露双方原始数据的前提下，计算两个集合的交集。

一个典型场景：

两家医院希望寻找共同患者； 但不愿泄露各自独有的数据。 PSI 技术便可以解决这一问题。

二、PSI 技术路线分类 目前主流 PSI 方案主要可以分为三类：

不同路线具有不同特点：

• DH-based PSI 更适合小规模集合；
• OT-based PSI 更适合中大型集合；
• HE-based PSI 更适合非对称查询场景。

三、DH-based PSI DH-based PSI 是最经典的一类 PSI 协议。

其核心思想来源于：

$$ (g^a)^b = (g^b)^a $$

协议通常依赖：

• ECDH
• OPRF
• ECC 运算

特点包括：

• 通信量较低；
• 工程实现简单；
• 小规模集合性能优秀。

本文测试以下三种 DH-based PSI：

• DH-PSI
• JL10-PSI
• MiniPSI

1. Runtime Comparison

2. Communication Comparison

3. 实验分析

从实验结果可以看出：

• 三种算法均呈线性增长趋势；
• MiniPSI 在运行时间与通信量方面均表现更优；
• DH-PSI 与 JL10-PSI 整体性能接近。

其中：

MiniPSI 通过 subset-sum 与 polynomial encoding 进一步压缩了通信量，因此在小规模集合场景下具有更好的整体性能。

四、OT-based PSI
OT-based PSI 主要基于：

• Oblivious Transfer
• OKVS
• Sparse OT Extension

相比 DH-based PSI：

• 更适合大规模集合；
• 在线阶段更快；
• 更适合工业场景。

本文测试：

• SpOT-fast
• SpOT-low

1. Runtime Comparison

2. Communication Comparison

3. 实验分析

实验结果表明：

• SpOT-fast 运行速度明显更快；
• SpOT-low 通信量更低；
• 当集合规模增大后，两者差异进一步扩大。

因此：

• SpOT-fast 更适合低延迟场景；
• SpOT-low 更适合带宽敏感环境。

五、HE-based PSI
HE-based PSI（Homomorphic Encryption-based PSI）主要基于：

• BFV Homomorphic Encryption
• Polynomial Evaluation
• OPRF
• Cuckoo Hashing

代表算法包括：

• Microsoft APSI

相比：

• DH-based PSI
• OT-based PSI

HE-based PSI 更适用于：

$$ |Y| \ll |X| $$

即：

Receiver 查询集合较小； Sender 数据库规模巨大； 的大规模非对称查询场景。

1. APSI 实验结果

说明：

• R→S：Receiver → Sender 的通信量；
• S→R：Sender → Receiver 的通信量。

实验结果表格略（保持你原文内容）。

2. JSON 参数文件说明

（保持你原文内容）

3. 实验现象分析

（保持你原文内容）

4. 核心结论

（保持你原文内容）

六、总结

不同 PSI 技术路线适用于不同场景