Paper 2020/1270

Classical vs Quantum Random Oracles

Takashi Yamakawa and Mark Zhandry

Abstract

In this paper, we study relationship between security of cryptographic schemes in the random oracle model (ROM) and quantum random oracle model (QROM). First, we introduce a notion of a proof of quantum access to a random oracle (PoQRO), which is a protocol to prove the capability to quantumly access a random oracle to a classical verifier. We observe that a proof of quantumness recently proposed by Brakerski et al. (TQC '20) can be seen as a PoQRO. We also give a construction of a publicly verifiable PoQRO relative to a classical oracle. Based on them, we construct digital signature and public key encryption schemes that are secure in the ROM but insecure in the QROM. In particular, we obtain the first examples of natural cryptographic schemes that separate the ROM and QROM under a standard cryptographic assumption. On the other hand, we give lifting theorems from security in the ROM to that in the QROM for certain types of cryptographic schemes and security notions. For example, our lifting theorems are applicable to Fiat-Shamir non-interactive arguments, Fiat-Shamir signatures, and Full-Domain-Hash signatures etc. We also discuss applications of our lifting theorems to quantum query complexity.

Note: This is a major update version of https://eprint.iacr.org/2020/787 with many new results. Fixed minor typos etc. (03/05/2021)

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Keywords
random oracle modelquantum random oracle modelpost-quantum security
Contact author(s)
takashi yamakawa obf @ gmail com
History
2021-03-05: revised
2020-10-14: received
See all versions
Short URL
https://ia.cr/2020/1270
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1270,
      author = {Takashi Yamakawa and Mark Zhandry},
      title = {Classical vs Quantum Random Oracles},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1270},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1270}},
      url = {https://eprint.iacr.org/2020/1270}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.