问题综述 | 隐私求交(Private Set Intersection)

隐私求交(Private Set Intersection, PSI)可能是被研究最多的具体的多方安全计算（Secure Multiparty Computation, MPC）协议。PSI本质上是一种特殊的多方安全计算协议：计算双方各自有一个集合，要求双方协作共同计算出两者集合的交集，计算过程中（除了交集部分）不泄露任何和各自集合相关的信息。PSI属于一种特殊的多方安全计算，自然可以通过通用多方安全计算协议进行构造，但是效率通常不高^[1]。目前效率比较好的PSI都是基于一些特殊技术。下面基于这些特殊技术对PSI进行一个分类。

1

标准PSI的分类

这里讨论的PSI是标准PSI(standard PSI)。也就是说，只需安全地计算两个集合的交集即可，无需基于交集再做一些其他运算(secure computing over set intersection)。这里分成四大类简单描述如下。
基于密钥交换(Diffie-Hellman key exchange based)最早的PSI协议就是建立在Diffie-Hellman密钥交换的基础上^[2][3]，随后又被扩展到抵御恶意敌手攻击(malicious adversary attacks)^[4][5]。另外这篇论文^[6]提出一种利用RSA加密实现低通讯复杂度PSI的方法。这类PSI的通讯复杂度较低，这是它的一大优势。缺陷主要是密钥交换相关操作计算复杂度高，因此当计算双方的集合较大时，PSI的计算效率较低。
基于透明传输 (oblivious transfer based, OT-based)基于OT extension技术^[7]构造的PSI是目前的主流，通常和格式哈希算法(例如 simple hashing, permutation-based hashing, cuckoo hashing)搭配使用。由于OT extension技术的高效性(依赖轻量级的对称密码)，OT-based PSI的计算效率非常高，包括^{[7][8][9][10][11][12][13][14][15]}。特别是^[8]观察到OT-based PSI中的OT extension可以被视为batched OPRF(oblivious pseudorandom function)，他们提出的方法可能是目前为止最有竞争力的方法之一。
基于透明键-值(oblivious key-value stores based, OKVS-based)这类分支是近几年提出的全新方法。它依赖于对计算方拥有的集合进行一种特殊编码，使得其拥有透明数据结构(oblivious data structures)。这类方法最开始使用多项式插值技术^[16][17]导致计算效率偏低。后来^[18]提出了PaXoS数据结构极大地提高了计算效率，直接导致了目前效率最高的OKVS-based PSI的诞生^[19]。透明数据结构的概念和方法在^[20]得到进一步总结。

基于多项式操作(polynomial manipulation)这类分支需要将计算方拥有的集合表示成多项式，并通过相应的多项式操作(主要是oblivious Polynomial evaluation, OPE)等价地进行集合运算^{[21][22][23][24][25][26][27][28]}。这些方法通常较慢，但在其他方面也展现了一些优势。比如，可以在标准安全模型(standard model, 不依赖一些非标准安全假设，比如random oracle model)下论证安全性；可以提供除了求交集之外其他更丰富的计算功能(例如^[27]提到的threshold PSI)；当计算双方集合大小相差较大时通讯复杂度只依赖于较小集合的大小^[12]。

2

PSI变体

除了标准PSI, 学界对PSI的各式变体也进行了若干研究。其中最重要的是两个变式：隐私求交集基数(Private Intersection Cardinality)和阈值隐私求交(Threshold Private Set Intersection)。

隐私求交集基数

(Private Intersection Cardinality)

^{[21][22][29][30][31][14]}考虑如何安全地计算双方交集的大小，而不是交集本身。在论文^[21]给出了标准PSI的通讯复杂度的下限为。这里是计算双方较小集合的基数。这个下限同样适用于Private Intersection Cardinality问题。

阈值隐私求交

(Threshold Private Set Intersection)

在很多应用场景下，我们并不需要完整的计算出交集或者交集的基数。这里举两个例子说明问题。第一个例子，例如在指纹识别中，计算双方分别是用户自己的指纹信息和服务器指纹数据库。用户的指纹信息包括若干个匹配点，如果指纹信息中匹配点匹配上的个数超过某个阈值认为该用户指纹匹配成功。这里用户关心的是匹配成功与否，而不是交集的内容又或是交集的大小。第二个例子，约会网站一对男女想了解彼此的兴趣爱好是否一致，如果兴趣爱好重合较多，那么双方有进一步的必要，否则彼此不应该透露兴趣爱好。这类问题现在被称之为Threshold PSI。抽象地讲，在Threshold PSI协议中，计算双方各自拥有大小为的集合，如果交集的大小超过某个阈值(例如)，那么协议完成时计算双方获得交集，否则获得空集。

Threshold PSI在^{[32][28][14][33]}得到了深入研究。^[32]提出组合phasing技术和threshold key encapsulation mechanism技术可以构造threshold PSI。^[28]基于透明线性函数估值 (oblivious linear function evaluation, OLE) 技术和秘密分享 (robust secret sharing) 技术构造了可以抵御恶意敌手攻击的Threshold PSI。^[14]优化了基于通用多方安全性协议的比较电路从而构造了Threshold PSI。^[33]利用Paillier同态加密方案,透明多项式估值（oblivious polynomial evaluation, OPE), Bloom Filter 构造了Threshold PSI。^[27]揭示了当计算双方的交集很大时

(), threshold PSI通讯复杂度理论下界为。

3

参考文献

1. Huang, Yan, David Evans, and Jonathan Katz. "Private set intersection: Are garbled circuits better than custom protocols?." NDSS. 2012.

