{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T11:04:25Z","timestamp":1777806265188,"version":"3.51.4"},"reference-count":44,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p>Private set intersection cardinality (PSI-CA) and private intersection-sum with cardinality (PSI-CA-sum) are two primitives that enable data owners to learn the intersection cardinality of their data sets, with the difference that PSI-CA-sum additionally outputs the sum of the associated integer values of all the data that belongs to the intersection (i.e., intersection-sum). However, to the best of our knowledge, all existing multi-party PSI-CA (MPSI-CA) protocols are either limited by high computational cost or face security challenges under arbitrary collusion. As for multi-party PSI-CA-sum (MPSI-CA-sum), there is even no formalization for this notion at present, not to mention secure constructions for it.<\/jats:p>\n                  <jats:p>In this paper, we first present an efficient MPSI-CA protocol with two non-colluding parties. This protocol significantly decreases the number of parties involved in expensive interactive procedures, leading to a significant enhancement in runtime efficiency. Our numeric results demonstrate that the running time of this protocol is merely one-quarter of the time required by our proposed MPSI-CA protocol that is secure against arbitrary collusion. Therefore, in scenarios where performance is a priority, this protocol stands out as an excellent choice.<\/jats:p>\n                  <jats:p>\n                    Second, we successfully construct the first MPSI-CA protocol that achieves simultaneous practicality and security against arbitrary collusion. Additionally, we also conduct implementation to verify its practicality (while the previous results under arbitrary collusion only present theoretical analysis of performance, lacking real implementation). Numeric results show that by shifting the costly operations to an offline phase, the online computation can be completed in just 12.805 seconds, even in the dishonest majority setting, where 15 parties each hold a set of size\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:msup>\n                          <mml:mn>2<\/mml:mn>\n                          <mml:mn>16<\/mml:mn>\n                        <\/mml:msup>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>\n                  <jats:p>Third, we formalize the concept of MPSI-CA-sum and present the first realization that ensures simultaneous practicality and security against arbitrary collusion. The computational complexity of this protocol is roughly twice that of our MPSI-CA protocol.<\/jats:p>\n                  <jats:p>Besides the main results, we introduce the concepts and efficient constructions of two novel building blocks: multi-party secret-shared shuffle and multi-party oblivious zero-sum check, which may be of independent interest.<\/jats:p>","DOI":"10.3233\/jcs-230091","type":"journal-article","created":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T11:48:47Z","timestamp":1712317727000},"page":"3-36","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Practical multi-party private set intersection cardinality and intersection-sum protocols under arbitrary collusion"],"prefix":"10.1177","volume":"33","author":[{"given":"You","family":"Chen","sequence":"first","affiliation":[{"name":"School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ning","family":"Ding","sequence":"additional","affiliation":[{"name":"School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai, China"},{"name":"Shanghai Jiao Tong University (Wuxi) Blockchain Advanced Research Center, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dawu","family":"Gu","sequence":"additional","affiliation":[{"name":"School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai, China"},{"name":"Shanghai Jiao Tong University (Wuxi) Blockchain Advanced Research Center, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Bian","sequence":"additional","affiliation":[{"name":"Fudata Technology, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2025,3,28]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"382","volume-title":"IFIP Annual Conference on Data and Applications Security and Privacy","author":"Ashok V.G.","year":"2014","unstructured":"Ashok V.G., Mukkamala R., A scalable and efficient privacy preserving global itemset support approximation using bloom filters, in: IFIP Annual Conference on Data and Applications Security and Privacy, Springer, 2014, pp.\u00a0382\u2013389."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2021.3118879"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484591"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Chandran N. Gupta D. Shah A. Circuit-psi with linear complexity via relaxed batch opprf Cryptology ePrint Archive 2021.","DOI":"10.2478\/popets-2022-0018"},{"key":"e_1_3_2_6_2","first-page":"342","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security","author":"Chase M.","year":"2020","unstructured":"Chase M., Ghosh E., Poburinnaya O., Secret-shared shuffle, in: International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2020, pp.\u00a0342\u2013372."},{"key":"e_1_3_2_7_2","first-page":"505","volume-title":"International Conference on Information Security and Cryptology","author":"Debnath S.K.","year":"2016","unstructured":"Debnath S.K., Dutta R., Provably secure fair mutual private set intersection cardinality utilizing bloom filter, in: International Conference on Information Security and Cryptology, Springer, 2016, pp.\u00a0505\u2013525."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.3934\/amc.2020071"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Demmler D. Schneider T. Zohner M. Aby-a framework for efficient mixed-protocol secure two-party computation in: NDSS 2015.","DOI":"10.14722\/ndss.2015.23113"},{"key":"e_1_3_2_10_2","unstructured":"Dong C. Chen L. Wen Z. When private set intersection meets big data: An efficient and scalable protocol."},{"key":"e_1_3_2_11_2","first-page":"870","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security","author":"Duong T.","year":"2020","unstructured":"Duong T., Phan D.H., Trieu N., Catalic: Delegated psi cardinality with applications to contact tracing, in: International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2020, pp.\u00a0870\u2013899."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19962-7_24"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1561\/3300000019"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-014-9190-0"},{"key":"e_1_3_2_15_2","first-page":"1","volume-title":"International Conference on the Theory and Applications of Cryptographic Techniques","author":"Freedman M.J.","year":"2004","unstructured":"Freedman M.J., Nissim K., Pinkas B., Efficient private matching and set intersection, in: International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2004, pp.\u00a01\u201319."},{"key":"e_1_3_2_16_2","first-page":"591","volume-title":"IACR International Conference on Public-Key Cryptography","author":"Garimella G.","year":"2021","unstructured":"Garimella G., Mohassel P., Rosulek M., Sadeghian S., Singh J., Private set operations from oblivious switching, in: IACR International Conference on Public-Key Cryptography, Springer, 2021, pp.\u00a0591\u2013617."},{"key":"e_1_3_2_17_2","first-page":"395","volume-title":"Annual International Cryptology Conference","author":"Garimella G.","year":"2021","unstructured":"Garimella G., Pinkas B., Rosulek M., Trieu N., Yanai A., Oblivious key-value stores and amplification for private set intersection, in: Annual International Cryptology Conference, Springer, 2021, pp.\u00a0395\u2013425."},{"key":"e_1_3_2_18_2","first-page":"154","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Ghosh S.","year":"2019","unstructured":"Ghosh S., Nilges T., An algebraic approach to maliciously secure private set intersection, in: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2019, pp.\u00a0154\u2013185."},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","unstructured":"Gordon S.D. Hazay C. Le P.H. Fully secure psi via mpc-in-the-head in: Proceedings on Privacy Enhancing Technologies 2022.","DOI":"10.56553\/popets-2022-0073"},{"key":"e_1_3_2_20_2","first-page":"175","volume-title":"IACR International Workshop on Public Key Cryptography","author":"Hazay C.","year":"2017","unstructured":"Hazay C., Venkitasubramaniam M., Scalable multi-party private set-intersection, in: IACR International Workshop on Public Key Cryptography, Springer, 2017, pp.\u00a0175\u2013203."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98113-0_13"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP48549.2020.00031"},{"key":"e_1_3_2_23_2","unstructured":"Ion M. Kreuter B. Nergiz E. Patel S. Saxena S. Seth K. Shanahan D. Yung M. Private intersection-sum protocol with applications to attributing aggregate ad conversions Cryptology ePrint Archive 2017."},{"key":"e_1_3_2_24_2","first-page":"145","volume-title":"Annual International Cryptology Conference","author":"Ishai Y.","year":"2003","unstructured":"Ishai Y., Kilian J., Nissim K., Petrank E., Extending oblivious transfers efficiently, in: Annual International Cryptology Conference, Springer, 2003, pp.\u00a0145\u2013161."},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"Kissner L. Song D. Private and threshold set-intersection Tech. rep. Carnegie-Mellon Univ Pittsburgh Pa Dept Of Computer Science 2004.","DOI":"10.21236\/ADA461119"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978381"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134065"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2019.09.022"},{"key":"e_1_3_2_29_2","first-page":"3","volume-title":"Annual International Cryptology Conference","author":"Miao P.","year":"2020","unstructured":"Miao P., Patel S., Raykova M., Seth K., Yung M., Two-sided malicious security for private intersection-sum with cardinality, in: Annual International Cryptology Conference, Springer, 2020, pp.\u00a03\u201333."},{"key":"e_1_3_2_30_2","first-page":"557","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Mohassel P.","year":"2013","unstructured":"Mohassel P., Sadeghian S., How to hide circuits in mpc an efficient framework for private function evaluation, in: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2013, pp.\u00a0557\u2013574."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_3_2_32_2","first-page":"448","volume-title":"SODA","author":"Naor M.","year":"2001","unstructured":"Naor M., Pinkas B., Efficient oblivious transfer protocols, in: SODA, Vol.\u00a01, 2001, pp.\u00a0448\u2013457."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484772"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1002\/int.22420"},{"key":"e_1_3_2_35_2","series-title":"Proceedings","first-page":"28","volume-title":"Algorithms\u00a0\u2013 ESA 2001: 9th Annual European Symposium \u00c5rhus","author":"Pagh R.","year":"2001","unstructured":"Pagh R., Rodler F.F., Cuckoo hashing, in: Algorithms\u00a0\u2013 ESA 2001: 9th Annual European Symposium \u00c5rhus, Denmark, August 28\u201331, 2001, Proceedings, Springer, 2001, pp.\u00a028\u201331."},{"key":"e_1_3_2_36_2","first-page":"739","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Pinkas B.","year":"2020","unstructured":"Pinkas B., Rosulek M., Trieu N., Yanai A., Psi from paxos: Fast, malicious private set intersection, in: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2020, pp.\u00a0739\u2013767."},{"key":"e_1_3_2_37_2","series-title":"Proceedings, Part III","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1007\/978-3-030-17659-4_5","volume-title":"Advances in Cryptology\u2013EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Pinkas B.","year":"2019","unstructured":"Pinkas B., Schneider T., Tkachenko O., Yanai A., Efficient circuit-based psi with linear communication, in: Advances in Cryptology\u2013EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19\u201323, 2019, Proceedings, Part III, Vol.\u00a038, Springer, 2019, pp.\u00a0122\u2013153."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78372-7_5"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3154794"},{"key":"e_1_3_2_40_2","unstructured":"Rabin M.O. How to exchange secrets with oblivious transfer Cryptology ePrint Archive 2005."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560658"},{"key":"e_1_3_2_42_2","first-page":"901","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Rindal P.","year":"2021","unstructured":"Rindal P., Schoppmann P., Vole-psi: Fast oprf and circuit-psi from vector-ole, in: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2021, pp.\u00a0901\u2013930."},{"key":"e_1_3_2_43_2","unstructured":"Trieu N. Yanai A. Gao J. Multiparty private set intersection cardinality and its applications Cryptology ePrint Archive 2022."},{"key":"e_1_3_2_44_2","unstructured":"Vos J. Conti M. Erkin Z. Fast multi-party private set operations in the star topology from secure ands and ors Cryptology ePrint Archive 2022."},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","unstructured":"Vos J. Conti M. Erkin Z. Sok: Collusion-resistant multi-party private set intersections in the semi-honest model Cryptology ePrint Archive 2023.","DOI":"10.1109\/SP54263.2024.00079"}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-230091","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-230091","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-230091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:45:51Z","timestamp":1777495551000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-230091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.3233\/JCS-230091"],"URL":"https:\/\/doi.org\/10.3233\/jcs-230091","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"value":"0926-227X","type":"print"},{"value":"1875-8924","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1]]}}}