{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:21:33Z","timestamp":1740122493464,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2023,4,3]],"date-time":"2023-04-03T00:00:00Z","timestamp":1680480000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,3]],"date-time":"2023-04-03T00:00:00Z","timestamp":1680480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009105","name":"Ministry of Internal Affairs and Communications","doi-asserted-by":"crossref","award":["JPJ000254"],"award-info":[{"award-number":["JPJ000254"]}],"id":[{"id":"10.13039\/501100009105","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Broadcast Encryption (BE) is public-key encryption allowing a sender to encrypt a message by specifing recipients, and only the specified recipients can decrypt the message. In several BE applications, since the privacy of recipients allowed to access the message is often as important as the confidentiality of the message, anonymity is introduced as an additional but important security requirement for BE. Kiayias and Samari (IH 2013) presented an asymptotic lower bound on the ciphertext sizes in BE schemes satisfying anonymity (ANO-BE for short). More precisely, their lower bound is derived under the assumption that ANO-BE schemes have a special property. However, it is insufficient to show their lower bound is asymptotically tight since it is unclear whether existing ANO-BE schemes meet the special property. In this work, we derive asymptotically tight lower bounds on the ciphertext size in ANO-BE by assuming only properties that most existing ANO-BE schemes satisfy. With a similar technique, we first derive asymptoticallyPlease provide MSC codes. For more details, please visit http:\/\/www.ams.org\/msc\/. tight lower bounds on the authenticator sizes in Anonymous Broadcast Authentication (ABA). Furthermore, we extend the above result and present (non-asymptotically) tight lower and upper bounds on thePlease check and confirm the Running title. ciphertext sizes in ANO-BE. We show that a variant of ANO-BE scheme proposed by Li and Gong (ACNS 2018) is optimal. We also provide tight bounds on the authenticator sizes in ABA via the same approach as ANO-BE, and propose an optimal construction for ABA.<\/jats:p>","DOI":"10.1007\/s10623-023-01211-x","type":"journal-article","created":{"date-parts":[[2023,4,3]],"date-time":"2023-04-03T17:02:31Z","timestamp":1680541351000},"page":"2523-2562","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight lower bounds and optimal constructions of anonymous broadcast encryption and authentication"],"prefix":"10.1007","volume":"91","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2804-8079","authenticated-orcid":false,"given":"Hirokazu","family":"Kobayashi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yohei","family":"Watanabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhiko","family":"Minematsu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junji","family":"Shikata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,3]]},"reference":[{"key":"1211_CR1","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-030-45721-1_2","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2020","author":"S Agrawal","year":"2020","unstructured":"Agrawal S., Yamada S.: Optimal broadcast encryption from pairings and LWE. In: Canteaut A., Ishai Y. (eds.) Advances in Cryptology\u2014EUROCRYPT 2020, pp. 13\u201343. Springer, Cham (2020)."},{"key":"1211_CR2","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-030-64375-1_6","volume-title":"Theory of Cryptography","author":"S Agrawal","year":"2020","unstructured":"Agrawal S., Wichs D., Yamada S.: Optimal broadcast encryption from LWE and pairings in the standard model. In: Pass R., Pietrzak K. (eds.) Theory of Cryptography, pp. 149\u2013178. Springer, Cham (2020)."},{"key":"1211_CR3","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/11889663_4","volume-title":"Financial Cryptography and Data Security","author":"A Barth","year":"2006","unstructured":"Barth A., Boneh D., Waters B.: Privacy in encrypted content distribution using private broadcast encryption. In: Di Crescenzo G., Rubin A. (eds.) Financial Cryptography and Data Security, pp. 52\u201364. Springer, Berlin (2006)."},{"key":"1211_CR4","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-662-44371-2_23","volume-title":"Advances in Cryptology\u2014CRYPTO 2014","author":"O Blazy","year":"2014","unstructured":"Blazy O., Kiltz E., Pan J.: (hierarchical) Identity-based encryption from affine message authentication. In: Garay J.A., Gennaro R. (eds.) Advances in Cryptology\u2014CRYPTO 2014, pp. 408\u2013425. Springer, Berlin (2014)."},{"key":"1211_CR5","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/11535218_16","volume-title":"Advances in Cryptology\u2014CRYPTO 2005","author":"D Boneh","year":"2005","unstructured":"Boneh D., Gentry C., Waters B.: Collusion resistant broadcast encryption with short ciphertexts and private keys. In: Shoup V. (ed.) Advances in Cryptology\u2014CRYPTO 2005, pp. 258\u2013275. Springer, Berlin (2005)."},{"key":"1211_CR6","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-662-44371-2_12","volume-title":"Advances in Cryptology\u2014CRYPTO 2014","author":"D Boneh","year":"2014","unstructured":"Boneh D., Waters B., Zhandry M.: Low overhead broadcast encryption from multilinear maps. In: Garay J.A., Gennaro R. (eds.) Advances in Cryptology\u2014CRYPTO 2014, pp. 206\u2013223. Springer, Berlin (2014)."},{"key":"1211_CR7","doi-asserted-by":"publisher","unstructured":"Chan H., Perrig A.: Round-efficient broadcast authentication protocols for fixed topology classes, pp. 257\u2013272 (2010). https:\/\/doi.org\/10.1109\/SP.2010.22.","DOI":"10.1109\/SP.2010.22"},{"issue":"2","key":"1211_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.13154\/tosc.v2017.i2.27-58","volume":"2017","author":"B Cogliati","year":"2017","unstructured":"Cogliati B., Lee J., Seurin Y.: New constructions of macs from (tweakable) block ciphers. IACR Trans. Symmetric Cryptol. 2017(2), 27\u201358 (2017). https:\/\/doi.org\/10.13154\/tosc.v2017.i2.27-58.","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"1211_CR9","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-642-40084-1_8","volume-title":"Advances in Cryptology\u2014CRYPTO 2013","author":"A Escala","year":"2013","unstructured":"Escala A., Herold G., Kiltz E., R\u00e0fols C., Villar J.: An algebraic framework for Diffie-Hellman assumptions. In: Canetti R., Garay J.A. (eds.) Advances in Cryptology\u2014CRYPTO 2013, pp. 129\u2013147. Springer, Berlin (2013)."},{"key":"1211_CR10","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-642-30057-8_14","volume-title":"Public Key Cryptography\u2014PKC 2012","author":"N Fazio","year":"2012","unstructured":"Fazio N., Perera I.M.: Outsider-anonymous broadcast encryption with sublinear ciphertexts. In: Fischlin M., Buchmann J., Manulis M. (eds.) Public Key Cryptography\u2014PKC 2012, pp. 225\u2013242. Springer, Berlin (2012)."},{"key":"1211_CR11","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/3-540-48329-2_40","volume-title":"Advances in Cryptology\u2014CRYPTO\u2019 93","author":"A Fiat","year":"1994","unstructured":"Fiat A., Naor M.: Broadcast encryption. In: Stinson D.R. (ed.) Advances in Cryptology\u2014CRYPTO\u2019 93, pp. 480\u2013491. Springer, Berlin (1994)."},{"key":"1211_CR12","doi-asserted-by":"crossref","unstructured":"Fischlin M.: Pseudorandom function tribe ensembles based on one-way permutations: improvements and applications. In: EUROCRYPT (1999).","DOI":"10.1007\/3-540-48910-X_30"},{"key":"1211_CR13","first-page":"1","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2016","author":"R Gay","year":"2016","unstructured":"Gay R., Hofheinz D., Kiltz E., Wee H.: Tightly CCA-secure encryption without pairings. In: Fischlin M., Coron J.-S. (eds.) Advances in Cryptology\u2014EUROCRYPT 2016, pp. 1\u201327. Springer, Berlin (2016)."},{"key":"1211_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-319-63697-9_5","volume-title":"Advances in Cryptology\u2014CRYPTO 2017","author":"R Gay","year":"2017","unstructured":"Gay R., Hofheinz D., Kohl L.: Kurosawa-Desmedt meets tight security. In: Katz J., Shacham H. (eds.) Advances in Cryptology\u2014CRYPTO 2017, pp. 133\u2013160. Springer, Cham (2017)."},{"key":"1211_CR15","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-319-98113-0_7","volume-title":"Security and Cryptography for Networks, SCN 2018","author":"R Gay","year":"2018","unstructured":"Gay R., Kowalczyk L., Wee H.: Tight adaptively secure broadcast encryption with short ciphertexts and keys. In: Catalano D., De Prisco R. (eds.) Security and Cryptography for Networks, SCN 2018, pp. 123\u2013139. Springer, Cham (2018)."},{"key":"1211_CR16","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-01001-9_10","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2009","author":"C Gentry","year":"2009","unstructured":"Gentry C., Waters B.: Adaptive security in broadcast encryption systems (with short ciphertexts). In: Joux A. (ed.) Advances in Cryptology\u2014EUROCRYPT 2009, pp. 171\u2013188. Springer, Berlin (2009)."},{"key":"1211_CR17","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s10623-017-0339-3","volume":"86","author":"S Han","year":"2018","unstructured":"Han S., Liu S., Qin B., Gu D.: Tightly CCA-secure identity-based encryption with ciphertext pseudorandomness. Des. Codes Cryptogr. 86, 517\u2013554 (2018). https:\/\/doi.org\/10.1007\/s10623-017-0339-3.","journal-title":"Des. Codes Cryptogr."},{"key":"1211_CR18","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-319-56617-7_17","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2017","author":"D Hofheinz","year":"2017","unstructured":"Hofheinz D.: Adaptive partitioning. In: Coron J.-S., Nielsen J.B. (eds.) Advances in Cryptology\u2014EUROCRYPT 2017, pp. 489\u2013518. Springer, Cham (2017)."},{"key":"1211_CR19","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-030-03329-3_7","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2018","author":"D Hofheinz","year":"2018","unstructured":"Hofheinz D., Jia D., Pan J.: Identity-based encryption tightly secure under chosen-ciphertext attacks. In: Peyrin T., Galbraith S. (eds.) Advances in Cryptology\u2014ASIACRYPT 2018, pp. 190\u2013220. Springer, Cham (2018)."},{"key":"1211_CR20","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-36373-3_12","volume-title":"Information Hiding","author":"A Kiayias","year":"2013","unstructured":"Kiayias A., Samari K.: Lower bounds for private broadcast encryption. In: Kirchner M., Ghosal D. (eds.) Information Hiding, pp. 176\u2013190. Springer, Berlin (2013)."},{"key":"1211_CR21","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-662-46803-6_4","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2015","author":"E Kiltz","year":"2015","unstructured":"Kiltz E., Wee H.: Quasi-adaptive NIZK for linear subspaces revisited. In: Oswald E., Fischlin M. (eds.) Advances in Cryptology\u2014EUROCRYPT 2015, pp. 101\u2013128. Springer, Berlin (2015)."},{"key":"1211_CR22","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-030-92641-0_6","volume-title":"Cryptography and Coding","author":"H Kobayashi","year":"2021","unstructured":"Kobayashi H., Watanabe Y., Shikata J.: Asymptotically tight lower bounds in anonymous broadcast encryption and authentication. In: Paterson M.B. (ed.) Cryptography and Coding, pp. 105\u2013128. Springer, Cham (2021)."},{"issue":"4","key":"1211_CR23","doi-asserted-by":"publisher","first-page":"1787","DOI":"10.1007\/s00145-020-09356-x","volume":"33","author":"R Langrehr","year":"2020","unstructured":"Langrehr R., Pan J.: Tightly secure hierarchical identity-based encryption. J. Cryptol. 33(4), 1787\u20131821 (2020).","journal-title":"J. Cryptol."},{"key":"1211_CR24","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/978-3-319-93387-0_26","volume-title":"Applied Cryptography and Network Security, ACNS 2018","author":"J Li","year":"2018","unstructured":"Li J., Gong J.: Improved anonymous broadcast encryptions. In: Preneel B., Vercauteren F. (eds.) Applied Cryptography and Network Security, ACNS 2018, pp. 497\u2013515. Springer, Cham (2018)."},{"key":"1211_CR25","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-30057-8_13","volume-title":"Public Key Cryptography\u2014PKC 2012","author":"B Libert","year":"2012","unstructured":"Libert B., Paterson K.G., Quaglia E.A.: Anonymous broadcast encryption: adaptive security and efficient constructions in the standard model. In: Fischlin M., Buchmann J., Manulis M. (eds.) Public Key Cryptography\u2014PKC 2012, pp. 206\u2013224. Springer, Berlin (2012)."},{"key":"1211_CR26","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-319-76578-5_3","volume-title":"Public-Key Cryptography\u2014PKC 2018","author":"L Lyu","year":"2018","unstructured":"Lyu L., Liu S., Han S., Gu D.: Tightly sim-so-CCA secure public key encryption from standard assumptions. In: Abdalla M., Dahab R. (eds.) Public-Key Cryptography\u2014PKC 2018, pp. 62\u201392. Springer, Cham (2018)."},{"key":"1211_CR27","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-030-65745-1_10","volume-title":"Network and System Security","author":"M Mandal","year":"2020","unstructured":"Mandal M., Nuida K.: Identity-based outsider anonymous broadcast encryption with simultaneous individual messaging. In: Kuty\u0142owski M., Zhang J., Chen C. (eds.) Network and System Security, pp. 167\u2013186. Springer, Cham (2020)."},{"key":"1211_CR28","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1007\/978-3-030-64837-4_24","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2020","author":"A Morgan","year":"2020","unstructured":"Morgan A., Pass R., Shi E.: On the adaptive security of MACS and PRFS. In: Moriai S., Wang H. (eds.) Advances in Cryptology\u2014ASIACRYPT 2020, pp. 724\u2013753. Springer, Cham (2020)."},{"key":"1211_CR29","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/978-3-662-53887-6_27","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2016","author":"P Morillo","year":"2016","unstructured":"Morillo P., R\u00e0fols C., Villar J.L.: The kernel matrix Diffie-Hellman assumption. In: Cheon J.H., Takagi T. (eds.) Advances in Cryptology\u2014ASIACRYPT 2016, pp. 729\u2013758. Springer, Berlin (2016)."},{"key":"1211_CR30","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/3-540-44647-8_3","volume-title":"Advances in Cryptology\u2014CRYPTO 2001","author":"D Naor","year":"2001","unstructured":"Naor D., Naor M., Lotspiech J.: Revocation and tracing schemes for stateless receivers. In: Kilian J. (ed.) Advances in Cryptology\u2014CRYPTO 2001, pp. 41\u201362. Springer, Berlin (2001)."},{"key":"1211_CR31","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-04159-4_21","volume-title":"Selected Areas in Cryptography","author":"J Patarin","year":"2009","unstructured":"Patarin J.: The coefficients h technique. In: Avanzi R.M., Keliher L., Sica F. (eds.) Selected Areas in Cryptography, pp. 328\u2013345. Springer, Berlin (2009)."},{"key":"1211_CR32","doi-asserted-by":"crossref","unstructured":"Perrig A.: The biba one-time signature and broadcast authentication protocol. In: Proc. 8th ACM Conference on Computer and Communications Security, pp. 28\u201337 (2001).","DOI":"10.1145\/501983.501988"},{"key":"1211_CR33","unstructured":"Perrig A., Canetti R., Tygar J.D., Song D.X.: Efficient authentication and signing of multicast streams over lossy channels. In: Proceedings of 2000 TEEE Symposium on Security and Privacy. S &P, pp. 56\u201373 (2000)."},{"key":"1211_CR34","unstructured":"Perrig A., Canetti R., Tygar J.D., Song D.: TESLA: Multicast source authentication transform. IETF draft. draft-ietf-msec-tesla-intro-03.txt (2004)."},{"key":"1211_CR35","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1007\/3-540-45682-1_32","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2001","author":"RL Rivest","year":"2001","unstructured":"Rivest R.L., Shamir A., Tauman Y.: How to leak a secret. In: Boyd C. (ed.) Advances in Cryptology\u2014ASIACRYPT 2001, pp. 552\u2013565. Springer, Berlin (2001)."},{"key":"1211_CR36","unstructured":"Shoup V.: Sequences of games: a tool for taming complexity in security proofs. In: IACR Cryptology ePrint Archive 2004, p. 332 (2004)."},{"key":"1211_CR37","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/978-3-030-75075-6_56","volume-title":"Advanced Information Networking and Applications","author":"Y Watanabe","year":"2021","unstructured":"Watanabe Y., Yanai N., Shikata J.: Anonymous broadcast authentication for securely remote-controlling IoT devices. In: Barolli L., Woungang I., Enokido T. (eds.) Advanced Information Networking and Applications, pp. 679\u2013690. Springer, Cham (2021)."},{"key":"1211_CR38","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/978-3-642-03356-8_36","volume-title":"Advances in Cryptology\u2014CRYPTO 2009","author":"B Waters","year":"2009","unstructured":"Waters B.: Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In: Halevi S. (ed.) Advances in Cryptology\u2014CRYPTO 2009, pp. 619\u2013636. Springer, Berlin (2009)."},{"key":"1211_CR39","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-662-49099-0_9","volume-title":"Theory of Cryptography","author":"H Wee","year":"2016","unstructured":"Wee H.: D\u00e9j\u00e0 q: Encore! un petit ibe. In: Kushilevitz E., Malkin T. (eds.) Theory of Cryptography, pp. 237\u2013258. Springer, Berlin (2016)."},{"key":"1211_CR40","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-319-03584-0_19","volume-title":"Cyberspace Safety and Security","author":"L Zhang","year":"2013","unstructured":"Zhang L., Wu Q., Mu Y.: Anonymous identity-based broadcast encryption with adaptive security. In: Wang G., Ray I., Feng D., Rajarajan M. (eds.) Cyberspace Safety and Security, pp. 258\u2013271. Springer, Cham (2013)."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-023-01211-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-023-01211-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-023-01211-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T17:14:00Z","timestamp":1686590040000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-023-01211-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,3]]},"references-count":40,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1211"],"URL":"https:\/\/doi.org\/10.1007\/s10623-023-01211-x","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2023,4,3]]},"assertion":[{"value":"31 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}