【精选】Private Set Intersection（PSI） |
您所在的位置：网站首页 › psi实验 › 【精选】Private Set Intersection（PSI） |
【精选】Private Set Intersection（PSI）
|
1. 引言
PSI为当前secure-party computing (MPC) 安全多方计算的一个应用热点。 随着人们越来越关注用户数据的隐私保护，需在保护隐私的前提下，充分利用用户信息。 Private Set Intersection（PSI）私有集合交集： 是一种安全的多方计算加密技术，它允许持有集合的两方比较这些集合的加密版本以计算交集。在这种情况下，除了交叉点中的元素之外，双方都没有向对方透露任何信息。 PSI最常用的构建方式为： 服务器-客户端方案，在该方案中，只有客户端了解其集合与服务器集合的交集，而服务器不了解其集合与客户端的交集：
实际使用时，也存在变种，如： Client和Server都知道交集 X ∩ Y X\cap Y X∩Y；Client仅知道交集大小，即 size_of ( X ∩ Y ) \text{size\_of}(X\cap Y) size_of(X∩Y);对交集内容进行相关运算等等。PSI的主要特征为： two parties 两方；均不想暴露己方数据；想找到两方数据的交集 或者 对两方数据交集进行相关运算。基于PSI的以上特征，PSI的主要应用场景为： PSI的算法实现可有： 基于Hash的PSI：即借助公共hash函数，对hash结果进行比对来实现。基于公钥加密的PSI：基于circuit通用协议：是指将所需运算以circuit来表示，然后借助generic protocol通用协议来计算。基于OT (oblivious transfer) 不经意传输：是指将PSI问题等价理解为不经意传输问题来解决。在Benny Pinkas等人2016年论文《Scalable Private Set Intersection Based on OT Extension∗》对当前各种主流算法实现进行了对比: 基于Hash的PSI：即借助公共hash函数，对hash结果进行比对来实现。 这是一种很直观的实现方式，即： Alice和Bob agree on a “cryptographic hash function” H ( ) H() H();Bob对其输入集合内元素分别进行hash运算，并将hash结果发送给Alice： H ( y 1 ) , ⋯ , H ( y n ) H(y_1),\cdots, H(y_n) H(y1),⋯,H(yn)；Alice使用相同的hash函数对其集合内元素分别进行hash运算，比较 H ( x 1 ) , ⋯ , H ( x n ) H(x_1),\cdots,H(x_n) H(x1),⋯,H(xn)，比对与 H ( y 1 ) , ⋯ , H ( y n ) H(y_1),\cdots, H(y_n) H(y1),⋯,H(yn)的交集，即代表的是 x 1 , ⋯ , x n x_1,\cdots,x_n x1,⋯,xn与 y 1 , ⋯ , y n y_1,\cdots,y_n y1,⋯,yn之间的交集。这种方式的缺陷是不安全，即： 若熵不够大的话，不能保护Bob的隐私。 2.2 基于公钥加密的PSI基于公钥加密的PSI又分为： 基于Diffie-Hellman公钥加密的PSI基于RSA盲签名的PSI基于Oblivious polynomial evaluation的PSI 2.2.1 基于Diffie-Hellman公钥加密的PSI基于Diffie-Hellman公钥加密的PSI的安全性依赖于decisional Diffie-Hellman假设： 已知group G G G和相应的generator g g g，对于任意的随机值 a , b , c a,b,c a,b,c，无法区分 ( g a , g b , g a b ) (g^a,g^b,g^{ab}) (ga,gb,gab) 和 ( g a , g b , g c ) (g^a,g^b,g^c) (ga,gb,gc)。 详细的实现为： 详细可看 知乎 基于 DHKE 实现的 Private Set Intersection。 2.2.2 基于RSA盲签名的PSI详细的实现为： 主要是借助加密算法的加法同态属性，详细实现为： 基于通用协议的PSI： 是指将所需运算以circuit来表示，然后借助generic protocol通用协议来计算。 主要分为两个方向： 基于Goldreich Micali-Wigderson (GMW) protocol 计算协议；基于姚期智教授的混淆电路计算协议。【效率比GMW高。但若借助OT extension，GMW的效率要优于Yao的方案。】以[HEK12] Yan Huang等人2012年论文《Private set intersection: Are garbled circuits better than custom protocols?》为例，其将circuit分为3步： Sort：merge two sorted lists using a bitonic merging network [Bat68]. 使用
n
log
(
2
n
)
n\log(2n)
nlog(2n) comparisons。 Compare：compare adjacent items。使用 2 n 2n 2n equality checks。 Shuffle：Randomly shuffle results using a Waxman permutation network [W68]。使用 ∼ n log ( n ) \sim n\log(n) ∼nlog(n) swappings。 总体需要 L ⋅ ( 3 n log n + 4 n ) L\cdot (3n\log n+4n) L⋅(3nlogn+4n) 加法门，其中 L L L为input length， 2 / 3 2/3 2/3的加法门 are for multiplexers。 2.4 基于OT不经意传输的PSI基于OT (oblivious transfer) 不经意传输（又名，遗忘传输）的PSI： 是指将PSI问题等价理解为不经意传输问题来解决。 所谓OT不经意传输问题是指： Alice的输入为1个 bit b b b；Bob的输入为2个 bit x 0 , x 1 x_0,x_1 x0,x1；Alice想要知道 x b x_b xb。通过计算PSI来实现OT的思路为： Alice使用输入集合 ( b 0 , b 1 ) (b0, b1) (b0,b1)；Bob使用输入集合 ( 0 x 0 , 1 x 1 ) (0x_0, 1x_1) (0x0,1x1)。基于OT的PSI效率很高，可将OT与Hash结合，最大程度提升PSI的效率。 参考资料[1] csdn博客 Private Set Intersection（PSI）简介和资料分享 [2] 知乎 基于 DHKE 实现的 Private Set Intersection [3] OpenMined 博客 A PRIVACY-PRESERVING WAY TO FIND THE INTERSECTION OF TWO DATASETS [4] 维基百科 Private set intersection [5] 意大利银行报告 Privacy preserving set intersection [6] 以色列巴伊兰大学报告 Private Set Intersection [7] 百度安全X-Lab medium 博客 Private Set Intersection Technology: A Hot Topic in Multi-Party Computing [8] Avishay Yanai在Decentralized Thoughts 博客 Private Set Intersection |
主要优点为：
主要问题为：
【本文地址】
今日新闻 |
推荐新闻 |