Paper 2021/059

The Cost of Adaptivity in Security Games on Graphs

Chethan Kamath, Karen Klein, Krzysztof Pietrzak, and Michael Walter


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.

Available format(s)
Publication info
Preprint. MINOR revision.
adaptive securityblack-box reductiongeneralized selective decryptiongroup messagingconstrained pseudorandom functionproxy re-encryption
Contact author(s)
ckamath @ protonmail com
kklein @ ist ac at
pietrzak @ ist ac at
mwalter @ ist ac at
2021-07-08: revised
2021-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chethan Kamath and Karen Klein and Krzysztof Pietrzak and Michael Walter},
      title = {The Cost of Adaptivity in Security Games on Graphs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/059},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.