ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (10): 2153-2169.doi: 10.7544/issn1000-1239.2017.20170461

Special Issue: 2017应用驱动的网络空间安全研究进展

Previous Articles     Next Articles

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

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

CLC Number: