---
_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'
...