{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T07:06:42Z","timestamp":1763968002693,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T00:00:00Z","timestamp":1254355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2009,10]]},"abstract":"<jats:p>\n            Many applications require performing set operations without publishing individual datesets. In this article, we address this problem for five fundamental set operations including set intersection, cardinality of set intersection, element reduction, overthreshold set-union, and subset relation. Our protocols are obtained in the universally composable security framework, in the assumption of the probabilistic polynomial time bounded adversary, which actively controls a fixed set of\n            <jats:italic>t<\/jats:italic>\n            parties and the assumption of an authenticated broadcast channel. Our constructions utilize building blocks of nonmalleable NonInteractive Zero-Knowledge (NIZK) arguments, which are based on a (\n            <jats:italic>t<\/jats:italic>\n            + 1,\n            <jats:italic>N<\/jats:italic>\n            )-threshold version (\n            <jats:italic>N<\/jats:italic>\n            is the number of parties in the protocol) of the boneh-goh-nissim (BGN) cryptosystem whose underlying group supports bilinear maps, in the assumption that the public key and shares of the secret key have been generated by a trusted dealer. The previous studies were all based on the stand-alone model with the same assumptions on the adversary, broadcast channel, and key generation. For the first four operations, we propose protocols that improve the previously known results by an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>N<\/jats:italic>\n            ) factor in the computation and communication complexities. For the subset relation, our protocol is the first one secure against the active adversary. Our constructions of NIZK have independent interest in that, though also mentioned as building blocks, the previous work did not illustrate how to construct them. We construct these NIZK with an additional nonmalleable property, the same complexity as claimed in the previous work, and also an improvement on the communication complexity.\n          <\/jats:p>","DOI":"10.1145\/1609956.1609965","type":"journal-article","created":{"date-parts":[[2009,11,4]],"date-time":"2009-11-04T18:28:31Z","timestamp":1257359311000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":49,"title":["Efficient and secure protocols for privacy-preserving set operations"],"prefix":"10.1145","volume":"13","author":[{"given":"Yingpeng","family":"Sang","sequence":"first","affiliation":[{"name":"The University of Adelaide, SA, Australia"}]},{"given":"Hong","family":"Shen","sequence":"additional","affiliation":[{"name":"The University of Adelaide, SA, Australia"}]}],"member":"320","published-online":{"date-parts":[[2009,11,6]]},"reference":[{"volume-title":"Proceedings of the 4th Theory of Cryptography Conference (TCC'07)","author":"Adida B.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of Advances in Cryptology (EUROCRYPT'04)","author":"Aggarwal G.","key":"e_1_2_1_2_1"},{"volume-title":"Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology (CRYPTO'02)","author":"Barreto P.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398521"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_18"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875553"},{"volume-title":"Proceedings of Advances in Cryptology (EUROCRYPT'01)","author":"Cramer R.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277779"},{"volume-title":"Proceedings of Advances in Cryptology (ERUROCRYPT'04)","author":"Freedman M.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72738-5_16"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-001-0015-6"},{"volume-title":"Foundations of Cryptography","author":"Goldreich O.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28420"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_21"},{"volume-title":"Proceedings of Advances in Cryptology (EUROCRYPT'08)","author":"Groth J.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11957454_16"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_15"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Kissner L. and Song D. 2006. Privacy-preserving set operations. Tech. rep. CMU-CS-05-113 Carnegie Mellon University.  Kissner L. and Song D. 2006. Privacy-preserving set operations. Tech. rep. CMU-CS-05-113 Carnegie Mellon University.","DOI":"10.21236\/ADA457144"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72738-5_15"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-002-0143-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.259647"},{"key":"e_1_2_1_23_1","unstructured":"Menezes A. Oorschot P. and Vanstone S. 1996. Handbook of Applied Cryptography. CRC Press Boca Raton FL.   Menezes A. Oorschot P. and Vanstone S. 1996. Handbook of Applied Cryptography. CRC Press Boca Raton FL."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-004-0315-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11745853_4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46416-6_47"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796535"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11935308_15"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDCAT.2007.73"},{"volume-title":"Proceedings of the 31st Australasian Computer Science Conference (ACSC'08)","author":"Sang Y.","key":"e_1_2_1_30_1"},{"volume-title":"Archive: Report 2006\/418","year":"2006","author":"Seo J.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775142"},{"volume-title":"Proceedings of the Australian Conference on Information Security and Privacy (ACISP'01)","author":"Yamamura A.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1609956.1609965","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1609956.1609965","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:14Z","timestamp":1750278374000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1609956.1609965"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1145\/1609956.1609965"],"URL":"https:\/\/doi.org\/10.1145\/1609956.1609965","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2009,10]]},"assertion":[{"value":"2007-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}