Classical vs Quantum Random Oracles
https://www.cs.princeton.edu/~mzhandry/docs/papers/QROMsep.pdf https://eprint.iacr.org/2020/1270.pdf
Background
Boneh et al. observe that many proof techniques in the ROM cannot be directly translated into one in the QROM, even if the other building blocks of the system are quantum-resistant. Therefore, new proof techniques are needed in order to justify the post-quantum security of random oracle model systems.
Fortunately, recent advances of proof techniques have clarified that most important constructions that are originally proven secure in the ROM are also secure in the QROM. These include OAEP [TU16], Fujisaki-Okamoto transform [TU16, JZC+18, Zha19], Fiat-Shamir transform [LZ19b, DFMS19, DFM20], Full-Domain Hash (FDH) signatures [Zha12], Gentry-Peikert-Vaikuntanathan (GPV) IBE [Zha12, KYY18] etc.
Given this situation, it is natural to ask if there may be a general theorem lifting any classical ROM proof into a proof in the QROM, provided that the other building blocks of the system remain quantum resistant.
There are several known lifting theorems that ensure that certain types of security reductions in the ROM also work in the QROM [BDF+11, Son14, ZYF+19, KS20]. How- ever, there is no known general lifting theorem that works regardless of form of security proofs in the ROM.
Such a general lifting theorem certainly seems like a challenging task. Nevertheless, demonstrating a separation — that is, a scheme using quantum-resistant building blocks that is secure in the ROM but insecure in the QROM — has also been elusive. Intuitively, the reason is that natural problems on random oracles (such as pre-image search, collision finding, etc) only have polynomial gaps between classical and quantum query complexity.
We are aware of two works that consider the task of finding a separation. First, Boneh et al. [BDF+11] gave an example of an identification protocol that is secure in the ROM but insecure in the QROM, but is specific to a certain nonstandard timing model. Concretely, the protocol leverages the polynomial gap in collision finding to allow an attacker with quantum oracle access to break the system somewhat faster than any classical-access algorithm. The verifier then rejects if the prover cannot respond to its challenges fast enough, thereby blocking classical attacks while allowing the quantum attack to go through. This unfortunately requires a synchronous model where the verifier keeps track of the time between messages; such a model is non-standard.
Second, a recent work of Zhang et al. [ZYF+19] showed that quantum random oracle is differentiable from classical random oracle, which roughly means that it is impossible to simulate quantum random oracle using only classical queries to the same function. Their result rules out a natural approach one may take to give a lifting theorem, but it fails to actually give a scheme separating classical from quantum access to a random oracle.
In summary, there is no known classical cryptographic scheme (e.g., digital signatures or PKE) that can be proven secure in the ROM but insecure in the QROM. This leaves open the important question of whether or not a general lifting theorem for cryptographic schemes is possible.
Results
We give constructions of cryptographic schemes that separate the ROM and QROM, showing that a fully general lifting theorem is impossible. On the other hand, we also give lifting theorems from the ROM security to the QROM security for some constrained but still very general settings.
Separation of ROM and QROM
Proof of Quantum Access to a Random Oracle (PoQRO)
For showing separations between the ROM and QROM, we first introduce a primitive which we call *a proof of quantum access to random oracle *(PoQRO). Roughly speaking, a PoQRO is a protocol where a quantum prover proves his ability to quantumly access to a random oracle to a classical verifier who is only given classical access to the random oracle. We obtain a PoQRO under the assumed quantum hardness of the learning with errors (LWE) problem [Reg09] (which we call the QLWE assumption in the following). The construction is non-interacitve in the sense that after a verifier generates a pair of a public and secret keys and publishes the public key, a prover can generate a proof without any interaction. However, the proof is not publicly verifiable since the verification relies on the secret key.
We also study the possibility of publicly verifiable PoQRO. We give a construction of a publicly verifiable PoQRO relative to a classical oracle using the technique developed in the recent work by Amos et al. [AGKZ20]. Similarly to [AGKZ20], we can heuristically instantiate the protocol in the standard model by using candidate constructions of post-quantum obfuscation [Agr19, AP20, BDGM20, WW20, GP20].
A (non-interactive) proof of quantum access to a random oracle (PoQRO) consists of algorithms (PoQRO.Setup, PoQRO.Prove, PoQRO.Verify).
PoQRO.Setup This is a classical algorithm that takes the security parameter as input and outputs a public key and a secret key .
PoQRO.Prove This is a quantum oracle-aided algorithm that takes a public key as input and given a quantum access to a random oracle , and outputs a proof .
PoQRO.Verify This is a classical algorithm that takes a secret key and a proof as input and given a classical access to a random oracle , and outputs indicating acceptance or indicating rejection.
Correctness.
Separation of ROM and QROM
A PoQRO itself is already an example of cryptographic task that can be done in the QROM but cannot be done in the ROM. By embedding a PoQRO into digital signatures and PKE, we obtain the following results:
A digital signature scheme that is EUF-CMA secure in the ROM but completely broken by 1 signing query in the QROM
A PKE scheme that is IND-CCA secureinthe ROM but completely broken by 1 decryption query in the QROM.
Both these results rely on the QLWE assumption.
Moreover, by embedding a publicly verifiable PoQRO into them, we can show the existence of a classical oracle relative to which there exist the following schemes:
A digital signature scheme that is EUF-CMA secure in the ROM but not even EUF-NMA secure in the QROM, and A PKE scheme that is IND-CCA secure in the ROM but not even IND-CPA secure in the QROM.
These results can be understood as an evidence that a generic lifting theorem is unlikely to exist even for the weak security notions of EUF-NMA security of digital signatures and IND-CPA security of PKE. Specifically, the above results imply that there do not exist a relativizing lifting theorem for them that works relative to any classical oracle.
Lifting Theorems
We now turn to our positive results, giving lifting theorems for certain class of schemes and security notions.
Lifting Theorem for Search-Type Games
For any search-type game where a challenger makes constant number of queries to the random oracle, if the game is hard in the ROM, then that is also hard in the QROM.
Lifting Theorem for EUF-CMA Security of Digital Signatures
Suppose that a digital signature scheme satisfies the following:
EUF-NMA secure in the ROM, The key generation algorithm does not make random oracle queries and the verification algorithm makes O(1) random oracle queries, Random oracle queries made by the signing and verification algorithms reveal the corresponding message, and Signatures are simulatable without the signing key if one is allowed to non-adaptively program the random oracle. Then the scheme is EUF-CMA secure in the QROM.
Application to Quantum Query Complexity
We obtain a general theorem about query complexity. We consider a class of oracle problems, where the adversary’s goal is to find distinct inputs to such that the corresponding outputs satisfy some relation. Our theorem can be seen as upper bounding the success probability of a -query adversary in terms of the probability of an adversary that makes no queries at all.