Paper 2017/515

Be Adaptive, Avoid Overcommitting

Zahra Jafargholi, Chethan Kamath, Karen Klein, Ilan Komargodski, Krzysztof Pietrzak, and Daniel Wichs


For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC '07 and Fuchsbauer et al., CRYPTO '15), constrained PRFs (Fuchsbauer et al., ASIACRYPT '14), and Yao garbled circuits (Jafargholi and Wichs, TCC '16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to $n$-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary's advantage by a factor of up to $2^n$. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of $m \ll n$ bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire $n$-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary's advantage by a factor of only $2^m \ll 2^n$. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2017
adaptive securitysecret sharinggarblingYaogeneralized selective decryptionGSDpebbling strategies
Contact author(s)
ilan komargodski @ weizmann ac il
2017-09-01: last of 2 revisions
2017-06-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zahra Jafargholi and Chethan Kamath and Karen Klein and Ilan Komargodski and Krzysztof Pietrzak and Daniel Wichs},
      title = {Be Adaptive, Avoid Overcommitting},
      howpublished = {Cryptology ePrint Archive, Paper 2017/515},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.