ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (10): 2153-2169.doi: 10.7544/issn1000-1239.2017.20170461

所属专题: 2017应用驱动的网络空间安全研究进展

• 综述 • 上一篇    下一篇



  1. 1(中国科学院大学网络空间安全学院 北京 100049); 2(中国科学院信息工程研究所 北京 100093) (
  • 出版日期: 2017-10-01
  • 基金资助: 

Survey on Private Preserving Set Intersection Technology

Shen Liyan1,2, Chen Xiaojun2, Shi Jinqiao2, Hu Lanlan2   

  1. 1 (School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049) 2 (Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093)
  • Online: 2017-10-01

摘要: 隐私保护集合交集(private set intersection, PSI)计算属于安全多方计算领域的特定应用问题,不仅具有重要的理论意义也具有很强的应用背景,在大数据时代,对该问题的研究更是符合人们日益强烈的在享受各种服务的同时达到隐私保护的需求.对安全多方计算基础理论进行了简要介绍,并重点介绍了目前主流的安全多方计算框架下2类PSI研究技术:传统的基于公钥加密机制,混乱电路,不经意传输的PSI协议和新型的云辅助的PSI协议,并对各类协议的过程、适用性、复杂性进行简要分析总结.同时,也对隐私保护集合交集问题的应用场景进行详细说明,进一步体现对该问题的实际研究价值.随着对该问题的不断深入研究,目前已经设计了在半诚实模型下快速完成上亿元素规模的隐私集合求交集协议.

关键词: 隐私保护集合交集, 安全多方计算, 不经意传输, 混乱电路, 不经意伪随机函数计算, 不经意多项式计算, 云计算

Abstract: The private set intersection (PSI) is a specific application problem that belongs to the field of secure multi-party computation. It not only has important theoretical significance but also has many application scenarios. In the era of big data, the research on this problem is in accord with people’s increasing privacy preserving demands at the same time to enjoy a variety of services. This paper briefly introduces the basic theory of secure multi-party computation, and highlights the two categories of current mainstream research methods of PSI under the framework of secure multi-party computation: the traditional PSI protocols based on the public key encryption mechanism, garbled circuit, oblivious transfer and the outsourced PSI protocols based on the untrusted third party service provider. Besides, we have briefly summarized the characteristic, applicability and complexity of those protocols. At the same time, the application scenarios of privacy preserving set intersection problem are also explained in detail, which further reflects the practical research value of the problem. With the deep research on the PSI problem, researchers have designed a set of private protocols that can quickly complete set intersection of millions of elements in the semi-honest model.

Key words: private set intersection (PSI), secure multi-party computation, oblivious transfer, garbled circuit, oblivious pseudorandom function evaluation, oblivious polynomial evaluation, cloud computing