A Secure and Scalable Variant-Threshold Multiparty Private Set Intersection Protocol

doi:10.3969/j.issn.1671-1122.2026.04.003

Abstract

Abstract:

The ability of multi-party private intersection (MPSI) protocols is to securely find the intersection of multi-party sets and output it without disclosing any other information. However, there are some special and useful scenarios that cannot be solved directly using traditional MPSI protocols. One of such scenarios is to compute the set of elements that appear in some but not all sets (at least k times) for only a third party. However, the previous method(Quorum PSI) can only addresse the problem of getting special intersections of known elements. The over-threshold PSI can address the issue, but needs to perform times, which is inefficient when the number of participants is large. This paper proposed a secure and scalable variant-threshold multiparty private set intersection protocol. It only executes n − k + 1 times, which is more efficient in cases with a high threshold k.

Key words: private set intersection, private set membership test, private information retrieval, equal test

CLC Number:

TP309

ZHENG Dong, LIU Yanrong, QIN Baodong. A Secure and Scalable Variant-Threshold Multiparty Private Set Intersection Protocol[J]. Netinfo Security, 2026, 26(4): 542-551.

Figures/Tables 6

References 39

[1]	HAZAY C, NISSIM K. Efficient Set Operations in the Presence of Malicious Adversaries[C]// Springer. Public Key Cryptography-PKC 2010. Heidelberg:Springer, 2010: 312-331.
[2]	DE C E, KIM J, TSUDIK G. Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model[C]// Springer. Cryptology-ASIACRYPT 2010. Heidelberg:Springer, 2010: 213-231.
[3]	CHASE M, MIAO P. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF[C]// Springer. Cryptology-CRYPTO 2020. Heidelberg:Springer, 2020: 34-63.
[4]	DONG C, CHEN L, WEN Z. 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.
[5]	ORRU M, ORSINI E, SCHOLL P. Actively Secure 1-out-of-n OT Extension With Application to Private Set Intersection[C]// Springer. Topics in Cryptology-CT-RSA 2017. Heidelberg:Springer, 2017: 381-396.
[6]	RINDAL P, ROSULEK M. Malicious-Secure Private Set Intersection via Dual Execution[C]// ACM. The 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 1229-1242.
[7]	PINKAS B, SCHNEIDER T, ZOHNER M. Scalable Private Set Intersection Based on OT Extension[J]. ACM Transactions on Privacy and Security, 2018, 21(2): 1-35.
[8]	DING Jiang, ZHANG Guoyan, WEI Zizhong, et al. Research on Private Set Intersection for Multi-Source Heterogeneous Data Fusion[J]. Netinfo Security, 2023, 23(8): 86-98.
	丁江, 张国艳, 魏子重, 等. 面向多源异构数据融合的隐私集合求交研究[J]. 信息网络安全, 2023, 23(8): 86-98.
[9]	KOLESNIKOV V, MATANIA N, PINKAS B, et al. Practical Multiparty 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.
[10]	GAO Hongfeng, HUANG Hao, TIAN Youliang. Secure Byzantine Resilient Federated Learning Based on Multi-Party Computation[J]. Journal on Communications, 2025, 46(2): 108-122.
	高鸿峰, 黄浩, 田有亮. 基于多方计算的安全拜占庭弹性联邦学习[J]. 通信学报, 2025, 46(2):108-122.
[11]	XU Jian, XIAO Yongcai, LIN Zejian, et al. Privacy Protection Anomaly Detection in Smart Grids Based on Homomorphic Encryption[J]. Computer Technology and Development, 2025, 35(8):93-100.
	徐健, 肖勇才, 等. 基于同态加密的智能电网隐私保护异常检测技术[J]. 计算机技术与发展, 2025, 35(8):93-100.
[12]	FREEDMAN M J, NISSIM K, PINKAS B. Efficient Private Matching and Set Intersection[C]// Springer. Cryptology-EUROCRYPT 2004. Heidelberg:Springer, 2004: 1-19.
[13]	HAZAY C, VENKITASUBRAMANIAM M. Scalable Multiparty Private Set Intersection[C]// ACM. The 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 175-203.
[14]	KOLESNIKOV V, MATANIA N, PINKAS B, et al. Practical Multiparty 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.
[15]	GHOSH S, SIMKIN M. Threshold Private Set Intersection with Better Communication Complexity[C]// Springer. Public-Key Cryptography-PKC 2023. Heidelberg:Springer, 2023: 251-272.
[16]	WEI Lifei, LIU Jihai, ZHANG Lei, et al. A Dual-Cloud-Assisted Threshold-Based Multi-Party Private Set Intersection Protocol[J]. Journal of Software, 2023, 34(11): 5442-5456.
	魏立斐, 刘纪海, 张蕾, 等. 双云辅助的超阈值多方隐私集合交集计算协议[J]. 软件学报, 2023, 34(11): 5442-5456.
