Cryptology ePrint Archive: Report 2020/787

A Note on Separating Classical and Quantum Random Oracles

Takashi Yamakawa and Mark Zhandry

Abstract: In this note, we observe that a proof of quantumness in the random oracle model recently proposed by Brakerski et al. can be seen as a proof of quantum access to a random oracle. Based on this observation, we give the first examples of natural cryptographic schemes that separate classical and quantum random oracle models. Specifically, we construct digital signature and public key encryption schemes that are secure in the classical random oracle model but insecure in the quantum random oracle model assuming the quantum hardness of learning with error problem.

Category / Keywords: foundations / random oracle, post-quantum security

Date: received 24 Jun 2020

Contact author: takashi yamakawa obf at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200627:185010 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]