Paper 2019/1093

Quantum Random Oracle Model with Auxiliary Input

Minki Hhan, Keita Xagawa, and Takashi Yamakawa


The random oracle model (ROM) is an idealized model where hash functions are modeled as random functions that are only accessible as oracles. Although the ROM has been used for proving many cryptographic schemes, it has (at least) two problems. First, the ROM does not capture quantum adversaries. Second, it does not capture non-uniform adversaries that perform preprocessings. To deal with these problems, Boneh et al. (Asiacrypt'11) proposed using the quantum ROM (QROM) to argue post-quantum security, and Unruh (CRYPTO'07) proposed the ROM with auxiliary input (ROM-AI) to argue security against preprocessing attacks. However, to the best of our knowledge, no work has dealt with the above two problems simultaneously. In this paper, we consider a model that we call the QROM with (classical) auxiliary input (QROM-AI) that deals with the above two problems simultaneously and study security of cryptographic primitives in the model. That is, we give security bounds for one-way functions, pseudorandom generators, (post-quantum) pseudorandom functions, and (post-quantum) message authentication codes in the QROM-AI. We also study security bounds in the presence of quantum auxiliary inputs. In other words, we show a security bound for one-wayness of random permutations (instead of random functions) in the presence of quantum auxiliary inputs. This resolves an open problem posed by Nayebi et al. (QIC'15). In a context of complexity theory, this implies $ \mathsf{NP}\cap \mathsf{coNP} \not\subseteq \mathsf{BQP/qpoly}$ relative to a random permutation oracle, which also answers an open problem posed by Aaronson (ToC'05).

Note: This is the full version.

Available format(s)
Publication info
A minor revision of an IACR publication in ASIACRYPT 2019
Quantum Random Oracle ModelPost-quantum Cryptography
Contact author(s)
hhan_ @ snu ac kr
keita xagawa zv @ hco ntt co jp
takashi yamakawa ga @ hco ntt co jp
2019-10-22: revised
2019-09-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Minki Hhan and Keita Xagawa and Takashi Yamakawa},
      title = {Quantum Random Oracle Model with Auxiliary Input},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1093},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.