On the adaptive security of graph-based games

Klein K. 2021. On the adaptive security of graph-based games. IST Austria.

OA thesis_pdfa.pdf 2.10 MB

Thesis | Published | English
Series Title
IST Austria Thesis
Many security definitions come in two flavors: a stronger “adaptive” flavor, where the adversary can arbitrarily make various choices during the course of the attack, and a weaker “selective” flavor where the adversary must commit to some or all of their choices a-priori. For example, in the context of identity-based encryption, selective security requires the adversary to decide on the identity of the attacked party at the very beginning of the game whereas adaptive security allows the attacker to first see the master public key and some secret keys before making this choice. Often, it appears to be much easier to achieve selective security than it is to achieve adaptive security. A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption [Pan07][FJP15], constrained PRFs [FKPR14], and Yao’s garbled circuits [JW16]. 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 (published at Crypto ’17 [JKK+17a]) that connects all of these works and allows us to present them in a unified and simplified fashion. Having the framework in place, we show how to achieve adaptive security for proxy re-encryption schemes (published at PKC ’19 [FKKP19]) and provide the first adaptive security proofs for continuous group key agreement protocols (published at S&P ’21 [KPW+21]). Questioning optimality of our framework, we then show that currently used proof techniques cannot lead to significantly better security guarantees for "graph-building" games (published at TCC ’21 [KKPW21a]). These games cover generalized selective decryption, as well as the security of prominent constructions for constrained PRFs, continuous group key agreement, and proxy re-encryption. Finally, we revisit the adaptive security of Yao’s garbled circuits and extend the analysis of Jafargholi and Wichs in two directions: While they prove adaptive security only for a modified construction with increased online complexity, we provide the first positive results for the original construction by Yao (published at TCC ’21 [KKP21a]). On the negative side, we prove that the results of Jafargholi and Wichs are essentially optimal by showing that no black-box reduction can provide a significantly better security bound (published at Crypto ’21 [KKPW21c]).
Publishing Year
Date Published
I want to acknowledge the funding by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).

Cite this

Klein K. On the adaptive security of graph-based games. 2021. doi:10.15479/at:ista:10035
Klein, K. (2021). On the adaptive security of graph-based games. IST Austria. https://doi.org/10.15479/at:ista:10035
Klein, Karen. “On the Adaptive Security of Graph-Based Games.” IST Austria, 2021. https://doi.org/10.15479/at:ista:10035.
K. Klein, “On the adaptive security of graph-based games,” IST Austria, 2021.
Klein K. 2021. On the adaptive security of graph-based games. IST Austria.
Klein, Karen. On the Adaptive Security of Graph-Based Games. IST Austria, 2021, doi:10.15479/at:ista:10035.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
MD5 Checksum

Source File
File Name
Access Level
Restricted Closed Access
Date Uploaded
MD5 Checksum


Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar