作者:珊竹
加入vx隐私计算交流群,和作者一起学习:SecretFlow01
01.The Problem of Private Set Intersection
PSI 全称为 Private Set Intersection,直观的翻译名字为“隐私求交”。从场景来看,隐私求交:
- 有许多个参与方,每个参与方持有各自的隐私数据
- 希望通过协议求到所有数据的交集
- 但是不泄漏除交集外的任何信息
文章图片
目前常用的 PSI 算法有:
- ECDH [1]
- KKRT [2]
- PSTY [3]
文章图片
,这里
文章图片
是计算安全参数,通常我们可以取 128,基于 DH 的 PSI 协议如下所示。
1.2. KKRT 结合 Cuckoo hash 以及 batched OPRF,可以构造出一个比较高效的基于 OT 的 PSI 协议(由于 batched OPRF 的构建基于 OT,因此我们可以认为 KKRT16 的 PSI 协议是基于 OT 构建的)。协议具体内容如下图所示,我们将左边参与方叫做 Alice,右边参与方叫做 Bob。
文章图片
02.PSI 的应用场景
我们可以看到,(如果我们只考虑两方的场景下)PSI 场景中参与方我们记为 P0 以及 P1
- P0 持有数据:data0 = (X, A1, A2, A3, ....)
- P1 持有:data1 = (Y, B1, B2, B3, ....)
注意在 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 + 交集元素在 P1 处的 Payload
- P1 什么都没有得到
文章图片
这种情况我们需要一些 tricky 的方式来计算,
- 通过 case1 首先使 P0 获取到 “x2” 这条交集的 UID 数据;
- 【隐私计算技术(隐私求交(PSI)及其应用场景)】运行一个 Symmetric PIR 协议,或者 1-out-of-n OT 协议获取到 payload 的交集信息。
Case 3: 交集 UID 公开 在这个 case 中,双方均获取到最终交集的 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 的某个统计值
文章图片
注:本文讨论的方案仅限于半诚实安全模型,恶意安全需要另行讨论。
相关资料
【课程】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.” Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (2016): n. pag.
[3] Pinkas, Benny et al. “Efficient Circuit-based PSI with Linear Communication.” IACR Cryptol. ePrint Arch. 2019 (2019): 241.
推荐阅读
- 大数据|大数据实战电商推荐系统(3)-基于隐语义模型的离线推荐模块
- 开源|从蚂蚁可信隐私计算开源框架“隐语”看隐私计算发展挑战
- 源码教程|微信小程序(王者荣耀战力查询微信小程序源码下载支持安卓苹果微信QQ等多区查询)
- 大数据|常见大数据面试话术(建议收藏)
- docker|云原生时代下的容器镜像安全(上)
- python|UNIX文件系统命令
- 资讯|为什么有些程序员敲代码太慢,效率太低()
- 数据库|Mall电商实战项目专属学习路线,主流技术一网打尽!
- 芯片|从学术空间通往商业之路 系统性AI芯片专著《人工智能芯片设计》面世