The Cost of Adaptivity in Security Games on Graphs
METADATA ONLY
Loading...
Author / Producer
Date
2021
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Book title
Theory of Cryptography
Journal / series
Volume
13043
Pages / Article No.
550 - 581
Publisher
Springer
Event
19th International Conference on Theory of Cryptography (TCC 2021)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
adaptive security; lower bounds; generalised selective decryption; group messaging; constrained pseudorandom function; proxy re-encryption
Organisational unit
09693 - Hofheinz, Dennis / Hofheinz, Dennis
Notes
Funding
724307 - Preparing Cryptography for Modern Applications (EC)