Skip to main content

Classical vs Quantum Random Oracles

Author(s): Yamakawa, Takashi; Zhandry, Mark

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr15717n5d
Full metadata record
DC FieldValueLanguage
dc.contributor.authorYamakawa, Takashi-
dc.contributor.authorZhandry, Mark-
dc.date.accessioned2023-12-23T23:04:30Z-
dc.date.available2023-12-23T23:04:30Z-
dc.date.issued2021en_US
dc.identifier.citationYamakawa, Takashi, and Mark Zhandry. "Classical vs Quantum Random Oracles." In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 568-597. 2021. https://doi.org/10.1007/978-3-030-77886-6_20en_US
dc.identifier.urihttps://www.cs.princeton.edu/~mzhandry/docs/papers/YZ21.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr15717n5d-
dc.description.abstractIn 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.en_US
dc.format.extent568 - 597en_US
dc.language.isoen_USen_US
dc.relation.ispartofAnnual International Conference on the Theory and Applications of Cryptographic Techniquesen_US
dc.rightsAuthor's manuscripten_US
dc.titleClassical vs Quantum Random Oraclesen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1007/978-3-030-77886-6_20-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
ClassicQuantumRandomOracles.pdf616.41 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.