{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:30:32Z","timestamp":1777390232732,"version":"3.51.4"},"reference-count":44,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2024,12,22]],"date-time":"2024-12-22T00:00:00Z","timestamp":1734825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["62472252"],"award-info":[{"award-number":["62472252"]}]},{"name":"National Natural Science Foundation of China","award":["62172258"],"award-info":[{"award-number":["62172258"]}]},{"name":"National Natural Science Foundation of China","award":["tsqn202211280"],"award-info":[{"award-number":["tsqn202211280"]}]},{"name":"National Natural Science Foundation of China","award":["ZR2024QF131"],"award-info":[{"award-number":["ZR2024QF131"]}]},{"name":"National Natural Science Foundation of China","award":["ZR2023LZH014"],"award-info":[{"award-number":["ZR2023LZH014"]}]},{"name":"National Natural Science Foundation of China","award":["ZR2022ZD01"],"award-info":[{"award-number":["ZR2022ZD01"]}]},{"name":"National Natural Science Foundation of China","award":["SYS202201"],"award-info":[{"award-number":["SYS202201"]}]},{"name":"National Natural Science Foundation of China","award":["QCLZD202302"],"award-info":[{"award-number":["QCLZD202302"]}]},{"name":"TaiShan Scholars Program","award":["62472252"],"award-info":[{"award-number":["62472252"]}]},{"name":"TaiShan Scholars Program","award":["62172258"],"award-info":[{"award-number":["62172258"]}]},{"name":"TaiShan Scholars Program","award":["tsqn202211280"],"award-info":[{"award-number":["tsqn202211280"]}]},{"name":"TaiShan Scholars Program","award":["ZR2024QF131"],"award-info":[{"award-number":["ZR2024QF131"]}]},{"name":"TaiShan Scholars Program","award":["ZR2023LZH014"],"award-info":[{"award-number":["ZR2023LZH014"]}]},{"name":"TaiShan Scholars Program","award":["ZR2022ZD01"],"award-info":[{"award-number":["ZR2022ZD01"]}]},{"name":"TaiShan Scholars Program","award":["SYS202201"],"award-info":[{"award-number":["SYS202201"]}]},{"name":"TaiShan Scholars Program","award":["QCLZD202302"],"award-info":[{"award-number":["QCLZD202302"]}]},{"name":"Shandong Provincial Natural Science Foundation","award":["62472252"],"award-info":[{"award-number":["62472252"]}]},{"name":"Shandong Provincial Natural Science Foundation","award":["62172258"],"award-info":[{"award-number":["62172258"]}]},{"name":"Shandong Provincial Natural Science Foundation","award":["tsqn202211280"],"award-info":[{"award-number":["tsqn202211280"]}]},{"name":"Shandong Provincial Natural Science Foundation","award":["ZR2024QF131"],"award-info":[{"award-number":["ZR2024QF131"]}]},{"name":"Shandong Provincial Natural Science Foundation","award":["ZR2023LZH014"],"award-info":[{"award-number":["ZR2023LZH014"]}]},{"name":"Shandong Provincial Natural Science Foundation","award":["ZR2022ZD01"],"award-info":[{"award-number":["ZR2022ZD01"]}]},{"name":"Shandong Provincial Natural Science Foundation","award":["SYS202201"],"award-info":[{"award-number":["SYS202201"]}]},{"name":"Shandong Provincial Natural Science Foundation","award":["QCLZD202302"],"award-info":[{"award-number":["QCLZD202302"]}]},{"name":"Department of Science and Technology of Shandong Province","award":["62472252"],"award-info":[{"award-number":["62472252"]}]},{"name":"Department of Science and Technology of Shandong Province","award":["62172258"],"award-info":[{"award-number":["62172258"]}]},{"name":"Department of Science and Technology of Shandong Province","award":["tsqn202211280"],"award-info":[{"award-number":["tsqn202211280"]}]},{"name":"Department of Science and Technology of Shandong Province","award":["ZR2024QF131"],"award-info":[{"award-number":["ZR2024QF131"]}]},{"name":"Department of Science and Technology of Shandong Province","award":["ZR2023LZH014"],"award-info":[{"award-number":["ZR2023LZH014"]}]},{"name":"Department of Science and Technology of Shandong Province","award":["ZR2022ZD01"],"award-info":[{"award-number":["ZR2022ZD01"]}]},{"name":"Department of Science and Technology of Shandong Province","award":["SYS202201"],"award-info":[{"award-number":["SYS202201"]}]},{"name":"Department of Science and Technology of Shandong Province","award":["QCLZD202302"],"award-info":[{"award-number":["QCLZD202302"]}]},{"name":"Quan Cheng Laboratory","award":["62472252"],"award-info":[{"award-number":["62472252"]}]},{"name":"Quan Cheng Laboratory","award":["62172258"],"award-info":[{"award-number":["62172258"]}]},{"name":"Quan Cheng Laboratory","award":["tsqn202211280"],"award-info":[{"award-number":["tsqn202211280"]}]},{"name":"Quan Cheng Laboratory","award":["ZR2024QF131"],"award-info":[{"award-number":["ZR2024QF131"]}]},{"name":"Quan Cheng Laboratory","award":["ZR2023LZH014"],"award-info":[{"award-number":["ZR2023LZH014"]}]},{"name":"Quan Cheng Laboratory","award":["ZR2022ZD01"],"award-info":[{"award-number":["ZR2022ZD01"]}]},{"name":"Quan Cheng Laboratory","award":["SYS202201"],"award-info":[{"award-number":["SYS202201"]}]},{"name":"Quan Cheng Laboratory","award":["QCLZD202302"],"award-info":[{"award-number":["QCLZD202302"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Private Set Intersection (PSI) is a significant application of interest within Secure Multi-party Computation (MPC), even though we are still in the early stages of deploying MPC solutions to real-world problems. Threshold PSI (tPSI), a variant of PSI, allows two parties to determine the intersection of their respective sets only if the cardinality of the intersection is at least (or less than) a specified threshold t. In this paper, we propose a generic construction for two-party tPSI that extensively utilizes Oblivious Transfer (OT). Our approach is based on lightweight primitives and avoids costly public-key systems such as homomorphic encryption. We start by introducing the secret-sharing private membership test PMTss that is based on the secret-sharing private equality test PEQTss. The PMTss enables tPSI to be scaled for a wide range of practical applications, particularly benefiting parties with limited computational resources. Consequently, two distinct two-party tPSI protocols can be efficiently implemented: over-threshold PSI (t\u2264PSI) and under-threshold PSI t&gt;PSI. In addition, we propose a lightweight two-party tPSI with limited leakage and a generic precomputing OT suitable for phased implementation. Experimental performance demonstrates that our protocols are highly efficient and computationally friendly, thus paving the way for broader deployment of tPSI solutions.<\/jats:p>","DOI":"10.3390\/cryptography8040058","type":"journal-article","created":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T10:06:52Z","timestamp":1734948412000},"page":"58","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Two-Party Threshold Private Set Intersection Protocols from Lightweight Cryptographic Primitives"],"prefix":"10.3390","volume":"8","author":[{"given":"Shengnan","family":"Zhao","sequence":"first","affiliation":[{"name":"Quan Cheng Laboratory, Jinan 250103, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuan","family":"Zhao","sequence":"additional","affiliation":[{"name":"Quan Cheng Laboratory, Jinan 250103, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9660-3444","authenticated-orcid":false,"given":"Yuchen","family":"Huang","sequence":"additional","affiliation":[{"name":"College of Computer and Information Engineering, Henan Normal University, Xinxiang 453007, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiangfu","family":"Song","sequence":"additional","affiliation":[{"name":"College of Computing and Data Science, Nanyang Technological University, Singapore 639798, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiuliang","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Software, Shandong University, Jinan 250101, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,12,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Yao, A.C. (1982, January 3\u20135). Protocols for secure computations. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), Chicago, IL, USA.","DOI":"10.1109\/SFCS.1982.38"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/j.ins.2018.10.024","article-title":"Secure multi-party computation: Theory, practice and applications","volume":"476","author":"Zhao","year":"2019","journal-title":"Inf. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Kolesnikov, V., Kumaresan, R., Rosulek, M., and Trieu, N. (2016, January 24\u201328). Efficient batched oblivious PRF with applications to private set intersection. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.","DOI":"10.1145\/2976749.2978381"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Pinkas, B., Schneider, T., Tkachenko, O., and Yanai, A. (2019). Efficient circuit-based psi with linear communication. Advances in Cryptology\u2013EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany 19\u201323 May 2019, Springer.","DOI":"10.1007\/978-3-030-17659-4_5"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Pinkas, B., Rosulek, M., Trieu, N., and Yanai, A. (2019, January 18\u201322). SpOT-light: Lightweight private set intersection from sparse OT extension. Proceedings of the Advances in Cryptology\u2013CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA. Proceedings, Part III 39.","DOI":"10.1007\/978-3-030-26954-8_13"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Kolesnikov, V., Rosulek, M., Trieu, N., and Wang, X. (2019). Scalable private set union from symmetric-key techniques. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Springer.","DOI":"10.1007\/978-3-030-34621-8_23"},{"key":"ref_7","unstructured":"Zhang, C., Chen, Y., Liu, W., Zhang, M., and Lin, D. (2023, January 9\u201311). Linear private set union from {Multi-Query} reverse private membership test. Proceedings of the 32nd USENIX Security Symposium (USENIX Security 23), Anaheim, CA, USA."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Le, P.H., Ranellucci, S., and Gordon, S.D. (2019, January 11\u201315). Two-party private set intersection with an untrusted third party. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, London, UK.","DOI":"10.1145\/3319535.3345661"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., and Trieu, N. (November, January 30). Practical multi-party private set intersection from symmetric-key techniques. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA.","DOI":"10.1145\/3133956.3134065"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"103764","DOI":"10.1016\/j.csi.2023.103764","article-title":"Efficient multi-party private set intersection protocols for large participants and small sets","volume":"87","author":"Wei","year":"2024","journal-title":"Comput. Stand. Interfaces"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Chongchitmate, W., Ishai, Y., Lu, S., and Ostrovsky, R. (2022, January 7\u201311). Psi from ring-ole. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, CA, USA.","DOI":"10.1145\/3548606.3559378"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"120995","DOI":"10.1016\/j.ins.2024.120995","article-title":"New Approach for Efficient Malicious Multiparty Private Set Intersection","volume":"678","author":"Lv","year":"2024","journal-title":"Inf. Sci."},{"key":"ref_13","first-page":"738","article-title":"Private intersection-sum protocol with applications to attributing aggregate ad conversions","volume":"2017","author":"Ion","year":"2017","journal-title":"Cryptology ePrint Archive"},{"key":"ref_14","unstructured":"Duong, T., Phan, D.H., and Trieu, N. (2020). Catalic: Delegated PSI cardinality with applications to contact tracing. Proceedings of the Advances in Cryptology\u2013ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, Republic of Korea, 7\u201311 December 2020, Springer. Proceedings, Part III 26."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Kong, X., Chen, L., Zhu, Y., and Mu, Y. (2024). Efficient Public-key Searchable Encryption Scheme from PSI with Scalable Proxy Servers. IEEE Trans. Serv. Comput., 1\u201314.","DOI":"10.1109\/TSC.2024.3489432"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"9670","DOI":"10.1109\/TIFS.2024.3477924","article-title":"OpenVFL: A Vertical Federated Learning Framework with Stronger Privacy-Preserving","volume":"19","author":"Yang","year":"2024","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1109\/TSC.2024.3356667","article-title":"DMPSI: Efficient Scalable Delegated Multiparty PSI and PSI-CA with Oblivious PRF","volume":"17","author":"Yang","year":"2024","journal-title":"IEEE Trans. Serv. Comput."},{"key":"ref_18","unstructured":"Bradley, T., Faber, S., and Tsudik, G. Bounded size-hiding private set intersection. Proceedings of the International Conference on Security and Cryptography for Networks."},{"key":"ref_19","first-page":"149","article-title":"Are you the one to share? secret transfer with access structure","volume":"2017","author":"Zhao","year":"2017","journal-title":"Proc. Priv. Enhanc. Technol."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Zhao, Y., and Chow, S.S. (2018, January 15\u201319). Can you find the one for me?. Proceedings of the 2018 Workshop on Privacy in the Electronic Society, Toronto, ON, Canada.","DOI":"10.1145\/3267323.3268965"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Ghosh, S., and Simkin, M. (2019, January 18\u201322). The communication complexity of threshold private set intersection. Proceedings of the Annual International Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-030-26951-7_1"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Branco, P., D\u00f6ttling, N., and Pu, S. (2021, January 10\u201313). Multiparty cardinality testing for threshold private intersection. Proceedings of the IACR International Conference on Public-Key Cryptography, Vitual Event.","DOI":"10.1007\/978-3-030-75248-4_2"},{"key":"ref_23","first-page":"600","article-title":"Multi-Party Threshold Private Set Intersection with Sublinear Communication","volume":"2020","author":"Badrinarayanan","year":"2020","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_24","unstructured":"Ghosh, S., and Simkin, M. Threshold private set intersection with better communication complexity. Proceedings of the IACR International Conference on Public-Key Cryptography."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Liu, F.H., Zhang, E., and Qin, L. (2023, January 26\u201330). Efficient Multiparty Probabilistic Threshold Private Set Intersection. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, Copenhagen, Denmark.","DOI":"10.1145\/3576915.3623158"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"103781","DOI":"10.1016\/j.csi.2023.103781","article-title":"Over-threshold multi-party private set operation protocols for lightweight clients","volume":"88","author":"Ma","year":"2024","journal-title":"Comput. Stand. Interfaces"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1761","DOI":"10.1109\/JIOT.2023.3291132","article-title":"Quantum secure threshold private set intersection protocol for IoT-Enabled privacy preserving ride-sharing application","volume":"11","author":"Mohanty","year":"2023","journal-title":"IEEE Internet Things J."},{"key":"ref_28","unstructured":"Pinkas, B., Schneider, T., and Zohner, M. (2014, January 20\u201322). Faster private set intersection based on {OT} extension. Proceedings of the 23rd {USENIX} Security Symposium ({USENIX} Security 14), San Diego, CA, USA."},{"key":"ref_29","unstructured":"Chase, M., and Miao, P. (2020). Private set intersection in the internet setting from lightweight oblivious PRF. Advances in Cryptology\u2013CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, 17\u201321 August 2020, Springer. Proceedings, Part III 40."},{"key":"ref_30","first-page":"2221","article-title":"Privacy-Preserving Statistics Protocol for Set-Based Computation (in Chinese)","volume":"57","author":"Song","year":"2020","journal-title":"J. Comput. Res. Dev."},{"key":"ref_31","unstructured":"Ciampi, M., and Orlandi, C. Combining private set-intersection with secure two-party computation. Proceedings of the International Conference on Security and Cryptography for Networks."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Karako\u00e7, F., and K\u00fcp\u00e7\u00fc, A. (2020). Linear Complexity Private Set Intersection for Secure Two-Party Protocols. Cryptology ePrint Archive, Report 2020\/864. International Conference on Cryptology and Network Security, Springer.","DOI":"10.1007\/978-3-030-65411-5_20"},{"key":"ref_33","unstructured":"Miao, P., Patel, S., Raykova, M., Seth, K., and Yung, M. Two-sided malicious security for private intersection-sum with cardinality. Proceedings of the Annual International Cryptology Conference."},{"key":"ref_34","unstructured":"Kolesnikov, V., and Kumaresan, R. Improved OT extension for transferring short secrets. Proceedings of the Annual Cryptology Conference."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Orr\u00f9, M., Orsini, E., and Scholl, P. (2017, January 14\u201317). Actively secure 1-out-of-N OT extension with application to private set intersection. Proceedings of the Topics in Cryptology\u2013CT-RSA 2017: The Cryptographers\u2019 Track at the RSA Conference 2017, San Francisco, CA, USA. Proceedings.","DOI":"10.1007\/978-3-319-52153-4_22"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Zhao, S., Ma, M., Song, X., Jiang, H., Yan, Y., and Xu, Q. Lightweight threshold private set intersection via oblivious transfer. Proceedings of the Wireless Algorithms, Systems, and Applications: 16th International Conference, WASA 2021, Nanjing, China, 25\u201327 June 2021, Proceedings, Part III 16.","DOI":"10.1007\/978-3-030-86137-7_12"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"6184","DOI":"10.1109\/TIFS.2024.3402355","article-title":"Enabling Threshold Functionality for Private Set Intersection Protocols in Cloud Computing","volume":"19","author":"Hu","year":"2024","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Asharov, G., Lindell, Y., Schneider, T., and Zohner, M. (2013, January 4\u20138). More efficient oblivious transfer and extensions for faster secure computation. Proceedings of the 2013 ACM SIGSAC conference on Computer & Communications Security, Berlin, Germnay.","DOI":"10.1145\/2508859.2516738"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Yang, K., Weng, C., Lan, X., Zhang, J., and Wang, X. (2020, January 9\u201313). Ferret: Fast Extension for coRRElated oT with small communication. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event.","DOI":"10.1145\/3372297.3417276"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","article-title":"Cuckoo hashing","volume":"51","author":"Pagh","year":"2004","journal-title":"J. Algorithms"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/359168.359176","article-title":"How to share a secret","volume":"22","author":"Shamir","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_42","unstructured":"Goldreich, O. (2009). Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press."},{"key":"ref_43","unstructured":"Couteau, G. New protocols for secure equality test and comparison. Proceedings of the International Conference on Applied Cryptography and Network Security."},{"key":"ref_44","unstructured":"Beaver, D. Precomputing oblivious transfer. Proceedings of the Annual International Cryptology Conference."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/8\/4\/58\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:57:52Z","timestamp":1760115472000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/8\/4\/58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,22]]},"references-count":44,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["cryptography8040058"],"URL":"https:\/\/doi.org\/10.3390\/cryptography8040058","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,22]]}}}