适用于轻量级客户端的多方隐私集合求交协议

doi:10.3969/j.issn.1671-1122.2026.02.006

摘要/Abstract

摘要：

随着隐私保护需求的增长，多方隐私集合求交（MP-PSI）协议作为一种关键的隐私计算技术，在多个领域受到广泛关注。然而，在计算资源受限的环境中，现有的MP-PSI协议往往面临客户端计算负担较重的问题，限制了其在实际应用中的可行性。为解决这一问题，文章提出一种基于布隆过滤器和同态加密的轻量级客户端MP-PSI协议。该协议通过引入不经意可编程伪随机函数，将大部分计算任务从客户端转移到服务器，从而显著降低了客户端的计算开销并充分利用了服务器的计算资源。实验结果表明，该协议在客户端计算时间和服务器计算效率方面均优于现有方案。协议在半诚实模型中可抵抗至多n-1个参与方合谋攻击，可确保诚实参与方的隐私。该协议为资源受限环境下的隐私保护问题提供了新的解决方案。

关键词: 多方隐私集合求交, 轻量级客户端, 布隆过滤器, 不经意可编程伪随机函数

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

中图分类号:

TP309

杨乐, 何慧阳, 尤玮婧, 张佰韬, 林璟锵. 适用于轻量级客户端的多方隐私集合求交协议[J]. 信息网络安全, 2026, 26(2): 251-262.

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.

图/表 7

图1

图2

表1

表2

表3

图3

表4

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