Paper 2021/059
On the Cost of Adaptivity in Graph-Based Games
Chethan Kamath and Karen Klein and Krzysztof Pietrzak and Michael Walter
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 and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. The security games used to model these protocols involve an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a certain class of black-box reductions, which we term ``oblivious''. (We do however show one lower bound on proxy re-encryption that applies to general fully black-box reductions.) The fact that our lower bounds crucially rely on ``obliviousness'' hints to the possibility that the existing upper bounds can be improved by using more sophisticated reductions. As the main technical contribution, we introduce a two-player multi-stage game called the Builder-Pebbler Game and then analyze strategies for this game to establish bounds on success probability of its players. Finally, using oracle separation techniques, we translate these bounds into cryptographic lower bounds.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- adaptive securityblack-box reductiongeneralized selective decryptionproxy re-encryption
- Contact author(s)
- ckamath @ protonmail com,kklein @ ist ac at,pietrzak @ ist ac at,mwalter @ ist ac at
- History
- 2021-07-08: revised
- 2021-01-18: received
- See all versions
- Short URL
- https://ia.cr/2021/059
- License
-
CC BY