A Multiparty Private Set Intersection Protocol for Lightweight Clients

doi:10.3969/j.issn.1671-1122.2026.02.006

Abstract

Abstract:

With the increasing demand for privacy protection, Multiparty Private Set Intersection (MP-PSI) has emerged as a crucial privacy-preserving computation technique and has gained widespread attention across various domains. However, in resource-constrained environments, existing MP-PSI protocols often impose a significant computational burden on clients, limiting their practical applicability. To address this issue, this paper proposed an MP-PSI protocol based on Bloom filter and homomorphic encryption for lightweight clients. By incorporating oblivious programmable pseudorandom function, the proposed protocol effectively offloaded most computational tasks from the client to the server, thereby significantly reducing client-side computational overhead while fully utilizing server-side computational resources. Experimental results demonstrate that the proposed protocol outperforms existing approaches in terms of client-side computation time and server-side computational efficiency. Furthermore, in the semi-honest model, the protocol can resist collusion attacks from up to n-1 participants while ensuring the privacy of honest parties. This paper provides an innovative solution to privacy protection in resource-constrained environments.

Key words: multiparty private set intersection, lightweight clients, bloom filter, oblivious programmable pseudorandom function

CLC Number:

TP309

YANG Le, HE Huiyang, YOU Weijing, ZHANG Baitao, LIN Jingqiang. A Multiparty Private Set Intersection Protocol for Lightweight Clients[J]. Netinfo Security, 2026, 26(2): 251-262.

Figures/Tables 7

References 27

[1]	CHASE M, MIAO Peihan. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF[C]// IACR. Advances in Cryptology-CRYPTO 2020: The 40th Annual International Cryptology Conference. Heidelberg: Springer, 2020: 34-63.
[2]	PINKAS B, ROSULEK M, TRIEU N, et al. PSI from PaXoS:Fast, Malicious Private Set Intersection[C]// IACR. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2020: 739-767.
[3]	RINDAL P, SCHOPPMANN P. VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE[C]// IACR. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2021: 901-930.
[4]	ELKORDY A R, EZZELDIN Y H, AVESTIMEHR S. Federated K-Private Set Intersection[C]// ACM. The 31st ACM International Conference on Information & Knowledge Management. New York: ACM, 2022: 436-445.
[5]	LU Linpeng, DING Ning. Multi-Party Private Set Intersection in Vertical Federated Learning[C]// IEEE. 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications. New York: IEEE, 2020: 707-714.
[6]	GHOSH S, NILGES T. An Algebraic Approach to Maliciously Secure Private Set Intersection[C]// IACR. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2019: 154-185.
[7]	NGUYEN D T, TRIEU N. MPCCache: Privacy-Preserving Multi-Party Cooperative Cache Sharing at the Edge[C]// IFCA. International Conference on Financial Cryptography and Data Security. Heidelberg: Springer, 2022: 80-99.
[8]	MIYAJI A, NISHIDA S. A Scalable Multiparty Private Set Intersection[C]// Springer. International Conference on Network and System Security. Heidelberg: Springer, 2015: 376-385.
[9]	BAY A, ERKIN Z, HOEPMAN J H, et al. Practical Multi-Party Private Set Intersection Protocols[J]. IEEE Transactions on Information Forensics and Security, 2021, 17: 1-15. doi: 10.1109/TIFS.2021.3118879 URL
[10]	DAVIDSON A, CID C. An Efficient Toolkit for Computing Private Set Operations[C]// Springer. Information Security and Privacy:The 22nd Australasian Conference. Heidelberg: Springer, 2017: 261-278.
[11]	VOS J, CONTI M, ERKIN Z. Fast Multi-Party Private Set Operations in the Star Topology from Secure ANDs and ORs[EB/OL]. (2022-07-21)[2025-02-17]. https://eprint.iacr.org/2022/721.pdf.
[12]	RUAN Ou, AI Chaohao. An Efficient Multi-Party Private Set Intersection Protocols Based on Bloom Filter[C]// Karpagam College of Engineering. The Second International Conference on Algorithms, Microchips, and Network Applications. Bellingham: SPIE, 2023: 282-287.
[13]	RUAN Ou, YAN Changwang, ZHOU Jing, et al. A Practical Multiparty Private Set Intersection Protocol Based on Bloom Filters for Unbalanced Scenarios[EB/OL]. (2023-12-13)[2025-02-17]. https://www.mdpi.com/2076-3417/13/24/13215.
[14]	GAO Ying, LUO Yuanchao, WANG Longxin, et al. Efficient Scalable Multi-Party Private Set Intersection (-Variants) from Bicentric Zero-Sharing[C]// ACM. The 2024 on ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2024: 4137-4151.
[15]	KOLESNIKOV V, MATANIA N, PINKAS B, et al. Practical Multi-Party Private Set Intersection from Symmetric-Key Techniques[C]// ACM. The 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 1257-1272.
[16]	INBAR R, OMRI E, PINKAS B. Efficient Scalable Multiparty Private Set-Intersection via Garbled Bloom Filters[C]// IACR. International Conference on Security and Cryptography for Networks. Heidelberg: Springer, 2018: 235-252.
[17]	DONG Changyu, CHEN Liqun, WEN Zikai. When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol[C]// ACM.The 2013 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2013: 789-800.
[18]	NEVO O, TRIEU N, YANAI A. Simple, Fast Malicious Multiparty Private Set Intersection[C]// ACM. The 2021 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2021: 1151-1165.
[19]	WU Mingli, YUEN T H, CHAN K Y. O-Ring and K-Star: Efficient Multi-Party Private Set Intersection[C]// USENIX. The 33rd USENIX Security Symposium. Berkeley: USENIX, 2024: 6489-6506.
[20]	BLOOM B H. Space/Time Trade-Offs in Hash Coding with Allowable Errors[J]. Communications of the ACM, 1970, 13(7): 422-426. doi: 10.1145/362686.362692 URL
[21]	ELGAMAL T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[J]. IEEE Transactions on Information Theory, 1985, 31(4): 469-472. doi: 10.1109/TIT.1985.1057074 URL
[22]	KATZ J, LINDELL Y. Introduction to Modern Cryptography: Principles and Protocols[M]. New York: Chapman and Hall/CRC, 2007.
[23]	KOLESNIKOV V, KUMARESAN R, ROSULEK M, et al. Efficient Batched Oblivious PRF with Applications to Private Set Intersection[C]// ACM. The 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 818-829.
[24]	EVANS D, KOLESNIKOV V, ROSULEK M. A Pragmatic Introduction to Secure Multi-Party Computation[J]. Foundations and Trends in Privacy and Security, 2018, 2(2-3): 70-246. doi: 10.1561/SEC URL
[25]	CANETTI R. Security and Composition of Multiparty Cryptographic Protocols[J]. Journal of Cryptology, 2000, 13: 143-202. doi: 10.1007/s001459910006 URL
[26]	KOLESNIKOV V, KUMARESAN R. Improved OT Extension for Transferring Short Secrets[C]// IACR. Advances in Cryptology-CRYPTO 2013-The 33rd Annual Cryptology Conference. Heidelberg: Springer, 2013: 54-70.
[27]	ASHAROV G, LINDELL Y, SCHNEIDER T, et al. More Efficient Oblivious Transfer and Extensions for Faster Secure Computation[C]// ACM. The 2013 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2013: 535-548.

