Fair multi-party private set intersection protocol based on cloud server

doi:10.11772/j.issn.1001-9081.2022081229

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (9): 2806-2811.DOI: 10.11772/j.issn.1001-9081.2022081229

• Cyber security • Previous Articles Next Articles

Fair multi-party private set intersection protocol based on cloud server

Jing ZHANG, He TIAN, Kun XIONG, Yongli TANG(), Li YANG

School of Software，Henan Polytechnic University，Jiaozuo Henan 454000，China

Received:2022-08-29 Revised:2023-02-01 Accepted:2023-02-08 Online:2023-02-28 Published:2023-09-10
Contact: Yongli TANG
About author:ZHANG Jing， born in 1978， Ph. D.， associate professor. Her research interests include cryptography and information security， secure multi-party computation.
TIAN He， born in 1997， M. S. candidate. His research interests include cryptography and information security， privacy set intersection computation.
XIONG Kun， born in 1999， M. S. candidate. His research interests include cryptography and information security， secure multi-party computation.
YANG Li， born in 1998， M. S. candidate. Her research interests include cryptography and information security， privacy set intersection computation.
Supported by:
Henan Polytechnic University of Technology Doctoral Fund(B2021-41);Research Project of Henan Key Laboratory of Network Cryptography Technology(LNCT2022-A11)

基于云服务器的公平多方隐私集合交集协议

张静, 田贺, 熊坤, 汤永利(), 杨丽

河南理工大学软件学院，河南焦作 454000

通讯作者: 汤永利
作者简介:张静（1978—），女，河南焦作人，副教授，博士，CCF会员，主要研究方向：密码学与信息安全、安全多方计算
田贺（1997—），男，河南商丘人，硕士研究生，主要研究方向：密码学与信息安全、隐私集合交集计算
熊坤（1999—），男，重庆人，硕士研究生，主要研究方向：密码学与信息安全、安全多方计算
杨丽（1998—），女，河南商丘人，硕士研究生，主要研究方向：密码学与信息安全、隐私集合交集计算。
基金资助:
河南理工大学博士基金资助项目(B2021-41);河南省网络密码技术重点实验室研究课题(LNCT2022-A11)

Abstract

Abstract:

Private Set Intersection （PSI） is an important solution for privacy information sharing. A fair multi-party PSI protocol based on cloud server was proposed for the unfairness caused by the existing protocols in which the parties involved do not have simultaneous access to the calculation results. Firstly， the storage of a sub-share of the private information in Garbled Bloom Filter （GBF） was accomplished by using hash mapping. Secondly， in order to avoid the leakage of the index value of each party’s set element during the interaction， combined with Oblivious Transfer （OT） technique， the share replacement of the stored information was realized. Finally， the bit-by-bit calculation was performed by the cloud server， and the results were returned to each party at the same time to ensure the fairness of each party’s access to the results. The correctness and security analysis of the protocol shows that the proposed protocol can achieve the fairness of the parties in obtaining the intersection results， and can resist the collusion of parties with the cloud server. The performance analysis shows that both of the computational complexity and the communication complexity of the proposed protocol are independent of the total number of elements contained in the set of participants. Under the same conditions， compared with Multi-party PSI protocol （MPSI）， practical multiparty maliciously-secure PSI protocol （PSImple） and Private Intersection Sum algorithm （PI-Sum）， the proposed protocol has less storage overhead， communication overhead and running time.

Key words: Private Set Intersection (PSI), Garbled Bloom Filter (GBF), secure multi-party computation, fair computation, Oblivious Transfer (OT)

摘要：

隐私集合交集（PSI）是解决隐私信息共享的重要办法。针对现有的协议中参与方不能同时获取计算结果而导致的不公平性问题，提出一种基于云服务器的公平多方PSI协议。首先，利用哈希映射完成隐私信息的子份额在混淆布隆过滤器（GBF）中的存储；其次，为避免交互过程中各参与方集合元素索引值的泄露，协议结合不经意传输（OT）技术完成存储信息的份额置换；最后，通过云服务器进行逐位计算，并将结果同时返回各参与方，保证各参与方获取结果的公平性。协议的正确性和安全性分析表明，所提协议能够实现参与方获得交集结果的公平性，而且协议能够抵抗参与方与云服务器进行的合谋。性能分析表明，所提协议的计算复杂度和通信复杂度与参与方集合包含的元素总数无关；与多方隐私集合交集协议（MPSI）、实用多方恶意安全私有集合交集PSImple和隐私集合交集求和协议（PI-Sum）相比，在同等条件下，所提协议的存储开销、通信开销和运行时间更少。

关键词: 隐私集合交集, 混淆布隆过滤器, 安全多方计算, 公平计算, 不经意传输

CLC Number:

TP309.7

Jing ZHANG, He TIAN, Kun XIONG, Yongli TANG, Li YANG. Fair multi-party private set intersection protocol based on cloud server[J]. Journal of Computer Applications, 2023, 43(9): 2806-2811.