2. Meadows, Catherine. "A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party." 1986 IEEE Symposium on Security and Privacy. IEEE, 1986.

3. Huberman, Bernardo A., Matt Franklin, and Tad Hogg. "Enhancing privacy and trust in electronic communities." Proceedings of the 1st ACM conference on Electronic commerce. 1999.

4. Cristofaro, Emiliano De, Jihye Kim, and Gene Tsudik. "Linear-complexity private set intersection protocols secure in malicious model." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2010.

5. Jarecki, Stanisław, and Xiaomin Liu. "Fast secure computation of set intersection." International Conference on Security and Cryptography for Networks. Springer, Berlin, Heidelberg, 2010.

6. Ateniese, Giuseppe, Emiliano De Cristofaro, and Gene Tsudik. "(If) size matters: size-hiding private set intersection." International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, 2011. 

7. Pinkas, Benny, Thomas Schneider, and Michael Zohner. "Faster private set intersection based on {OT} extension." 23rd USENIX Security Symposium (USENIX Security 14). 2014. 

8. 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.

9. Pinkas, Benny, et al. "Phasing: Private set intersection using permutation-based hashing." 24th USENIX Security Symposium (USENIX Security 15). 2015.

10. Hazay, Carmit, and Muthuramakrishnan Venkitasubramaniam. "Scalable multi-party private set-intersection." IACR international workshop on public key cryptography. Springer, Berlin, Heidelberg, 2017.

11. Rindal, Peter, and Mike Rosulek. "Malicious-secure private set intersection via dual execution." Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.

12. Chen, Hao, Kim Laine, and Peter Rindal. "Fast private set intersection from homomorphic encryption." Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.

13. Orrù, Michele, Emmanuela Orsini, and Peter Scholl. "Actively secure 1-out-of-N OT extension with application to private set intersection." Cryptographers’ Track at the RSA Conference. Springer, Cham, 2017.

14. Pinkas, Benny, et al. "Efficient circuit-based PSI via cuckoo hashing." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2018.

15. Pinkas, Benny, Thomas Schneider, and Michael Zohner. "Scalable private set intersection based on OT extension." ACM Transactions on Privacy and Security (TOPS) 21.2 (2018): 1-35.

16. Pinkas, Benny, et al. "Spot-light: Lightweight private set intersection from sparse OT extension." Annual International Cryptology Conference. Springer, Cham, 2019.

17. Chase, Melissa, and Peihan Miao. "Private set intersection in the internet setting from lightweight oblivious PRF." Annual International Cryptology Conference. Springer, Cham, 2020.

18. Pinkas, Benny, et al. "PSI from PaXoS: fast, malicious private set intersection." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2020.

19. Rindal, Peter, and Phillipp Schoppmann. "VOLE-PSI: fast OPRF and circuit-psi from vector-ole." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2021.

20. Garimella, Gayathri, et al. "Oblivious key-value stores and amplification for private set intersection." Annual International Cryptology Conference. Springer, Cham, 2021.

21. Freedman, Michael J., Kobbi Nissim, and Benny Pinkas. "Efficient private matching and set intersection." International conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2004.

22. Kissner, Lea, and Dawn Song. "Privacy-preserving set operations." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2005.

23. Dachman-Soled, Dana, et al. "Efficient robust private set intersection." International Conference on Applied Cryptography and Network Security. Springer, Berlin, Heidelberg, 2009.

24. Hazay, Carmit, and Kobbi Nissim. "Efficient set operations in the presence of malicious adversaries." International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, 2010.

25. Hazay, Carmit. "Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs." Journal of Cryptology 31.2 (2018): 537-586.

26. Freedman, Michael J., et al. "Efficient set intersection with simulation-based security." Journal of Cryptology 29.1 (2016): 115-155.

27. Ghosh, Satrajit, and Mark Simkin. "The communication complexity of threshold private set intersection." Annual International Cryptology Conference. Springer, Cham, 2019.

28. Ghosh, Satrajit, and Tobias Nilges. "An algebraic approach to maliciously secure private set intersection." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2019.

29. Hohenberger, Susan, and Stephen A. Weis. "Honest-verifier private disjointness testing without random oracles." International Workshop on Privacy Enhancing Technologies. Springer, Berlin, Heidelberg, 2006.

30. Debnath, Sumit Kumar, and Ratna Dutta. "Secure and efficient private set intersection cardinality using bloom filter." International Conference on Information Security. Springer, Cham, 2015.

31. Egert, Rolf, et al. "Privately computing set-union and set-intersection cardinality via bloom filters." Australasian Conference on Information Security and Privacy. Springer, Cham, 2015.

32. Hallgren, Per, Claudio Orlandi, and Andrei Sabelfeld. "PrivatePool: Privacy-preserving ridesharing." 2017 IEEE 30th Computer Security Foundations Symposium (CSF). IEEE, 2017.

33. Zhao, Yongjun, and Sherman SM Chow. "Can you find the one for me?." Proceedings of the 2018 Workshop on Privacy in the Electronic Society. 2018.

作者知乎：hujwei

本文来源：https://zhuanlan.zhihu.com/p/586433710

END

往期推荐

案例分享 | 联邦学习在洗钱风险管理中的应用展望
上岸！选择你的隐私计算导师！
《计算机研究与发展》2022刊登安全与隐私保护相关论文整理
对于多方安全计算，你是否也有这样的疑惑？

欢迎投稿邮箱：[e-mail]参与更多讨论，请添加小编微信加入交流群