The cost of adaptivity in security games on graphs

Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference.

Download (ext.)
Conference Paper | Accepted | English
Department
Abstract
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.
Publishing Year
Date Published
2021-07-08
Proceedings Title
19th Theory of Cryptography Conference 2021
Conference
TCC: Theory of Cryptography Conference
Conference Location
Raleigh, NC, United States
Conference Date
2021-11-08 – 2021-11-11
IST-REx-ID

Cite this

Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research.
Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (n.d.). The cost of adaptivity in security games on graphs. In 19th Theory of Cryptography Conference 2021. Raleigh, NC, United States: International Association for Cryptologic Research.
Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research, n.d.
C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in 19th Theory of Cryptography Conference 2021, Raleigh, NC, United States.
Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference.
Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Dissertation containing IST record

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar