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

doi:10.11772/j.issn.1001-9081.2022081229

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (9): 2806-2811.DOI: 10.11772/j.issn.1001-9081.2022081229

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

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

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

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

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)

摘要/Abstract

摘要：

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

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

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)

中图分类号:

TP309.7

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

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.

图/表 8

图1 向GBF中插入元素

Fig. 1 Inserting elements into GBF

表1 参数及其含义说明

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$ 个消息

表1 参数及其含义说明

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$ 个消息

图2 系统模型

Fig. 2 System model

表2 不同方案的PSI性能分析

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)$	是

表2 不同方案的PSI性能分析

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)$	是

图3 总集合大小与存储时间的关系

Fig. 3 Relationship between total set size and storage time

图4 总集合大小与通信开销的关系

Fig. 4 Relationship between total set size and communication overhead

图5 总集合大小与协议运行时间的关系

Fig. 5 Relationship between total set size and running time

图6 参与方个数与协议运行时间的关系

Fig. 6 Relationship between number of parties and running time

参考文献 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]	王腾, 霍峥, 黄亚鑫, 范艺琳. 联邦学习中的隐私保护技术研究综述[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 437-449.
[2]	蒋楚钰, 方李西, 章宁, 朱建明. 基于公证人组的跨链交互安全模型[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3438-3443.
[3]	张利华, 王欣怡, 胡方舟, 黄阳, 白甲义. 基于双联盟链的智能电网数据共享模型[J]. 计算机应用, 2021, 41(4): 963-969.
[4]	张恩, 李会敏, 常键. 可验证的隐私保护k-means聚类方案[J]. 计算机应用, 2021, 41(2): 413-421.
[5]	王韫烨, 程亚歌, 贾志娟, 付俊俊, 杨艳艳, 何宇矗, 马威. 基于安全多方的区块链可审计签名方案[J]. 计算机应用, 2020, 40(9): 2639-2645.
[6]	马敏耀, 刘卓, 徐艺, 吴恋. 隐私保护整数区间位置关系判定问题[J]. 计算机应用, 2020, 40(9): 2657-2664.
[7]	马敏耀, 吴恋, 刘卓, 徐艺. 隐私保护整数点和区间关系判定问题[J]. 计算机应用, 2020, 40(7): 1983-1988.
[8]	马敏耀, 徐艺, 刘卓. 隐私保护DNA序列汉明距离计算问题[J]. 计算机应用, 2019, 39(9): 2636-2640.
[9]	罗小双, 杨晓元, 王绪安. 一类可抵抗恶意攻击的隐私集合交集协议[J]. 计算机应用, 2017, 37(6): 1593-1598.
[10]	李镇林, 张薇, 戴晓明. 支持安全多方同态乘积计算的谓词加密方案[J]. 计算机应用, 2017, 37(4): 999-1003.
[11]	罗小双, 杨晓元, 王绪安. 适用于社交网络的隐私保护兴趣度匹配方案[J]. 计算机应用, 2016, 36(12): 3322-3327.
[12]	张恩, 刘亚鹏. 基于混淆布鲁姆过滤器的云外包隐私集合比较协议[J]. 计算机应用, 2016, 36(10): 2723-2727.
[13]	豆永丽王海春康剑. 集合成员判定问题的安全多方计算解决方案[J]. 计算机应用, 2013, 33(12): 3527-3530.
[14]	孙彦飞仲红燕飞飞黄宏升. 保护私有信息的集合交集协议[J]. 计算机应用, 2010, 30(2): 506-509.
[15]	郑天翔. 基于三次同余方程的增强的Rabin密码体制[J]. 计算机应用, 2009, 29(07): 1803-1805.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 17

相关文章 15

编辑推荐

Metrics