On the adaptive security of graph-based games

Klein K. 2021. On the adaptive security of graph-based games. Institute of Science and Technology Austria.

Download
OA thesis_pdfa.pdf 2.10 MB [Published Version]

Thesis | PhD | Published | English

Corresponding author has ISTA affiliation

Series Title
ISTA Thesis
Abstract
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
2021-09-23
Publisher
Institute of Science and Technology Austria
Acknowledgement
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).
Page
276
ISSN
IST-REx-ID

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. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:10035
Klein, Karen. “On the Adaptive Security of Graph-Based Games.” Institute of Science and Technology Austria, 2021. https://doi.org/10.15479/at:ista:10035.
K. Klein, “On the adaptive security of graph-based games,” Institute of Science and Technology Austria, 2021.
Klein K. 2021. On the adaptive security of graph-based games. Institute of Science and Technology Austria.
Klein, Karen. On the Adaptive Security of Graph-Based Games. Institute of Science and Technology 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
2021-10-04
MD5 Checksum
73a44345c683e81f3e765efbf86fdcc5

Source File
File Name
Access Level
Restricted Closed Access
Date Uploaded
2021-10-05
MD5 Checksum
7b80df30a0e686c3ef6a56d4e1c59e29

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar