打开链接即可点亮社区Star，照亮技术的前进之路。

Github 地址：https://github.com/secretflow/secretflow

The Problem of Private Set Intersection

PSI 全称为 Private Set Intersection，直观的翻译名字为"隐私求交"。

从场景来看，隐私求交：

• 有许多个参与方，每个参与方持有各自的隐私数据
• 希望通过协议求到所有数据的交集
• 但是不泄漏除交集外的任何信息

目前常用的 PSI 算法有：

• ECDH [1]
• KKRT [2]
• PSTY [3]

1.1 ECDH

如果我们假设哈希函数

这里是入计算安全参数，通常我们可以取 128。

基于 DH 的 PSI 协议如下所示：

1.2 KKRT

结合 Cuckoo Hash 以及 Batched OPRF，可以构造出一个比较高效的基于 OT 的 PSI 协议。

由于 Batched OPRF 的构建基于 OT，因此我们可以认为 KKRT16 的 PSI 协议是基于 OT 构建的。

协议具体内容如下图所示，我们将左边参与方叫做 Alice ，右边参与方叫做 Bob。

PSI 的应用场景

我们可以看到（如果只考虑两方的场景下）：PSI 场景中参与方我们记为 P0 以及 P1

P0 持有数据：data0 = (X, A1, A2, A3, ....)

P1 持有：data1 = (Y, B1, B2, B3, ....)

这里 X、Y 表示想要"撞库"使用的匹配字段（类似于 UID），而 Ai、Bi 指的是可能存在的其他数据信息。

我们假设在所有两方 PSI 场景下想要比对的数据用下图方式表示。我们假设 data0 和 data 1 中只有一条数据是匹配的，即 y1 和 x2。

在 PSI 中需要重点保护的是：

• X 与 Y 的 非交集元素

Case 1: 指定参与方获取交集 UID

通常来说，在 PSI 中我们指定可以指定某个参与方（例如 P0）获取到 UID 的 PSI 结果。

在下面这种场景下，

• P0 得知交集的 UID
• P1 什么都没有得到

（几乎）所有的已知 PSI 协议都可以实现，例如 KKRT、ECDH PSI 等。

Case 2: 指定参与方获取交集 UID 以及 Payload

通常来说，在 PSI 中我们指定可以指定某个参与方（例如 P0）获取到 UID 以及 Payload 的 PSI 结果。在下面这种场景下，

• P0 得知交集的 UID + 该 UID 对应在 P1 的 Payload
• P1 什么都没有得到

这种情况我们需要一些 tricky 的方式来计算

1. 通过 Case 1，使 P0 获取交集的 UID（如 x2）
2. 运行一个 Symmetric PIR 协议，或者 1-out-of-n OT 协议，获取 Payload 信息

也存在更高效的方案，这里不赘述。

Case 3: 交集 UID 公开

在该场景中：

• 双方都获得交集的 UID 信息

所有已知 PSI 协议均可实现该功能。

Case 4: 交集 UID 公开，指定方获取 Payload

所有的已知 PSI 协议都可以实现上述功能。只需要在 case3 的基础上让 P1 将 payload 发送给 P0 即可。

Case 5: 双方数据集规模差异大（性能提升）

传统的 PSI 协议一般假设了双方数据集大小类似的情况，因此在 unbalanced 场景中我们需要特定设计的 PSI 协议来完成协议加速。

需要注意的是在 unbalanced 的场景下其实并不影响我们解决 case 1 - case 4 的所有应用场景，这里我们只以 case 3 的场景作为例子。

Case 6: 获取交集 UID 或 Payload 的统计值

在法律法规、用户隐私要求较高的场景中，我们需要对交集信息进行保护。因此在下面这种场景下，

• P0 得知了 双方交集 UID 的某个统计值

• P1 得知了 双方交集 UID 的某个统计值

如果我们想要同时对 Payload 进行计算，会牺牲较大的性能，可以达到的效果是：

• P0 得知了双方 交集 UID 的某个统计值 或者 Payload 的某个统计值

• P1 得知了双方 交集 UID 的某个统计值 或者 Payload 的某个统计值

注：本文所讨论方案仅限于 半诚实安全模型，恶意安全模型需另行讨论。

💡既然来都来了，花个1分钟点个 Star 再走吧！开源不易，每个人的点赞，都是社区技术大佬前进的动力~

打开链接即可点亮社区Star，照亮技术的前进之路。

Github 地址：https://github.com/secretflow/secretflow

相关资料

• 📚 课程：https://cyber.biu.ac.il/event/the-12th-biu-winter-school-on-cryptography/
• 💻 代码：https://github.com/osu-crypto/libPSI

参考文献

[1] Agrawal, Rakesh et al. Information sharing across private databases. SIGMOD '03 (2003)

[2] Kolesnikov, Vladimir et al. Efficient Batched Oblivious PRF with Applications to Private Set Intersection. CCS (2016)

[3] Pinkas, Benny et al. Efficient Circuit-based PSI with Linear Communication. IACR Cryptol. ePrint Arch. 2019 (2019): 241

本文由隐语社区统一发布，欢迎大家点 Star