--- _id: '10410' abstract: - lang: eng text: The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques. acknowledgement: C. Kamath—Supported by Azrieli International Postdoctoral Fellowship. Most of the work was done while the author was at Northeastern University and Charles University, funded by the IARPA grant IARPA/2019-19-020700009 and project PRIMUS/17/SCI/9, respectively. K. Klein—Supported in part by ERC CoG grant 724307. Most of the work was done while the author was at IST Austria funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT). K. Pietrzak—Funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT). alternative_title: - LNCS article_processing_charge: No author: - first_name: Chethan full_name: Kamath Hosdurg, Chethan id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87 last_name: Kamath Hosdurg - first_name: Karen full_name: Klein, Karen id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87 last_name: Klein - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Michael full_name: Walter, Michael id: 488F98B0-F248-11E8-B48F-1D18A9856A87 last_name: Walter orcid: 0000-0003-3186-2482 citation: ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: 19th International Conference. Vol 13043. Springer Nature; 2021:550-581. doi:10.1007/978-3-030-90453-1_19' apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The cost of adaptivity in security games on graphs. In 19th International Conference (Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_19' chicago: Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th International Conference, 13043:550–81. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_19. ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13043, pp. 550–581. ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 550–581.' mla: Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” 19th International Conference, vol. 13043, Springer Nature, 2021, pp. 550–81, doi:10.1007/978-3-030-90453-1_19. short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 550–581. conference: end_date: 2021-11-11 location: Raleigh, NC, United States name: 'TCC: Theory of Cryptography' start_date: 2021-11-08 date_created: 2021-12-05T23:01:43Z date_published: 2021-11-04T00:00:00Z date_updated: 2023-10-17T09:24:07Z day: '04' department: - _id: KrPi doi: 10.1007/978-3-030-90453-1_19 ec_funded: 1 external_id: isi: - '000728364000019' intvolume: ' 13043' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://ia.cr/2021/059 month: '11' oa: 1 oa_version: Preprint page: 550-581 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: 19th International Conference publication_identifier: eissn: - 1611-3349 isbn: - 9-783-0309-0452-4 issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '10048' relation: earlier_version status: public scopus_import: '1' status: public title: The cost of adaptivity in security games on graphs type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 13043 year: '2021' ...