International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Random Oracles in a Quantum World

Özgür Dagdelen
Marc Fischlin
Anja Lehmann
Christian Schaffner
Search ePrint
Search Google
Abstract: Once quantum computers reach maturity most of today’s traditional cryptographic schemes based on RSA or discrete logarithms become vulnerable to quantum-based attacks. Hence, schemes which are more likely to resist quantum attacks like lattice-based systems or code-based primitives have recently gained significant attention. Interestingly, a vast number of such schemes also deploy random oracles, which have mainly be analyzed in the classical setting. Here we revisit the random oracle model in cryptography in light of quantum attackers. We show that there are protocols using quantum-immune primitives and random oracles, such that the protocols are secure in the classical world, but insecure if a quantum attacker can access the random oracle via quantum states. We discuss that most of the proof techniques related to the random oracle model in the classical case cannot be transferred immediately to the quantum case. Yet, we show that “quantum random oracles” can nonetheless be used to show for example that the basic Bellare-Rogaway encryption scheme is quantum-immune against plaintext attacks (assuming quantum-immune primitives).
  title={Random Oracles in a Quantum World},
  booktitle={IACR Eprint archive},
  keywords={foundations / random oracle model, quantum adversaries},
  note={ 14827 received 2 Aug 2010, last revised 6 Aug 2010},
  author={Özgür Dagdelen and Marc Fischlin and Anja Lehmann and Christian Schaffner},