Paper 2019/1101

On the (Quantum) Random Oracle Methodology: New Separations and More

Jiang Zhang and Yu Yu and Dengguo Feng and Shuqin Fan and Zhenfeng Zhang

Abstract

In this paper, we first give, to the best of our knowledge, the first exponential separation between the ROM and QROM. Technically, we will first present a simple and efficient quantum distinguisher $\cD_q$ which can recognize the QROM by making at most two quantum RO queries, and can only be cheated by an adversary making (sub-)exponential classical RO queries. This (sub-)exponential query gap allows us to remove the ``unit time'' and ``zero time'' assumptions that are crucially needed for previously known separation due to Boneh et al. (Asiacrypt 2011). The construction of our distinguisher relies on a new {\it information versus disturbance} lemma, which may be of independent interest. Moreover, we show that the quantum operations of $\cD_q$ can actually be delegated to any quantum algorithms in a way that can be efficiently verified by a classical verifier under the LWE assumption, which allows us to give a pure classical distinguisher $\cD_c$ that can efficiently distinguish an environment equipped with a RO from that with a QRO. By using $\cD_c$ as a black-box, we can transform schemes that are secure in the ROM but insecure in the QROM (under the LWE assumption). We further abstract a class of BB-reductions in the ROM under the notion of committed-programming reduction (CPRed) for which the simulation of the RO can be easily quantized to handle quantum queries (from the adversary in the QROM). We show that 1) some well-known schemes such as the FDH signature and the Boneh-Franklin identity-based encryption are provably secure under CPReds; and 2) a CPRed associated with an instance-extraction algorithm implies a reduction in the QROM, which subsumes several recent results such as the security of the FDH signature by Zhandry (Crypto 2012) and the KEM variants from the Fujisaki-Okamoto transform by Jiang et al. (Crypto 2018). We finally show that CPReds are incomparable to non-programming reductions (NPReds) and randomly-programming reductions (RPReds) formalized by Fischlin et al. (Asiacrypt 2010), which gives new insights into the abilities (e.g., observability and programmability) provided by the (Q)ROM, and the hardness of proving security in the QROM.