[17]	KISSNER L, SONG D. Privacy-Preserving Set Operations[C]// Springer. Annual International Cryptology Conference. Heidelberg: Springer, 2005: 241-257.
[18]	HAZAY C, VENKITASUBRAMANIAM M. Scalable Multi-Party Private Set-Intersection[C]// Springer. International Workshop on Public Key Cryptography. Heidelberg: Springer, 2017: 175-203.
[19]	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.
[20]	KAVOUSI A, MOHAJERI J, SALMASIZADEH M. Efficient Scalable Multi-Party Private Set Intersection Using Oblivious PRF[C]// Springer.Security and Trust Management. Heidelberg: Springer, 2021: 81-99.
[21]	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.
[22]	MOHANTY T, SRIVASTAVA V, DEBNATH S K, et al. Quantum Secure Threshold Private Set Intersection Protocol for IoT-Enabled Privacy Preserving Ride-Sharing Application[J]. IEEE Internet of Things Journal, 2023, 10(7): 12784-12798.
[23]	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.
[24]	BRANCO P, DOTTLING N, PU S. Multiparty Cardinality Testing for Threshold Private Intersection[C]// Springer. Public-Key Cryptography-PKC 2021. Heidelberg:Springer, 2021: 32-60.
[25]	GHOSH S, SIMKIN M. The Communication Complexity of Threshold Private Set Intersection[C]// Springer. Annual International Cryptology Conference. Heidelberg: Springer, 2019: 3-29.
[26]	CHANDRAN N, DASGUPTA N, GUPTA D, et al. Efficient Linear Multi-Party PSI and Extensions to Circuit/Quorum PSI[C]// ACM.The 2021 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2021: 1182-1204.
[27]	KISSNER L, SONG D. Private and Threshold Set Intersection[D]. Pittsburgh: Carnegie Mellon University, 2004.
[28]	CHAKRABORTI A, FANTI G, REITER M K. Distance-Aware Private Set Intersection[C]// USENIX. The 32nd USENIX Security Symposium (USENIX Security 23). Berkely: USENIX, 2023: 319-336.
[29]	RATHEE D, RATHEE M, KUMAR N, et al. CryptFlow2: Practical 2-Party Secure Inference[C]// ACM. CCS’20: 2020 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2020: 325-342.
[30]	DAMGARD I, NIELSEN J B. Scalable and Unconditionally Secure Multiparty Computation[C]// Springer. Cryptology-CRYPTO 2007. Heidelberg:Springer, 2007: 572-590.
[31]	LINDELL Y, NOF A. A Framework for Constructing Fast MPC Over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority[C]// ACM. The 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 259-276.
[32]	GOLDREICH O, GOLDWASSER S, MICALI S. How to Construct Random Functions (Extended Abstract)[C]// IEEE. The 25th Annual Symposium on Foundations of Computer Science. New York: IEEE, 1984: 464-479.
[33]	CHOR B, KUSHILEVITZ E, GOLDREICH O, et al. Private Information Retrieval[J]. Journal of the ACM, 1998, 45(6): 965-981.
[34]	GENTRY C. Fully Homomorphic Encryption Using Ideal Lattices[C]// ACM. The Forty-First Annual ACM Symposium on Theory of Computing. New York: ACM, 2009: 169-178.
[35]	CHEON J H, KIM A, KIM M, et al. Homomorphic Encryption for Arithmetic of Approximate Numbers[C]// Springer. Cryptology-ASIACRYPT 2017. Heidelberg:Springer, 2017: 409-437.
[36]	YI X, KAOSAR M G, PAULET R, et al. Single-Database Private Information Retrieval from Fully Homomorphic Encryption[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 25(5): 1125-1134.
[37]	JARECKI S, LIU X. Fast Secure Computation of Set Intersection[C]// Springer. Security and Cryptography for Networks. Heidelberg: Springer, 2010: 418-435.
[38]	ANGEL S, CHEN H, LAINE K, et al. PIR with Compressed Queries and Amortized Query Processing[C]// IEEE. 2018 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2018: 962-979.
[39]	MAHDAVI R A, HUMPHRIES T, KACSMAR B, et al. Practical Over-Threshold Multi-Party Private Set Intersection[C]// ACM. The 36th Annual Computer Security Applications Conference. New York: ACM, 2020: 772-783.

符号	说明
X_i	参与方集合
$n$	参与方数量
$u$	集合大小
$\kappa $	安全参数
$\lambda $	计算安全参数
$k$	阈值
$\left[ n \right]~$	从1到$~n~$的整数集合
$\left[ x \right]$	$x$的秘密共享
$x$	$x$的加法秘密共享
$m$	$n$−k+1 个参与方
$Tabl{{e}_{\left[ i \right]~}}\left[ j \right]$	哈希表的第$i$个参与方的第j个箱子
$s~\leftarrow ~S$	s是 S里随机选取的元素

协议	通信复杂度	计算复杂度
Kissner Song^[27]协议	$O~\left(u~\cdot~n~\right)$	$O~\left( {{u}^{2}}\cdot ~{{n}^{2}} \right)$
t-PSI^[39]协议	$O~\left( u~\cdot ~n~\cdot ~t \right)$	$O~\left( u\cdot ~n~\cdot ~t \right)$
本文协议	$O~\left( mu\left( n~-~1 \right) \right)$	$O~\left( mu~\left( n-1 \right)+n\cdot m\text{lg}n \right)$