Paper 2022/773

Adaptive versus Static Multi-oracle Algorithms, and Quantum Security of a Split-key PRF

Jelle Don, Centrum Wiskunde & Informatica
Serge Fehr, Centrum Wiskunde & Informatica, Leiden University
Yu-Hsuan Huang, Centrum Wiskunde & Informatica
Abstract

In the first part of the paper, we show a generic compiler that transforms any oracle algorithm that can query multiple oracles adaptively, i.e., can decide on which oracle to query at what point dependent on previous oracle responses, into a static algorithm that fixes these choices at the beginning of the execution. Compared to naive ways of achieving this, our compiler controls the blow-up in query complexity for each oracle individually, and causes a very mild blow-up only. In the second part of the paper, we use our compiler to show the security of the very efficient hash-based split-key PRF proposed by Giacon, Heuer and Poettering (PKC 2018), in the quantum random-oracle model. Using a split-key PRF as the key-derivation function gives rise to a secure KEM combiner. Thus, our result shows that the hash-based construction of Giacon et al. can be safely used in the context of quantum attacks, for instance to combine a well-established but only classically-secure KEM with a candidate KEM that is believed to be quantum-secure. Our security proof for the split-key PRF crucially relies on our adaptive-to-static compiler, but we expect our compiler to be useful beyond this particular application. Indeed, we discuss a couple of other, known results from the literature that would have profitted from our compiler, in that these works had to go though serious complications in order to deal with adaptivity.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2022
Keywords
quantum random oracle QROM split-key PRF KEM combiner quantum security multi-oracle
Contact author(s)
jelle don @ cwi nl
serge fehr @ cwi nl
yhh @ cwi nl
History
2022-09-13: revised
2022-06-15: received
See all versions
Short URL
https://ia.cr/2022/773
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/773,
      author = {Jelle Don and Serge Fehr and Yu-Hsuan Huang},
      title = {Adaptive versus Static Multi-oracle Algorithms, and Quantum Security of a Split-key PRF},
      howpublished = {Cryptology ePrint Archive, Paper 2022/773},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/773}},
      url = {https://eprint.iacr.org/2022/773}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.