协议	客户端		所使用的加密算法	是否需要可信第三方
协议	加密次数	解密次数	所使用的加密算法	是否需要可信第三方
文献[8]	${{m}_{b}}$	${{m}_{b}}$	指数ElGamal	√
文献[9]	${{m}_{b}}$	$m$	Paillier	√
文献[11]	$mk$	$mk$	EC-ElGamal	?
文献[12]	${{m}_{b}}$	${{m}_{b}}$	ElGamal	?
文献[13]	${{m}_{b}}$	$m$	ElGamal	√
本文协议	$m$	$m$	ElGamal	?

协议		计算复杂度	通信复杂度
文献[15]		$O(nm\kappa )$	$O(nm\lambda )$
文献[16]		$O(nmk\lambda )$	$O(nmk\lambda )$
文献[19]	O-Ring	$O(nm\kappa )$	$O(nm(\lambda +\kappa +{{\log }_{2}}m))$
文献[19]	K-Star	$O(nm\kappa )$	$O(nm(\lambda +\kappa +{{\log }_{2}}m))$
本文协议		$O\text{(}m\kappa \text{)}$	$O\text{(max }\!\!\{\!\!\text{ }\lambda \text{,lo}{{\text{g}}_{\text{2}}}\|X\|\text{ }\!\!\}\!\!\text{ }m\text{)}$

协议		文献[9]		文献[13]		本文协议
参与方数量	集合大小	服务器（总）耗时/s	客户端耗时/s	服务器（总）耗时/s	客户端耗时/s	服务器（总）耗时/s	客户端耗时/s
5	${{2}^{4}}$	3.35	3.28	1.15	1.06	0.47	0.22
	${{2}^{6}}$	13.92	13.58	4.65	4.31	1.27	0.58
	${{2}^{8}}$	55.20	52.97	18.41	16.94	4.36	2.04
	${{2}^{10}}$	238.20	210.07	69.11	68.06	16.51	7.74
	${{2}^{12}}$	1325.87	836.37	276.40	271.23	65.55	30.83
	${{2}^{14}}$	—	—	1163.00	1085.16	262.35	123.93
