隐私保护集合交集计算协议

doi:10.3969/j.issn.1671-1122.2020.01.002

信息网络安全 ›› 2020, Vol. 20 ›› Issue (1): 9-15.doi: 10.3969/j.issn.1671-1122.2020.01.002

隐私保护集合交集计算协议

唐春明(), 林旭慧

广州大学数学与信息科学学院,广州510006

收稿日期:2019-07-15 出版日期:2020-01-10 发布日期:2020-05-11
作者简介:
作者简介：唐春明（1972—）,男,湖南,教授,博士,主要研究方向为信息安全、密码学;林旭慧（1995—）,女,广东,硕士研究生,主要研究方向为信息安全、密码学。
基金资助:
国家自然科学基金面上项目[61772147];广东省自然科学基金基础研究重大项目[2015A030308016];广东省教育厅科研团队项目[2015KCXTD014];广州市教育局协同创新重大项目[1201610005];国家密码发展基金[MMJJ20170117]

Protocol of Privacy-preserving Set Intersection Computation

TANG Chunming(), LIN Xuhui

School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China

Received:2019-07-15 Online:2020-01-10 Published:2020-05-11

摘要/Abstract

摘要：

隐私保护集合交集计算属于安全多方计算领域的特定应用问题,具有重要的研究价值和广泛的应用范围。在信息高速发展的时代,对该问题的研究满足了人们在日常生活中享受各种便利的同时隐私得到保护的需求。文章考虑的是两个参与者隐私保护集合交集计算的情形,首先将集合表示成多项式,把求解两个集合的交集问题转化为求解两个多项式的最大公因式问题;在此基础上,根据多项式的数学性质和Pailliar同态加密算法提出一种保护隐私的两方集合交集计算协议,并给出协议的正确性和安全性分析;最后通过与相关文献的比较分析,得出文章协议的计算复杂度和通信复杂度较低的结论,且能够很好地保护参与方集合的元素个数。

关键词: 安全多方计算, 隐私保护, 集合交集, Pailliar同态加密算法

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

中图分类号:

TP309

唐春明, 林旭慧. 隐私保护集合交集计算协议[J]. 信息网络安全, 2020, 20(1): 9-15.

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

图/表 2

参考文献 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

隐私保护集合交集计算协议

Protocol of Privacy-preserving Set Intersection Computation

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 16

相关文章 15

编辑推荐

Metrics

本文评价

[1]	汪金苗, 谢永恒, 王国威, 李易庭. 基于属性基加密的区块链隐私保护与访问控制方法[J]. 信息网络安全, 2020, 20(9): 47-51.
[2]	汪金苗, 王国威, 王梅, 朱瑞瑾. 面向雾计算的隐私保护与访问控制方法[J]. 信息网络安全, 2019, 19(9): 41-45.
[3]	郝文江, 林云. 互联网企业社会责任现状与启示研究[J]. 信息网络安全, 2019, 19(9): 130-133.
[4]	周权, 许舒美, 杨宁滨. 一种基于ABGS的智能电网隐私保护方案[J]. 信息网络安全, 2019, 19(7): 25-30.
[5]	李怡霖, 闫峥, 谢皓萌. 车载自组织网络的隐私保护综述[J]. 信息网络安全, 2019, 19(4): 63-72.
[6]	傅彦铭, 李振铎. 基于拉普拉斯机制的差分隐私保护k-means++聚类算法研究[J]. 信息网络安全, 2019, 19(2): 43-52.
[7]	赵志岩, 吴剑, 康凯. 一种兼顾业务数据安全的隐私保护世系发布方法[J]. 信息网络安全, 2019, 19(12): 29-37.
[8]	胡荣磊, 何艳琼, 曾萍, 范晓红. 一种大数据环境下医疗隐私保护方案设计与实现[J]. 信息网络安全, 2018, 18(9): 48-54.
[9]	李佩丽, 徐海霞, 马添军, 穆永恒. 区块链技术在网络互助中的应用及用户隐私保护[J]. 信息网络安全, 2018, 18(9): 60-65.
[10]	马蓉, 陈秀华, 刘慧, 熊金波. 移动群智感知中用户隐私度量与隐私保护研究[J]. 信息网络安全, 2018, 18(8): 64-72.
[11]	赖成喆, 王文娟. 面向车队的安全且具备隐私保护的移动性管理框架[J]. 信息网络安全, 2018, 18(7): 36-46.
[12]	王乐, 杨哲荣, 刘容京, 王祥. 基于属性加密算法的可穿戴设备系统隐私保护方法研究[J]. 信息网络安全, 2018, 18(6): 77-84.
[13]	张磊, 王斌, 于莉莉. 基于马尔可夫预测的连续查询隐私保护方法[J]. 信息网络安全, 2018, 18(5): 12-12.
[14]	张磊, 王斌, 于莉莉. 基于Hash函数的属性泛化隐私保护方案[J]. 信息网络安全, 2018, 18(3): 14-25.
[15]	李梁, 张应辉, 邓恺鑫, 张甜甜. 5G智能电网中具有隐私保护的电力注入系统[J]. 信息网络安全, 2018, 18(12): 87-92.