Paper 2023/875

The Power of Undirected Rewindings for Adaptive Security

Dennis Hofheinz, ETH Zurich
Julia Kastner, ETH Zurich
Karen Klein, ETH Zurich
Abstract

Existing proofs of adaptive security (e.g., in settings in which decryption keys are adaptively revealed) often rely on guessing arguments. Such guessing arguments can be simple (and, e.g., just involve guessing which keys are revealed), or more complex "partitioning'' arguments. Since guessing directly and negatively impacts the loss of the corresponding security reduction, this leads to black-box lower bounds for a number of cryptographic scenarios that involve adaptive security. In this work, we provide an alternative to such guessing arguments: instead of guessing in a security reduction which adaptive choices an adversary A makes, we rewind A many times until we can successfully embed a given computational challenge. The main benefit of using rewindings is that these rewindings can be arranged sequentially, and the corresponding reduction loss only accumulates additively (instead of multiplicatively, as with guessing). The main technical challenge is to show that A's success is not negatively affected after (potentially many) rewindings. To this end, we develop a machinery for "undirected'' rewindings that preserve A's success across (potentially many) rewindings. We use this strategy to show - security of the "Logical Key Hierarchy'' protocol underlying the popular TreeKEM key management protocol, and - security of the Goldreich-Goldwasser-Micali (GGM) pseudorandom function (PRF) as a prefix-constrained PRF. In both cases, we provide the first polynomial reductions to standard assumptions (i.e., to IND-CPA and PRG security, respectively), and in case of the GGM PRF, we also circumvent an existing lower bound.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2023
Keywords
Adaptive SecurityRewindingForking Lemmaconstrained PRFmulticast encryption
Contact author(s)
hofheinz @ inf ethz ch
julia kastner @ inf ethz ch
karen klein @ inf ethz ch
History
2023-09-06: revised
2023-06-08: received
See all versions
Short URL
https://ia.cr/2023/875
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/875,
      author = {Dennis Hofheinz and Julia Kastner and Karen Klein},
      title = {The Power of Undirected Rewindings for Adaptive Security},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/875},
      year = {2023},
      url = {https://eprint.iacr.org/2023/875}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.