{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T21:17:02Z","timestamp":1768079822394,"version":"3.49.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T00:00:00Z","timestamp":1667001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T00:00:00Z","timestamp":1667001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Institute of Information & communications Technology Planning & Evaluation","award":["2021-0-00518"],"award-info":[{"award-number":["2021-0-00518"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Functional encryption (FE) is a new paradigm of public key encryption that can control the exposed information of plaintexts by supporting computation on encrypted data. In this paper, we propose efficient multi-client FE (MCFE) schemes that compute the set intersection of ciphertexts generated by two clients. First, we propose an MCFE scheme that calculates the set intersection cardinality (MCFE-SIC) and prove its static security under dynamic assumptions. Next, we extend our MCFE-SIC scheme to an MCFE scheme for set intersection (MCFE-SI) and prove its static security under dynamic assumptions. The decryption algorithm of our MCFE-SI scheme is more efficient than the existing MCFE-SI scheme because it requires fewer pairing operations to calculate the intersection of two clients. Finally, we propose a decentralized MCFE scheme for set intersection (DMCFE-SI) that decentralizes the generation of function keys. Our MCFE schemes can be effectively applied to a privacy-preserving contact tracing system to prevent the spread of recent infectious diseases.<\/jats:p>","DOI":"10.1007\/s10623-022-01139-8","type":"journal-article","created":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T17:03:11Z","timestamp":1667062991000},"page":"1053-1093","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Decentralized multi-client functional encryption for set intersection with improved efficiency"],"prefix":"10.1007","volume":"91","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1910-8890","authenticated-orcid":false,"given":"Kwangsu","family":"Lee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"key":"1139_CR1","unstructured":"Apple and google privacy-preserving contact tracing. https:\/\/covid19.apple.com\/contacttracing (2020)."},{"key":"1139_CR2","doi-asserted-by":"crossref","unstructured":"Abdalla M., Bourse F., Caro A.D., Pointcheval D.: Simple functional encryption schemes for inner products. In: Katz J. (ed.) Public-Key Cryptography - PKC 2015, LNCS, vol. 9020, pp. 733\u2013751. Springer, Heidelberg (2015).","DOI":"10.1007\/978-3-662-46447-2_33"},{"key":"1139_CR3","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/978-3-319-56620-7_21","volume-title":"Advances in Cryptology - EUROCRYPT 2017, LNCS","author":"M Abdalla","year":"2017","unstructured":"Abdalla M., Gay R., Raykova M., Wee H.: Multi-input inner-product functional encryption from pairings. In: Coron J., Nielsen J.B. (eds.) Advances in Cryptology - EUROCRYPT 2017, LNCS, vol. 10210, pp. 601\u2013626. Springer, Heidelberg (2017)."},{"key":"1139_CR4","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-319-96884-1_20","volume-title":"Advances in Cryptology - CRYPTO 2018, LNCS","author":"M Abdalla","year":"2018","unstructured":"Abdalla M., Catalano D., Fiore D., Gay R., Ursu B.: Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings. In: Shacham H., Boldyreva A. (eds.) Advances in Cryptology - CRYPTO 2018, LNCS, vol. 10991, pp. 597\u2013627. Springer, Heidelberg (2018)."},{"key":"1139_CR5","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1007\/978-3-030-34618-8_19","volume-title":"Advances in Cryptology - ASIACRYPT 2019, LNCS","author":"M Abdalla","year":"2019","unstructured":"Abdalla M., Benhamouda F., Gay R.: From single-input to multi-client inner-product functional encryption. In: Galbraith S.D., Moriai S. (eds.) Advances in Cryptology - ASIACRYPT 2019, LNCS, vol. 11923, pp. 552\u2013582. Springer, Heidelberg (2019)."},{"key":"1139_CR6","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-662-53015-3_12","volume-title":"Advances in Cryptology - CRYPTO 2016, LNCS","author":"S Agrawal","year":"2016","unstructured":"Agrawal S., Libert B., Stehl\u00e9 D.: Fully secure functional encryption for inner products, from standard assumptions. In: Robshaw M., Katz J. (eds.) Advances in Cryptology - CRYPTO 2016, LNCS, vol. 9816, pp. 333\u2013362. Springer, Heidelberg (2016)."},{"key":"1139_CR7","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-030-84259-8_8","volume-title":"Advances in Cryptology - CRYPTO 2021, LNCS","author":"S Agrawal","year":"2021","unstructured":"Agrawal S., Goyal R., Tomida J.: Multi-input quadratic functional encryption from pairings. In: Malkin T., Peikert C. (eds.) Advances in Cryptology - CRYPTO 2021, LNCS, vol. 12828, pp. 208\u2013238. Springer, Heidelberg (2021)."},{"issue":"2","key":"1139_CR8","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s13389-013-0057-3","volume":"3","author":"JA Akinyele","year":"2013","unstructured":"Akinyele J.A., Garman C., Miers I., Pagano M.W., Rushanan M., Green M., Rubin A.D.: Charm: A framework for rapidly prototyping cryptosystems. J. Cryptogr. Eng. 3(2), 111\u2013128 (2013).","journal-title":"J. Cryptogr. Eng."},{"key":"1139_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-319-63688-7_3","volume-title":"Advances in Cryptology - CRYPTO 2017, LNCS","author":"CEZ Baltico","year":"2017","unstructured":"Baltico C.E.Z., Catalano D., Fiore D., Gay R.: Practical functional encryption for quadratic functions with applications to predicate encryption. In: Katz J., Shacham H. (eds.) Advances in Cryptology - CRYPTO 2017, LNCS, vol. 10401, pp. 67\u201398. Springer, Heidelberg (2017)."},{"key":"1139_CR10","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1007\/978-3-662-48797-6_20","volume-title":"Advances in Cryptology - ASIACRYPT 2015, LNCS","author":"A Bishop","year":"2015","unstructured":"Bishop A., Jain A., Kowalczyk L.: Function-hiding inner product encryption. In: Iwata T., Cheon J.H. (eds.) Advances in Cryptology - ASIACRYPT 2015, LNCS, vol. 9452, pp. 470\u2013491. Springer, Heidelberg (2015)."},{"key":"1139_CR11","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/3-540-44647-8_13","volume-title":"Advances in Cryptology - CRYPTO 2001, LNCS","author":"D Boneh","year":"2001","unstructured":"Boneh D., Franklin M.K.: Identity-based encryption from the Weil pairing. In: Kilian J. (ed.) Advances in Cryptology - CRYPTO 2001, LNCS, vol. 2139, pp. 213\u2013229. Springer, Heidelberg (2001)."},{"key":"1139_CR12","first-page":"535","volume-title":"Theory of Cryptography - TCC 2007, LNCS","author":"D Boneh","year":"2007","unstructured":"Boneh D., Waters B.: Conjunctive, subset, and range queries on encrypted data. In: Vadhan S.P. (ed.) Theory of Cryptography - TCC 2007, LNCS, vol. 4392, pp. 535\u2013554. Springer, Heidelberg (2007)."},{"key":"1139_CR13","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/11426639_26","volume-title":"Advances in Cryptology - EUROCRYPT 2005, LNCS","author":"D Boneh","year":"2005","unstructured":"Boneh D., Boyen X., Goh E.J.: Hierarchical identity based encryption with constant size ciphertext. In: Cramer R. (ed.) Advances in Cryptology - EUROCRYPT 2005, LNCS, vol. 3494, pp. 440\u2013456. Springer, Heidelberg (2005)."},{"key":"1139_CR14","first-page":"253","volume-title":"Theory of Cryptography - TCC 2011, LNCS","author":"D Boneh","year":"2011","unstructured":"Boneh D., Sahai A., Waters B.: Functional encryption: Definitions and challenges. In: Ishai Y. (ed.) Theory of Cryptography - TCC 2011, LNCS, vol. 6597, pp. 253\u2013273. Springer, Heidelberg (2011)."},{"key":"1139_CR15","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/978-3-030-03329-3_24","volume-title":"Advances in Cryptology - ASIACRYPT 2018, LNCS","author":"J Chotard","year":"2018","unstructured":"Chotard J., Dufour S.E., Gay R., Phan D.H., Pointcheval D.: Decentralized multi-client functional encryption for inner product. In: Peyrin T., Galbraith S.D. (eds.) Advances in Cryptology - ASIACRYPT 2018, LNCS, vol. 11273, pp. 703\u2013732. Springer, Heidelberg (2018)."},{"key":"1139_CR16","doi-asserted-by":"publisher","first-page":"870","DOI":"10.1007\/978-3-030-64840-4_29","volume-title":"Advances in Cryptology - ASIACRYPT 2020, LNCS","author":"T Duong","year":"2020","unstructured":"Duong T., Phan D.H., Trieu N.: Catalic: Delegated PSI cardinality with applications to contact tracing. In: Moriai S., Wang H. (eds.) Advances in Cryptology - ASIACRYPT 2020, LNCS, vol. 12493, pp. 870\u2013899. Springer, Heidelberg (2020)."},{"key":"1139_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24676-3_1","volume-title":"Advances in Cryptology - EUROCRYPT 2004, LNCS","author":"MJ Freedman","year":"2004","unstructured":"Freedman M.J., Nissim K., Pinkas B.: Efficient private matching and set intersection. In: Cachin C., Camenisch J. (eds.) Advances in Cryptology - EUROCRYPT 2004, LNCS, vol. 3027, pp. 1\u201319. Springer, Heidelberg (2004)."},{"key":"1139_CR18","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-642-13190-5_3","volume-title":"Advances in Cryptology - EUROCRYPT 2010, LNCS","author":"DM Freeman","year":"2010","unstructured":"Freeman D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert H. (ed.) Advances in Cryptology - EUROCRYPT 2010, LNCS, vol. 6110, pp. 44\u201361. Springer, Heidelberg (2010)."},{"key":"1139_CR19","doi-asserted-by":"crossref","unstructured":"Garg S., Gentry C., Halevi S., Raykova M., Sahai A., Waters B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS 2013, pp. 40\u201349. IEEE Computer Society (2013).","DOI":"10.1109\/FOCS.2013.13"},{"key":"1139_CR20","doi-asserted-by":"crossref","unstructured":"Goldwasser S., Kalai Y.T., Popa R.A., Vaikuntanathan V., Zeldovich N.: Reusable garbled circuits and succinct functional encryption. In: Boneh D., Roughgarden T., Feigenbaum J. (eds.) STOC 2013, pp. 555\u2013564. ACM, New York (2013).","DOI":"10.1145\/2488608.2488678"},{"key":"1139_CR21","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1007\/978-3-642-55220-5_32","volume-title":"Advances in Cryptology - EUROCRYPT 2014, LNCS","author":"S Goldwasser","year":"2014","unstructured":"Goldwasser S., Gordon S.D., Goyal V., Jain A., Katz J., Liu F., Sahai A., Shi E., Zhou H.: Multi-input functional encryption. In: Nguyen P.Q., Oswald E. (eds.) Advances in Cryptology - EUROCRYPT 2014, LNCS, vol. 8441, pp. 578\u2013602. Springer, Heidelberg (2014)."},{"key":"1139_CR22","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-642-32009-5_11","volume-title":"Advances in Cryptology - CRYPTO 2012, LNCS","author":"S Gorbunov","year":"2012","unstructured":"Gorbunov S., Vaikuntanathan V., Wee H.: Functional encryption with bounded collusions via multi-party computation. In: Safavi-Naini R., Canetti R. (eds.) Advances in Cryptology - CRYPTO 2012, LNCS, vol. 7417, pp. 162\u2013179. Springer, Heidelberg (2012)."},{"key":"1139_CR23","doi-asserted-by":"crossref","unstructured":"Goyal V., Pandey O., Sahai A., Waters B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Juels A., Wright R.N., di Vimercati S.D.C. (eds.) ACM Conference on Computer and Communications Security - CCS 2006, pp. 89\u201398. ACM, New York (2006).","DOI":"10.1145\/1180405.1180418"},{"key":"1139_CR24","first-page":"155","volume-title":"Theory of Cryptography - TCC 2008, LNCS","author":"C Hazay","year":"2008","unstructured":"Hazay C., Lindell Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In: Canetti R. (ed.) Theory of Cryptography - TCC 2008, LNCS, vol. 4948, pp. 155\u2013175. Springer, Heidelberg (2008)."},{"key":"1139_CR25","unstructured":"Huang Y., Evans D., Katz J.: Private set intersection: Are garbled circuits better than custom protocols? In: Network and Distributed System Security Symposium - NDSS 2012, The Internet Society (2012)."},{"key":"1139_CR26","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/336992.337012","volume-title":"ACM Conference on Electronic Commerce - EC-99","author":"BA Huberman","year":"1999","unstructured":"Huberman B.A., Franklin M.K., Hogg T.: Enhancing privacy and trust in electronic communities. In: Feldman S.I., Wellman M.P. (eds.) ACM Conference on Electronic Commerce - EC-99, pp. 78\u201386. ACM, New York (1999)."},{"key":"1139_CR27","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-662-45472-5_13","volume-title":"Financial Cryptography and Data Security - FC 2014, LNCS","author":"S Kamara","year":"2014","unstructured":"Kamara S., Mohassel P., Raykova M., Sadeghian S.S.: Scaling private set intersection to billion-element sets. In: Christin N., Safavi-Naini R. (eds.) Financial Cryptography and Data Security - FC 2014, LNCS, vol. 8437, pp. 195\u2013215. Springer, Heidelberg (2014)."},{"key":"1139_CR28","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-540-78967-3_9","volume-title":"Advances in Cryptology - EUROCRYPT 2008, LNCS","author":"J Katz","year":"2008","unstructured":"Katz J., Sahai A., Waters B.: Predicate encryption supporting disjunctions, polynomial equations, and inner products. In: Smart N.P. (ed.) Advances in Cryptology - EUROCRYPT 2008, LNCS, vol. 4965, pp. 146\u2013162. Springer, Heidelberg (2008)."},{"key":"1139_CR29","doi-asserted-by":"crossref","unstructured":"Kolesnikov V., Kumaresan R., Rosulek M., Trieu N.: Efficient batched oblivious PRF with applications to private set intersection. In: Weippl E.R., Katzenbeisser S., Kruegel C., Myers A.C., Halevi S. (eds.) ACM Conference on Computer and Communications Security - CCS 2016, pp. 818\u2013829. ACM, New York (2016).","DOI":"10.1145\/2976749.2978381"},{"key":"1139_CR30","unstructured":"Lee K.: Efficient multi-client functional encryption for conjunctive equality and range queries. Cryptology ePrint Archive, Report 2020\/822, http:\/\/eprint.iacr.org\/2020\/822 (2020)."},{"key":"1139_CR31","doi-asserted-by":"crossref","unstructured":"Lee K., Lee D.H.: Two-input functional encryption for inner products from bilinear maps. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 101-A(6):915\u2013928 (2018).","DOI":"10.1587\/transfun.E101.A.915"},{"issue":"1","key":"1139_CR32","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s10623-021-00961-w","volume":"90","author":"K Lee","year":"2022","unstructured":"Lee K., Seo M.: Functional encryption for set intersection in the multi-client setting. Des. Codes Cryptogr. 90(1), 17\u201347 (2022).","journal-title":"Des. Codes Cryptogr."},{"key":"1139_CR33","unstructured":"Pinkas B., Schneider T., Zohner M.: Faster private set intersection based on OT extension. In: Fu K., Jung J. (eds.) Proceedings of the 23rd USENIX Security Symposium, pp. 797\u2013812. USENIX Association (2014)."},{"key":"1139_CR34","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/11426639_27","volume-title":"Advances in Cryptology - EUROCRYPT 2005, LNCS","author":"A Sahai","year":"2005","unstructured":"Sahai A., Waters B.: Fuzzy identity-based encryption. In: Cramer R. (ed.) Advances in Cryptology - EUROCRYPT 2005, LNCS, vol. 3494, pp. 457\u2013473. Springer, Heidelberg (2005)."},{"key":"1139_CR35","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-69053-0_18","volume-title":"Advances in Cryptology - EUROCRYPT \u201997, LNCS","author":"V Shoup","year":"1997","unstructured":"Shoup V.: Lower bounds for discrete logarithms and related problems. In: Fumy W. (ed.) Advances in Cryptology - EUROCRYPT \u201997, LNCS, vol. 1233, pp. 256\u2013266. Springer, Heidelberg (1997)."},{"issue":"2","key":"1139_CR36","first-page":"95","volume":"43","author":"N Trieu","year":"2020","unstructured":"Trieu N., Shehata K., Saxena P., Shokri R., Song D.: Epione: Lightweight contact tracing with strong privacy. IEEE Data Eng. Bull. 43(2), 95\u2013107 (2020).","journal-title":"IEEE Data Eng. Bull."},{"key":"1139_CR37","first-page":"97","volume-title":"Information Security and Privacy - ACISP 2019, LNCS","author":"T van de Kamp","year":"2019","unstructured":"van de Kamp T., Stritzl D., Jonker W., Peter A.: Two-client and multi-client functional encryption for set intersection. In: Jang-Jaccard J., Guo F. (eds.) Information Security and Privacy - ACISP 2019, LNCS, vol. 11547, pp. 97\u2013115. Springer, Heidelberg (2019)."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01139-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-022-01139-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01139-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,10]],"date-time":"2023-03-10T18:20:04Z","timestamp":1678472404000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-022-01139-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,29]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1139"],"URL":"https:\/\/doi.org\/10.1007\/s10623-022-01139-8","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,29]]},"assertion":[{"value":"15 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}