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
基于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详细的实现为： 
主要问题为：
- 只有拥有私钥的一方才能做all the hard work，无法双方并行。
- 无法使用elliptic curve crypto。
主要是借助加密算法的加法同态属性，详细实现为： 
基于通用协议的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
