Welcome to the resource topic for 2019/1101
Title:
On the (Quantum) Random Oracle Methodology: New Separations and More
Authors: Jiang Zhang, Yu Yu, Dengguo Feng, Shuqin Fan, 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.
ePrint: https://eprint.iacr.org/2019/1101
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .