ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2022, Vol. 59 ›› Issue (8): 1782-1799.doi: 10.7544/issn1000-1239.20210685

• 信息安全 • 上一篇    下一篇



  1. (上海海洋大学信息学院 上海 201306) (
  • 出版日期: 2022-08-01
  • 基金资助: 

Survey of Privacy Preserving Oriented Set Intersection Computation

Wei Lifei, Liu Jihai, Zhang Lei, Wang Qin, He Chongde   

  1. (College of Information Technology, Shanghai Ocean University, Shanghai 201306)
  • Online: 2022-08-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61972241), the Natural Science Foundation of Shanghai (18ZR1417300, 22ZR1427100), the Open Project of Shanghai Key Laboratory of Trustworthy Computing (OP202102), Shanghai Sailing Program (21YF1417000), and the Luo Zhaorao College Student Science and Technology Innovation Fund of Shanghai Ocean University (A1-2004-20-201312, A1-2004-21-201311).

摘要: 随着物联网和大数据技术的发展,在计算机和手机上出现了大量分布式应用程序.然而现有的分布式数据处理方式已不能很好地满足用户对隐私保护的需求.隐私集合交集(private set intersection, PSI)协议作为一项典型的面向隐私保护的分布式集合计算技术,允许各参与方输入其私有集合,共同计算集合的交集,且不泄露除交集以外的任何信息.PSI协议作为安全多方计算的一种重要应用,已被广泛应用于隐私计算领域,具有重要的理论和实践意义.首先介绍PSI协议的基本密码技术、敌手模型、安全证明、编程框架等基础知识;其次系统总结了构造传统PSI协议的设计框架: 基于公钥加密体制的框架、基于混淆电路的框架、基于不经意传输的框架;随后介绍PSI协议核心的隐私集合元素比较技术/工具: 不经意伪随机函数、不经意多项式评估、布隆过滤器等;进一步地详细阐述了适应新型应用场景的PSI方案: 基于云辅助的PSI、非平衡型PSI、基于阈值的PSI和多方PSI;最后总结并展望面向隐私保护的集合交集计算中亟待解决问题和发展方向.

关键词: 隐私集合求交, 安全多方计算, 隐私保护, 不经意传输, 混淆电路

Abstract: With the development of Internet of things and big data technology, increasing distributed applications are booming in the personal computers and mobile phones. However, the existing distributed data processing methods have not met the needs of privacy protection. As a typical privacy-preserving technology for distributed set computation, private set intersection (PSI) protocols allow the participants to input individual sets and jointly calculate the intersection of these sets without disclosing any information except the intersection. As an important application of secure multiparty computation, PSI protocols have been widely used in privacy-preserving computation, which has theoretical and practical significance. Many PSI protocols have been emerged, but due to the lack of related surveys on PSI, we have written this paper. This paper introduces the fundamentals of PSI protocols such as the cryptographic technology, adversary model, security proof and implementation framework. And then the paper systematically summarizes the cryptographic framework of traditional PSI protocol from three aspects: the framework based on public key cryptosystem, garbled circuit, and oblivious transfer. Some of the key technologies in the set element comparison are introduced such as oblivious pseudo-random function, oblivious polynomial evaluation, and Bloom filter. Furthermore, a few of emerging PSI application scenarios are described in detail such as cloud-based PSI, unbalanced PSI, threshold PSI, and multiparty PSI. Finally, the paper summarizes the problems to be solved and prospects some possible development directions of PSI.

Key words: private set intersection, secure multiparty computation (MPC), privacy preserving, oblivious transfer, garbled circuit