10	${{2}^{4}}$	3.60	3.43	1.17	1.06	0.64	0.23
	${{2}^{6}}$	14.00	13.76	4.45	4.23	1.20	0.61
	${{2}^{8}}$	57.86	55.90	17.85	16.94	3.50	2.08
	${{2}^{10}}$	239.42	209.78	73.53	67.95	12.41	8.07
	${{2}^{12}}$	1467.29	873.28	295.74	281.40	49.19	32.24
	${{2}^{14}}$	—	—	1152.43	1095.19	193.50	125.67
15	${{2}^{4}}$	3.63	3.55	1.17	1.07	0.88	0.26
	${{2}^{6}}$	14.60	14.16	4.68	4.24	1.44	0.64
	${{2}^{8}}$	56.93	54.85	18.27	16.95	3.37	2.14
	${{2}^{10}}$	249.51	215.06	73.79	68.08	11.92	8.14
	${{2}^{12}}$	1493.46	845.68	294.58	273.12	45.43	32.37
	${{2}^{14}}$	—	—	1179.49	1167.14	180.97	128.99
20	${{2}^{4}}$	3.97	3.50	1.24	1.07	1.22	0.27
	${{2}^{6}}$	14.45	14.00	4.98	4.30	1.72	0.68
	${{2}^{8}}$	55.71	52.87	20.01	16.91	3.65	2.23
	${{2}^{10}}$	257.93	211.27	78.91	67.77	11.96	8.65
	${{2}^{12}}$	1617.95	867.34	314.43	292.74	45.91	34.18
	${{2}^{14}}$	—	—	1242.47	1083.16	178.01	133.56
30	${{2}^{4}}$	4.32	3.71	1.32	1.10	1.80	0.30
	${{2}^{6}}$	16.34	15.71	5.19	4.25	2.50	0.79
	${{2}^{8}}$	64.79	57.48	20.79	17.13	4.61	2.47
	${{2}^{10}}$	276.18	212.68	82.73	73.18	13.27	9.36
	${{2}^{12}}$	1690.65	886.12	333.15	273.47	48.54	35.70
	${{2}^{14}}$	—	—	1333.58	1083.74	183.57	139.49

协议		文献[9]协议		文献[13]协议		本文协议
参与方数量	集合大小	服务器通信开销/MB	客户端通信开销/MB	服务器通信开销/MB	客户端通信开销/MB	服务器通信开销/MB	客户端通信开销/MB
5	${{2}^{4}}$	0.06	0.13	0.02	0.12	0.69	0.46
	${{2}^{6}}$	0.25	0.51	0.06	0.47	2.71	1.86
	${{2}^{8}}$	1.00	2.06	0.25	1.86	10.09	5.99
	${{2}^{10}}$	4.01	8.23	1.00	7.44	40.33	23.98
	${{2}^{12}}$	16.03	32.91	4.00	29.76	161.27	95.92
	${{2}^{14}}$	—	—	16.00	119.02	642.49	381.08
10	${{2}^{4}}$	0.14	0.13	0.04	0.12	1.54	0.46
	${{2}^{6}}$	0.56	0.51	0.14	0.47	6.09	1.86
	${{2}^{8}}$	2.25	2.06	0.56	1.86	22.70	5.99
	${{2}^{10}}$	9.02	8.23	2.25	7.44	90.74	23.98
	${{2}^{12}}$	36.06	32.91	9.00	29.76	362.86	95.92
	${{2}^{14}}$	—	—	36.00	119.02	1445.60	381.08
15	${{2}^{4}}$	0.22	0.13	0.06	0.12	2.40	0.46
	${{2}^{6}}$	0.88	0.51	0.22	0.47	9.47	1.86
	${{2}^{8}}$	3.51	2.06	0.88	1.86	35.31	5.99
	${{2}^{10}}$	14.02	8.23	3.50	7.44	141.14	23.98
	${{2}^{12}}$	56.08	32.90	14.00	29.76	564.45	95.92
	${{2}^{14}}$	—	—	56.00	119.02	2248.72	381.08
20	${{2}^{4}}$	0.30	0.13	0.08	0.12	3.26	0.46
	${{2}^{6}}$	1.19	0.51	0.30	0.47	12.85	1.86
	${{2}^{8}}$	4.76	2.06	1.19	1.86	47.92	5.99
	${{2}^{10}}$	19.03	8.23	4.75	7.44	191.55	23.98
	${{2}^{12}}$	76.13	32.91	19.00	29.76	766.04	95.92
	${{2}^{14}}$	—	—	76.00	119.02	3051.83	381.08
30	${{2}^{4}}$	0.45	0.13	0.12	0.12	4.97	0.46
	${{2}^{6}}$	1.82	0.51	0.46	0.47	19.62	1.86
	${{2}^{8}}$	7.26	2.06	1.82	1.86	73.14	5.99
	${{2}^{10}}$	29.04	8.23	7.26	7.44	292.37	23.98
	${{2}^{12}}$	116.17	32.90	29.01	29.76	1169.22	95.92
	${{2}^{14}}$	—	—	116.01	119.02	4658.06	381.08