张静, 田贺, 熊坤, 汤永利, 杨丽. 基于云服务器的公平多方隐私集合交集协议[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2806-2811.

Figures/Tables 8

Fig. 1 Inserting elements into GBF

Tab. 1 Description of parameters and their meanings

参数	含义
$λ$	安全参数，字符串的长度
$k$	哈希函数 $H$ 的个数
$H = {h 1, h 2, ⋯, h k}$	哈希函数
$m$	GBF的存储范围
$X i$	参与方 $P i$ 持有的集合
$G B F X i$	由集合 $X i$ 生成的GBF
$i d$	GBF的索引值
$A$	敌手
$ω$	所有集合元素的总个数
$k ⁃ o u t ⁃ o f ⁃ m$ OT	发送方发送 $m$ 个消息，接收方从 $m$ 个消息中随机挑选 $k$ 个消息

Tab. 1 Description of parameters and their meanings

参数	含义
$λ$	安全参数，字符串的长度
$k$	哈希函数 $H$ 的个数
$H = {h 1, h 2, ⋯, h k}$	哈希函数
$m$	GBF的存储范围
$X i$	参与方 $P i$ 持有的集合
$G B F X i$	由集合 $X i$ 生成的GBF
$i d$	GBF的索引值
$A$	敌手
$ω$	所有集合元素的总个数
$k ⁃ o u t ⁃ o f ⁃ m$ OT	发送方发送 $m$ 个消息，接收方从 $m$ 个消息中随机挑选 $k$ 个消息

Fig. 2 System model

Tab. 2 PSI performance analysis of different schemes

协议	计算复杂度	通信复杂度	公平性
MPSI	$O (d ω λ + ω λ k)$	$O (d ω λ + ω λ k)$	否
PSImple	$O (d ω k l o g (d k))$	$O (d ω k l o g (d k))$	否
PI-Sum	$O (d ω λ + ω λ)$	$O (d ω λ + ω λ)$	否
$Π P S I$	$O (d λ m)$	$O (d λ m)$	是

Tab. 2 PSI performance analysis of different schemes

协议	计算复杂度	通信复杂度	公平性
MPSI	$O (d ω λ + ω λ k)$	$O (d ω λ + ω λ k)$	否
PSImple	$O (d ω k l o g (d k))$	$O (d ω k l o g (d k))$	否
PI-Sum	$O (d ω λ + ω λ)$	$O (d ω λ + ω λ)$	否
$Π P S I$	$O (d λ m)$	$O (d λ m)$	是

Fig. 3 Relationship between total set size and storage time

Fig. 4 Relationship between total set size and communication overhead

Fig. 5 Relationship between total set size and running time

Fig. 6 Relationship between number of parties and running time

References 17

1	申立艳，陈小军，时金桥，等. 隐私保护集合交集计算技术研究综述［J］. 计算机研究与发展， 2017， 54（10）：2153-2169. 10.7544/issn1000-1239.2017.20170461
	SHEN L Y， CHEN X J， SHI J Q， et al. Survey on privation set intersection technology［J］. Journal of Computer Research and Development，2017， 54（10）：2153-2169. 10.7544/issn1000-1239.2017.20170461
2	魏立斐，刘纪海，张蕾，等. 面向隐私保护的集合交集计算综述［J］. 计算机研究与发展， 2022， 59（8）：1782-1799. 10.7544/issn1000-1239.20210685
	WEI L F， LIU J H， ZHANG L， et al. Survey of privacy preserving oriented set intersection computation［J］. Journal of Computer Research and Development 2022， 59（8）：1782-1799. 10.7544/issn1000-1239.20210685
3	LV S Y， YE J H， YIN S J， et al. Unbalanced private set intersection cardinality protocol with low communication cost［J］. Future Generation Computer Systems， 2020， 102： 1054-1061. 10.1016/j.future.2019.09.022
4	LI M， YU S C， CAO N， et al. Privacy-preserving distributed profile matching in proximity based mobile social networks［J］. IEEE Transactions on Wireless Communications， 2013， 12（5）： 2024-2033. 10.1109/twc.2013.032513.120149
5	DEMMLER D， RINDAL P， ROSULEK M， et al. PIR-PSI： scaling private contact discovery［J］. Proceedings on Privacy Enhancing Technologies， 2018， 2018（4）： 159-178. 10.1515/popets-2018-0037
6	魏立斐，王勤，张蕾，等. 半可信云服务器辅助的高效隐私交集计算协议［J］. 软件学报， 2023， 34（2）：932-944.
	WEI L F， WANG Q， ZHANG L， et al. Efficient private set intersection protocols with semi-trusted cloud server aided［J］. Journal of Software， 2023， 34（2）：932-944.
7	SHEN L Y， CHEN X J， WANG D K， et al. Efficient and private set intersection of human genomes［C］// Proceedings of the 2018 IEEE International Conference on Bioinformatics and Biomedicine. Piscataway： IEEE， 2018： 761-764. 10.1109/bibm.2018.8621291
8	INBAR R， OMRI E， PINKAS B. Efficient scalable multiparty private set-intersection via garbled bloom filters［C］// Proceedings of the 2018 International Conference on Security and Cryptography for Networks， LNCS 11035. Cham： Springer， 2018： 235-252.
9	KAVOUSI A， MOHAJERI J， SALMASIZADEH M. Efficient scalable multi-party private set intersection using oblivious PRF［C］// Proceedings of the 2021 International Workshop on Security and Trust Management， LNCS 13075. Cham： Springer， 2021： 81-99.
10	BEN-EFRAIM A， NISSENBAUM O， OMRI E， et al. PSImple： practical multiparty maliciously-secure private set intersection［C］// Proceedings of the 2022 ACM Asia Conference on Computer and Communications Security. New York： ACM， 2022： 1098-1112. 10.1145/3488932.3523254
11	DEBNATH S K， SAKURAI K， DEY K， et al. Secure outsourced private set intersection with linear complexity［C］// Proceedings of the 2021 IEEE Conference on Dependable and Secure Computing. Piscataway： IEEE， 2021： 1-8. 10.1109/dsc49826.2021.9346230
12	KANO H， HAKUTA K. Efficiency improvement techniques for private intersection-sum protocol using Bloom filter［J］. SN Applied Sciences， 2022， 4（2）： No.37. 10.1007/s42452-021-04910-z
13	DEBNATH S K， DUTTA R. Towards fair mutual private set intersection with linear complexity［J］. Security and Communication Networks， 2016， 9（11）： 1589-1612. 10.1002/sec.1450
14	DEBNATH S K， DUTTA R. New realizations of efficient and secure private set intersection protocols preserving fairness［C］// Proceedings of the 2016 International Conference on Information Security and Cryptology， LNCS 10157. Cham： Springer， 2017： 254-284.
15	SHAMIR A. How to share a secret［J］. Communications of the ACM， 1979， 22（11）：612-613. 10.1145/359168.359176
16	DONG C Y， CHEN L Q， WEN Z K. When private set intersection meets big data： an efficient and scalable protocol［C］// Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2013： 789-800. 10.1145/2508859.2516701
17	WANG D， WANG P. Two birds with one stone： two-factor authentication with security beyond conventional bound［J］. IEEE Transactions on Dependable and Secure Computing， 2018， 15（4）： 708-722.

[1]	ZHANG Lihua, WANG Xinyi, HU Fangzhou, HUANG Yang, BAI Jiayi. Data sharing model of smart grid based on double consortium blockchains [J]. Journal of Computer Applications, 2021, 41(4): 963-969.
[2]	ZHANG En, LI Huimin, CHANG Jian. Verifiable k-means clustering scheme with privacy-preserving [J]. Journal of Computer Applications, 2021, 41(2): 413-421.
[3]	WANG Yunye, CHENG Yage, JIA Zhijuan, FU Junjun, YANG Yanyan, HE Yuchu, MA Wei. Auditable signature scheme for blockchain based on secure multi-party [J]. Journal of Computer Applications, 2020, 40(9): 2639-2645.
[4]	MA Minyao, LIU Zhuo, XU Yi, WU Lian. Private-preserving determination problem of integer-interval positional relationship [J]. Journal of Computer Applications, 2020, 40(9): 2657-2664.
[5]	MA Minyao, WU Lian, LIU Zhuo, XU Yi. Privacy-preserving determination of integer point-interval relationship [J]. Journal of Computer Applications, 2020, 40(7): 1983-1988.
[6]	MA Minyao, XU Yi, LIU Zhuo. Privacy preserving Hamming distance computing problem of DNA sequences [J]. Journal of Computer Applications, 2019, 39(9): 2636-2640.
[7]	ZHANG En, JIN Ganggang. Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter [J]. Journal of Computer Applications, 2018, 38(8): 2256-2260.
[8]	LUO Xiaoshuang, YANG Xiaoyuan, WANG Xu'an. A private set intersection protocol against malicious attack [J]. Journal of Computer Applications, 2017, 37(6): 1593-1598.
[9]	CUI Weirong, DU Chenglie. Fast proximity testing method with privacy preserving in mobile social network [J]. Journal of Computer Applications, 2017, 37(6): 1657-1662.
[10]	LI Zhenlin, ZHANG Wei, DAI Xiaoming. Predicate encryption scheme supporting secure multi-party homomorphic multiplicative computation [J]. Journal of Computer Applications, 2017, 37(4): 999-1003.
[11]	ZHANG En, LIU Yapeng. Cloud outsourcing private set intersection protocol based on garbled Bloom filter [J]. Journal of Computer Applications, 2016, 36(10): 2723-2727.
[12]	. Protocol for privacy-preserving set intersection [J]. Journal of Computer Applications, 2010, 30(2): 506-509.
[13]	. A safe mental poker protocol with two parts under hostile model [J]. Journal of Computer Applications, 2009, 29(07): 1836-1838.
[14]	. A secure twoparty bargaining protocolbased on additive homomorphic public key cryptosystem [J]. Journal of Computer Applications, 2006, 26(11): 2576-2577.

Fair multi-party private set intersection protocol based on cloud server

基于云服务器的公平多方隐私集合交集协议

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 17

Related Articles 14

Recommended Articles

Metrics