Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / adaptive security, black-box reduction, generalized selective decryption, proxy re-encryption

Date: received 15 Jan 2021

Contact author: ckamath at protonmail com,kklein@ist ac at,pietrzak@ist ac at,mwalter@ist ac at

Available format(s): PDF | BibTeX Citation

Version: 20210118:082345 (All versions of this report)

Short URL: ia.cr/2021/059


[ Cryptology ePrint archive ]