{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T15:49:53Z","timestamp":1789141793161,"version":"build-2803163510"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T00:00:00Z","timestamp":1709164800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T00:00:00Z","timestamp":1709164800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Swiss Federal Institute of Technology Zurich"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We construct an identity-based encryption (IBE) scheme that is tightly secure in a very strong sense. Specifically, we consider a setting with many instances of the scheme and many encryptions per instance. In this setting, we reduce the security of our scheme to a variant of a simple assumption used for a similar purpose by Chen and Wee (CRYPTO 2013, Springer, 2013). The security loss of our reduction is<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textbf{O} (k)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>k<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(where<jats:inline-formula><jats:alternatives><jats:tex-math>$$k $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is the security parameter). Our scheme is the first IBE scheme to achieve this strong flavor of tightness under a simple assumption. Technically, our scheme is a variation of the IBE scheme by Chen and Wee. However, in order to \u201clift\u201d their results to the multi-instance, multi-ciphertext case, we need to develop new ideas. In particular, while we build on (and extend) their high-level proof strategy, we deviate significantly in the low-level proof steps.<\/jats:p>","DOI":"10.1007\/s00145-024-09496-4","type":"journal-article","created":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T21:24:28Z","timestamp":1709241868000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Identity-Based Encryption with (Almost) Tight Security in the Multi-instance, Multi-ciphertext Setting"],"prefix":"10.1007","volume":"37","author":[{"given":"Dennis","family":"Hofheinz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jessica","family":"Koch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christoph","family":"Striecks","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,2,29]]},"reference":[{"key":"9496_CR1","doi-asserted-by":"publisher","unstructured":"Masayuki Abe, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, and Miyako Ohkubo. Tagged one-time signatures: Tight security and optimal tag size. In Kaoru Kurosawa and Goichiro Hanaoka, editors, PKC 2013, volume 7778 of LNCS, pages 312\u2013331. Springer, February \/ March 2013. https:\/\/doi.org\/10.1007\/978-3-642-36362-7_20.","DOI":"10.1007\/978-3-642-36362-7_20"},{"key":"9496_CR2","doi-asserted-by":"publisher","unstructured":"Nuttapong Attrapadung, Goichiro Hanaoka, and Shota Yamada. A framework for identity-based encryption with almost tight security. LNCS, pages 521\u2013549. Springer, December 2015. https:\/\/doi.org\/10.1007\/978-3-662-48797-6_22.","DOI":"10.1007\/978-3-662-48797-6_22"},{"key":"9496_CR3","doi-asserted-by":"crossref","unstructured":"Mihir Bellare, Anand Desai, Eric Jokipii, and Phillip Rogaway. A concrete security treatment of symmetric encryption. In 38th FOCS, pages 394\u2013403. IEEE Computer Society Press, October 1997.","DOI":"10.1109\/SFCS.1997.646128"},{"key":"9496_CR4","doi-asserted-by":"crossref","unstructured":"Mihir Bellare, Anand Desai, David Pointcheval, and Phillip Rogaway. Relations among notions of security for public-key encryption schemes. In Hugo Krawczyk, editor, CRYPTO\u201998, volume 1462 of LNCS, pages 26\u201345. Springer, August 1998.","DOI":"10.1007\/BFb0055718"},{"key":"9496_CR5","doi-asserted-by":"crossref","unstructured":"Mihir Bellare, Alexandra Boldyreva, and Silvio Micali. Public-key encryption in a multi-user setting: Security proofs and improvements. In Bart Preneel, editor, EUROCRYPT 2000, volume 1807 of LNCS, pages 259\u2013274. Springer, May 2000.","DOI":"10.1007\/3-540-45539-6_18"},{"key":"9496_CR6","doi-asserted-by":"crossref","unstructured":"Mihir Bellare, Brent Waters, and Scott Yilek. Identity-based encryption secure against selective opening attack. In Yuval Ishai, editor, TCC 2011, volume 6597 of LNCS, pages 235\u2013252. Springer, March 2011.","DOI":"10.1007\/978-3-642-19571-6_15"},{"key":"9496_CR7","doi-asserted-by":"crossref","unstructured":"Olivier Blazy, Eike Kiltz, and Jiaxin Pan. (hierarchical) identity-based encryption from affine message authentication. In Proceedings of CRYPTO (1) 2014, number 8616 in Lecture Notes in Computer Science, pages 408\u2013425. Springer, 2014.","DOI":"10.1007\/978-3-662-44371-2_23"},{"key":"9496_CR8","doi-asserted-by":"crossref","unstructured":"Alexandra Boldyreva. Strengthening security of RSA-OAEP. In Marc Fischlin, editor, CT-RSA 2009, volume 5473 of LNCS, pages 399\u2013413. Springer, April 2009.","DOI":"10.1007\/978-3-642-00862-7_27"},{"key":"9496_CR9","doi-asserted-by":"crossref","unstructured":"Dan Boneh and Xavier Boyen. Short signatures without random oracles. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 56\u201373. Springer, May 2004.","DOI":"10.1007\/978-3-540-24676-3_4"},{"key":"9496_CR10","doi-asserted-by":"crossref","unstructured":"Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 213\u2013229. Springer, August 2001.","DOI":"10.1007\/3-540-44647-8_13"},{"key":"9496_CR11","doi-asserted-by":"crossref","unstructured":"Dan Boneh, Shai Halevi, Michael Hamburg, and Rafail Ostrovsky. Circular-secure encryption from decision Diffie\u2013Hellman. In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 108\u2013125. Springer, August 2008.","DOI":"10.1007\/978-3-540-85174-5_7"},{"key":"9496_CR12","doi-asserted-by":"crossref","unstructured":"David Cash, Eike Kiltz, and Victor Shoup. The twin Diffie\u2013Hellman problem and applications. In Nigel P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 127\u2013145. Springer, April 2008.","DOI":"10.1007\/978-3-540-78967-3_8"},{"key":"9496_CR13","doi-asserted-by":"publisher","unstructured":"Jie Chen and Hoeteck Wee. Fully, (almost) tightly secure IBE and dual system groups. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 435\u2013460. Springer, August 2013a. https:\/\/doi.org\/10.1007\/978-3-642-40084-1_25.","DOI":"10.1007\/978-3-642-40084-1_25"},{"key":"9496_CR14","doi-asserted-by":"crossref","unstructured":"Jie Chen and Hoeteck Wee. Fully, (almost) tightly secure IBE from standard assumptions. Cryptology ePrint Archive, Report 2013\/803, 2013b. http:\/\/eprint.iacr.org\/2013\/803.","DOI":"10.1007\/978-3-642-40084-1_25"},{"key":"9496_CR15","unstructured":"Jie Chen and Hoeteck Wee. Dual system groups and its applications \u2014 compact hibe and more. Cryptology ePrint Archive, Report 2014\/265, 2014. http:\/\/eprint.iacr.org\/."},{"key":"9496_CR16","doi-asserted-by":"publisher","unstructured":"Jie Chen, Junqing Gong, and Jian Weng. Tightly secure IBE under constant-size master public key. LNCS, pages 207\u2013231. Springer, 2017. https:\/\/doi.org\/10.1007\/978-3-662-54365-8_9.","DOI":"10.1007\/978-3-662-54365-8_9"},{"key":"9496_CR17","doi-asserted-by":"crossref","unstructured":"David Mandell Freeman. Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 44\u201361. Springer, May 2010.","DOI":"10.1007\/978-3-642-13190-5_3"},{"key":"9496_CR18","doi-asserted-by":"crossref","unstructured":"David Galindo, Sebasti\u00e0 Mart\u00edn Mollev\u00ed, Paz Morillo, and Jorge Luis Villar. Easy verifiable primitives and practical public key cryptosystems. In Colin Boyd and Wenbo Mao, editors, ISC 2003, volume 2851 of LNCS, pages 69\u201383. Springer, October 2003.","DOI":"10.1007\/10958513_6"},{"key":"9496_CR19","doi-asserted-by":"publisher","unstructured":"Sanjam Garg, Romain Gay, and Mohammad Hajiabadi. Master-key KDM-secure IBE from pairings. In LNCS, pages 123\u2013152. Springer, 2020. https:\/\/doi.org\/10.1007\/978-3-030-45374-9_5.","DOI":"10.1007\/978-3-030-45374-9_5"},{"key":"9496_CR20","doi-asserted-by":"publisher","unstructured":"Romain Gay, Dennis Hofheinz, Eike Kiltz, and Hoeteck Wee. Tightly CCA-secure encryption without pairings. LNCS, pages 1\u201327. Springer, 2016. https:\/\/doi.org\/10.1007\/978-3-662-49890-3_1.","DOI":"10.1007\/978-3-662-49890-3_1"},{"key":"9496_CR21","doi-asserted-by":"publisher","unstructured":"Romain Gay, Dennis Hofheinz, and Lisa Kohl. Kurosawa-desmedt meets tight security. LNCS, pages 133\u2013160. Springer, 2017. https:\/\/doi.org\/10.1007\/978-3-319-63697-9_5.","DOI":"10.1007\/978-3-319-63697-9_5"},{"key":"9496_CR22","doi-asserted-by":"crossref","unstructured":"Craig Gentry. Practical identity-based encryption without random oracles. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 445\u2013464. Springer, May \/ June 2006.","DOI":"10.1007\/11761679_27"},{"key":"9496_CR23","doi-asserted-by":"crossref","unstructured":"Craig Gentry and Shai Halevi. Hierarchical identity based encryption with polynomially many levels. In Omer Reingold, editor, TCC 2009, volume 5444 of LNCS, pages 437\u2013456. Springer, March 2009.","DOI":"10.1007\/978-3-642-00457-5_26"},{"key":"9496_CR24","doi-asserted-by":"publisher","unstructured":"Junqing Gong, Jie Chen, Xiaolei Dong, Zhenfu Cao, and Shaohua Tang. Extended nested dual system groups, revisited. LNCS, pages 133\u2013163. Springer, 2016a. https:\/\/doi.org\/10.1007\/978-3-662-49384-7_6.","DOI":"10.1007\/978-3-662-49384-7_6"},{"issue":"11","key":"9496_CR25","doi-asserted-by":"publisher","first-page":"1669","DOI":"10.1093\/comjnl\/bxw030","volume":"59","author":"Junqing Gong","year":"2016","unstructured":"Junqing Gong, Xiaolei Dong, Zhenfu Cao, and Jie Chen. Almost-tight identity based encryption against selective opening attack. The Computer Journal, 59 (11): 1669\u20131688, 2016b. https:\/\/doi.org\/10.1093\/comjnl\/bxw030.","journal-title":"The Computer Journal"},{"key":"9496_CR26","doi-asserted-by":"publisher","unstructured":"Junqing Gong, Xiaolei Dong, Jie Chen, and Zhenfu Cao. Efficient IBE with tight reduction to standard assumption in the multi-challenge setting. LNCS, pages 624\u2013654. Springer, December 2016c. https:\/\/doi.org\/10.1007\/978-3-662-53890-6_21.","DOI":"10.1007\/978-3-662-53890-6_21"},{"key":"9496_CR27","doi-asserted-by":"crossref","unstructured":"Jens Groth and Amit Sahai. Efficient non-interactive proof systems for bilinear groups. In Nigel P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 415\u2013432. Springer, April 2008.","DOI":"10.1007\/978-3-540-78967-3_24"},{"key":"9496_CR28","doi-asserted-by":"publisher","unstructured":"Dennis Hofheinz. Adaptive partitioning. LNCS, pages 489\u2013518. Springer, 2017. https:\/\/doi.org\/10.1007\/978-3-319-56617-7_17.","DOI":"10.1007\/978-3-319-56617-7_17"},{"key":"9496_CR29","doi-asserted-by":"crossref","unstructured":"Dennis Hofheinz and Tibor Jager. Tightly secure signatures and public-key encryption. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 590\u2013607. Springer, August 2012.","DOI":"10.1007\/978-3-642-32009-5_35"},{"key":"9496_CR30","doi-asserted-by":"publisher","unstructured":"Dennis Hofheinz, Jessica Koch, and Christoph Striecks. Identity-based encryption with (almost) tight security in the multi-instance, multi-ciphertext setting. In PKC 2015, LNCS, pages 799\u2013822. Springer, 2015. https:\/\/doi.org\/10.1007\/978-3-662-46447-2_36.","DOI":"10.1007\/978-3-662-46447-2_36"},{"key":"9496_CR31","doi-asserted-by":"publisher","unstructured":"Dennis Hofheinz, Dingding Jia, and Jiaxin Pan. Identity-based encryption tightly secure under chosen-ciphertext attacks. LNCS, pages 190\u2013220. Springer, December 2018. https:\/\/doi.org\/10.1007\/978-3-030-03329-3_7.","DOI":"10.1007\/978-3-030-03329-3_7"},{"key":"9496_CR32","doi-asserted-by":"publisher","unstructured":"Roman Langrehr and Jiaxin Pan. Tightly secure hierarchical identity-based encryption. LNCS, pages 436\u2013465. Springer, 2019. https:\/\/doi.org\/10.1007\/978-3-030-17253-4_15.","DOI":"10.1007\/978-3-030-17253-4_15"},{"key":"9496_CR33","doi-asserted-by":"publisher","unstructured":"Roman Langrehr and Jiaxin Pan. Unbounded HIBE with tight security. LNCS, pages 129\u2013159. Springer, December 2020a. https:\/\/doi.org\/10.1007\/978-3-030-64834-3_5.","DOI":"10.1007\/978-3-030-64834-3_5"},{"issue":"4","key":"9496_CR34","doi-asserted-by":"publisher","first-page":"1787","DOI":"10.1007\/s00145-020-09356-x","volume":"33","author":"Roman Langrehr","year":"2020","unstructured":"Roman Langrehr and Jiaxin Pan. Tightly secure hierarchical identity-based encryption. Journal of Cryptology, 33 (4): 1787\u20131821, 2020b. https:\/\/doi.org\/10.1007\/s00145-020-09356-x.","journal-title":"Journal of Cryptology"},{"key":"9496_CR35","doi-asserted-by":"publisher","unstructured":"Roman Langrehr and Jiaxin Pan. Hierarchical identity-based encryption with tight multi-challenge security. LNCS, pages 153\u2013183. Springer, 2020c. https:\/\/doi.org\/10.1007\/978-3-030-45374-9_6.","DOI":"10.1007\/978-3-030-45374-9_6"},{"key":"9496_CR36","doi-asserted-by":"crossref","unstructured":"Allison B. Lewko. Tools for simulating features of composite order bilinear groups in the prime order setting. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 318\u2013335. Springer, April 2012.","DOI":"10.1007\/978-3-642-29011-4_20"},{"key":"9496_CR37","doi-asserted-by":"crossref","unstructured":"Beno\u00eet Libert, Marc Joye, Moti Yung, and Thomas Peters. Concise multi-challenge CCA-secure encryption and signatures with almost tight security. In Proceedings of ASIACRYPT 2014, Lecture Notes in Computer Science. Springer, 2014.","DOI":"10.1007\/978-3-662-45608-8_1"},{"key":"9496_CR38","doi-asserted-by":"crossref","unstructured":"Brent Waters. Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions. In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 619\u2013636. Springer, August 2009.","DOI":"10.1007\/978-3-642-03356-8_36"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09496-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-024-09496-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09496-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T16:35:23Z","timestamp":1731515723000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-024-09496-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,29]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["9496"],"URL":"https:\/\/doi.org\/10.1007\/s00145-024-09496-4","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,29]]},"assertion":[{"value":"10 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 February 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}