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

Motivated by the fact that in the quantum random oracle model (QROM) introduced by Boneh et al. (Asiacrypt 2011), honest parties (i.e., the cryptosystems) typically use the random oracle (RO) in a classical way while the adversary can send quantum queries to the RO, we first reformalize the classical RO (CRO) and the quantum RO (QRO) by adapting the indifferentiability framework of Maurer et al. (TCC 2004), and equipping a RO with a private and a (quantum) public interface for the honest parties and the adversary, respectively. Then, we give a new separation between the QROM and the ROM by showing that QRO is differentiable from CRO, which is technically different from Boneh et al.'s separation and is based on a new information versus disturbance lemma (that may be of independent interest). 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.