隐私保护求交集PSI

定义

隐私集合求交（Private Set Intersection, PSI）允许持有各自隐私数据集的多方计算他们数据的交集，同时不泄露任何交集以外的信息。假设一方持有数据集A，另一方持有数据集B，则PSI的结果为A交B。A方从B方获得的信息仅为AB的交集；同理，B方从A方获得的信息仅为AB的交集。

⚠️：PSI在概念上集合持有者是完全平等的，但是在协议执行过程中，求交结果通常由一方首先获得，并同步给另一方。

基于哈希的方案

假设A拥有数据$\{x_1,x_2,\dots ,x_n\}$，B拥有数据$\{y_1,y_2,\dots ,y_n\}$。

• A和B事先商量好一个哈希函数H()。
• B发给A：$H(y_1),H(y_2),\dots ,H(y_n)$.
• A收到后与$H(x_1),H(x_2),\dots ,H(x_n)$比较，并找出相同项。

尽管这一协议是十分有效的，但是当「输入域较小」的时候存在着一方使用暴力碰撞攻击的可能(一方计算域上所有元素的哈希值，然后进行交集运算，从而得到另一方的所有输入)。当输入集合的取值范围非常大(>280）时，此种简单比较哈希值的协议也可以被证明是安全的。然而，如此大的输入域在现实应用中是不存在的。

优化

引入一个第三方服务提供商S，A、B双方分别发送自己数据集合的哈希值给S，由S计算交集并返回给A、B。由于S并不知晓哈希函数H，因此S无法通过明文生成对应的哈希值执行碰撞攻击。

优点

与朴素哈希方案性能几乎一致

缺点

• 需要辅助服务器长期在线
• 辅助服务器不能与任意一方共谋，否则依旧可以执行暴力碰撞攻击
• 服务器S可以通过长期缓存参与方的数据得到其几乎所有数据的哈希值，从而有能力使其离线，独自提供求交服务。

基于Diffie-Hellman问题的方案[M86,HFH99,AES03]

来自论文【3,4,5】

• A和B事先商量好一个群G，并商量好生成元g
• A取随机数$\alpha$，并把签名过的数据发给B，即发送：$(H(x_1){)}^{\alpha },(H(x_2){)}^{\alpha },\dots ,(H(x_n){)}^{\alpha }$
• B取随机数$\beta$，并发给A两个东西
  • 对收到数据的加密：$((H(x_1){)}^{\alpha }{)}^{\beta },((H(x_2){)}^{\alpha }{)}^{\beta },\dots ,((H(x_n){)}^{\alpha }{)}^{\beta }$
  • 对自己签名的数据的加密：$(H(x_1){)}^{\beta },(H(x_2){)}^{\beta },\dots ,(H(x_n){)}^{\beta }$
• A然后对B的数据加密：$((H(x_1){)}^{\beta }{)}^{\alpha },((H(x_2){)}^{\beta }{)}^{\alpha },\dots ,((H(x_n){)}^{\beta }{)}^{\alpha }$，并比较与B发来的数据中的相同项。

优点

不需要辅助服务器

缺点

公钥加密运算普遍需要昂贵的模幂等大数运算操作，计算开销较大。

基于Blind RSA的方案[CT10]

来自论文[6]。

• B生成密钥对$((N,e),d)$，A为每一个数据选一个随机数$r_i$，将数据用公钥加密后发给B：$x_1\cdot (r_1{)}^e,x_2\cdot (r_2{)}^e,\dots ,x_n\cdot (r_n{)}^e$
• B给A发送的
  • 私钥加密后并签名的数据：$H((y_1{)}^d),H((y_2{)}^d),\dots ,H((y_n{)}^d)$
  • $(x_1\cdot (r_1{)}^e{)}^d,(x_2\cdot (r_2{)}^e{)}^d,\dots ,(x_n\cdot (r_n{)}^e{)}^d=(x_1{)}^d\cdot r_1,(x_2{)}^d\cdot r_2,\dots ,(x_n{)}^d\cdot r_n$
• A收到第二串数据后，把每个数据除掉自己生成的随机数$r_i$，并用哈希函数加密就得到$H((x_i{)}^d)$，就可以比较两个集合相同的元素了。

基于Oblivious Polynomial Evaluation的方案[FNP04]

来自论文[7].

• A计算多项式$P(x)=(x-x_1)(x-x_2)\dots (x-x_n)=a_n{x}^n+\dots +a_{1}x+a_0$，
• A将系数通过同态加密后发送给B：$Enc(a_0),Enc(a_1),\dots ,Enc(a_n)$
• B为每个数据生成随机数$r_i$，B计算下式并发送给Alice：$Enc(P(y_i)\cdot r_i+y_i)$
• 如果$y_i=x_i$，那么B发送来的应该就是$E(y_i)$.A只要比较收到的数据是否与$Enc(x_i)$相等即可。

参考

【1】https://zhuanlan.zhihu.com/p/396327172

【2】https://zhuanlan.zhihu.com/p/407290294

【3】Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//1986 IEEE Symposium on Security and Privacy. IEEE, 1986: 134-134.

【4】 Ishai Y, Kilian J, Nissim K, et al. Extending oblivious transfers efficiently[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2003: 145-161.

【5】Steinfield, C., & Whitten, P. (1999). Community level socio-economic impacts of electronic commerce. Journal of Computer-Mediated Communication, 5(2), JCMC524.

【6】De Cristofaro, E., & Tsudik, G. (2010, January). Practical private set intersection protocols with linear complexity. In International Conference on Financial Cryptography and Data Security (pp. 143-159). Springer, Berlin, Heidelberg.

【7】Freedman, M. J., Nissim, K., & Pinkas, B. (2004, May). Efficient private matching and set intersection. In International conference on the theory and applications of cryptographic techniques (pp. 1-19). Springer, Berlin, Heidelberg.