Crypto Reading Group on quantum computing | Jonas Janneck & Camryn Steckel, The Quantum-Accessible Random Oracle Model

Abstract: A lot of classical constructions are proven secure the random oracle model. With quantum adversaries, it is necessary to consider a quantum-accessible model allowing the adversary to query the oracle with quantum states. In this talk, we define such an oracle and show its implications on classical security proofs. We will present an example separating the classical and quantum-accessible random oracle models using a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when they can make quantum oracle queries. We further define history-free reductions and show that there is a general lifting result allowing to argue security in the quantum random oracle model when there is a reduction in the classical setting. As an example for this technique we will show how to prove the security of signatures following the Full Domain Hash paradigm.