定义

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

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

基于哈希的方案

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

  • A和B事先商量好一个哈希函数H()。
  • B发给A：$H(y_1),H(y_2),…,H(y_n)$.
  • A收到后与$H(x_1),H(x_2),…,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},…,(H(x_n))^{\alpha}$
  • B取随机数$\beta$，并发给A两个东西
    • 对收到数据的加密：$((H(x_1))^{\alpha})^{\beta},((H(x_2))^{\alpha})^{\beta},…,((H(x_n))^{\alpha})^{\beta}$
    • 对自己签名的数据的加密：$(H(x_1))^{\beta},(H(x_2))^{\beta},…,(H(x_n))^{\beta}$
  • A然后对B的数据加密：$((H(x_1))^{\beta})^{\alpha},((H(x_2))^{\beta})^{\alpha},…,((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,…,x_n\cdot(r_n)^e$
  • B给A发送的
    • 私钥加密后并签名的数据：$H((y_1)^d),H((y_2)^d),…,H((y_n)^d)$
    • $(x_1\cdot(r_1)^e)^d,(x_2\cdot(r_2)^e)^d,…,(x_n\cdot(r_n)^e)^d = (x_1)^d\cdot r_1,(x_2)^d\cdot r_2,…,(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)…(x-x_n)=a_nx^n+…+a_1x+a_0$，
  • A将系数通过同态加密后发送给B：$Enc(a_0),Enc(a_1),…,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.