Paper 2023/875

The Power of Undirected Rewindings for Adaptive Security

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

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.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2023
Adaptive SecurityRewindingForking Lemmaconstrained PRFmulticast encryption
Contact author(s)
hofheinz @ inf ethz ch
julia kastner @ inf ethz ch
karen klein @ inf ethz ch
2023-09-06: revised
2023-06-08: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.