Protocol of Privacy-preserving Set Intersection Computation

doi:10.3969/j.issn.1671-1122.2020.01.002

Abstract

Abstract:

Privacy-preserving set intersection computation is a special application problem in the field of secure multi-party computation, which has important research value and a wide range of application. In the era of rapid development of information, the study on this problem meets the needs of people for privacy protection while people enjoy various conveniences in daily life. This paper considers the privacy-preserving set intersection of two participants. First, the problem of solving the intersection of two sets is transformed into the problem of solving the greatest common factor of two polynomials by expressing sets as polynomials. Then, according to the mathematical properties of polynomials and Pailliar homomorphic encryption algorithm, a protocol of privacy-preserving two-party set intersection computation is designed, and the correctness and the security analyses of the protocol are given. Finally, through the comparison and analysis with the related literature, it is concluded that the computational complexity and communication complexity of the proposed protocol are relatively low, and the number of elements in the participant set can be well protected.

Key words: secure multi-party computation, privacy-preserving, set intersection, Pailliar homomorphic encryption algorithm

CLC Number:

TP309

TANG Chunming, LIN Xuhui. Protocol of Privacy-preserving Set Intersection Computation[J]. Netinfo Security, 2020, 20(1): 9-15.

Figures/Tables 2

References 16

[1]	YAO A C.Protocols for Secure Computations[C]//IEEE. 23rd Annual Symposium on Foundations of Computer Science, November 3-5, 1982, Chicago, IL, USA. NJ: IEEE, 1982: 160-164.
[2]	BENOR M, GOLDWASSER S, WIGDERSON A, et al.Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computation[C]//ACM. The Twentieth Annual ACM Symposium on Theory of Computing, May 2- 4, 1988, Chicago, Illinois, USA. New York: ACM, 1988: 1-10.
[3]	FREEDMAN M J, NISSIM K, PINKAS B, et al.Efficient Private Matching and Set Intersection[M]//Springer. Advances in Cryptology- Eurocrypt 2004. Heidelberg: Springer, Berlin, 2004: 1-19.
[4]	KISSNER L, SONG D. Privacy-preserving Set Operations[EB/OL]. , 2019-6-30.
[5]	DONG Changyu, CHEN Liqun, WEN Zikai, et al.When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol[C]//ACM. The 2013 ACM SIGSAC Conference on Computer & Communications security, November 4- 8, 2013, Berlin, Germany. New York: ACM, 2013: 789-800.
[6]	PINKAS B, SCHNEIDER T, ZOHNER M.Faster Private Set Intersection Based on OT Extension[C]// USENIX. The 23rd USENIX Conference on Security Symposium, August 20-22, 2014, San Diego, CA. Berkeley: USENIX Association, 2014: 797-812.
[7]	CHEN Zhenhua, LI Shundong, HUANG Qiong, et al.Protocols for Secure Computation of Two Set-relationships with the Nnencrypted Method[J]. Journal of Software, 2018, 29(2): 473-482.
	陈振华,李顺东,黄琼,等.非加密方法安全计算两种集合关系[J].软件学报,2018, 29(2):473-482.
[8]	ZHOU Sufang, LI Shundong, GUO Yiming, et al.Efficient Set Intersection Problem Computation[J]. Chinese Journal of Computers, 2018, 41(2): 464-480.
	周素芳,李顺东,郭奕旻,等.保密集合相交问题的高效计算[J].计算机学报,2018,41(2):464-480.
[9]	DOU Jiawei, LIU Xuhong, ZHOU Sufang, et al.Efficient Protocol and Application of Secure Multi-party Set Computation[J]. Chinese Journal of Computers, 2018, 41(8): 1844-1860.
	窦家维,刘旭红,周素芳,等.高效的集合安全多方计算协议及应用[J].计算机学报,2018,41(8):1844-1860.
[10]	HAZAY C, NISSIM K.Efficient Set Operations in the Presence of Malicious Adversaries[J]. Journal of Cryptography, 2012, 25(3): 383-433.
[11]	FREEDMAN M J, HAZAY C, NISSIM K, et al.Efficient Set Intersection with Simulation-Based Security[J]. Journal of Cryptology, 2016, 29(1): 115-155.
[12]	DACHMANSOLED D, MALKIN T, RAYKOVA M, et al.Efficient Robust Private Set Intersection[M]//Springer. Applied Cryptography and Network Security. Heidelberg: Springer, Berlin, 2009: 125-142.
[13]	DONG Changyu, CHEN Liqun, CAMENISCH J, et al.Fair Private Set Intersection with a Semi-trusted Arbiter[M]//Springer. Data and Applications Security and Privacy XXVII. Heidelberg: Springer, Berlin, 2013: 128-144.
[14]	LIU Fang, NG W K, ZHANG Wei, et al.Encrypted Set Intersection Protocol for Outsourced Datasets[C]//IEEE. 2014 IEEE International Conference on Cloud Engineering, March 11-14, 2014, Boston, MA, USA. NJ: IEEE, 2014: 35-140.
[15]	PAILLIER P.Public-key Cryptosystems Based on Composite Degree Residuosity Classes[C]//Springer. The 17th International Conference on Theory and Application of Cryptographic Techniques, May 2-6, 1999, Prague, Czech Republic. Heidelberg: Springer-Verlag Berlin, 1999: 223-238.
[16]	OEDE G.Foundations of Cryptography Volume 2: Basic Applications[J]. Foundations of Cryptography, 2009, 2(1): 1-14.

协议	加解密多项式操作次数	多项式运算次数
文献[4]协议	3	7
本文协议	3	2

协议	通信轮数
文献[4]协议	6
本文协议	2