Cryptology ePrint Archive: Report 2019/1093

Quantum Random Oracle Model with Auxiliary Input

Minki Hhan and Keita Xagawa and Takashi Yamakawa

Abstract: 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).

Category / Keywords: foundations / Quantum Random Oracle Model, Post-quantum Cryptography

Original Publication (with minor differences): IACR-ASIACRYPT-2019

Date: received 24 Sep 2019, last revised 21 Oct 2019

Contact author: hhan_ at snu ac kr,keita xagawa zv@hco ntt co jp,takashi yamakawa ga@hco ntt co jp

Available format(s): PDF | BibTeX Citation

Note: This is the full version.

Version: 20191022:010414 (All versions of this report)

Short URL: ia.cr/2019/1093


[ Cryptology ePrint archive ]