Random oracles in a quantum world

Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

105 Scopus citations

Abstract

The interest in post-quantum cryptography - classical systems that remain secure in the presence of a quantum adversary - has generated elegant proposals for new cryptosystems. Some of these systems are set in the random oracle model and are proven secure relative to adversaries that have classical access to the random oracle. We argue that to prove post-quantum security one needs to prove security in the quantum-accessible random oracle model where the adversary can query the random oracle with quantum state. We begin by separating the classical and quantum-accessible random oracle models by presenting a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when the adversary can make quantum oracle queries. We then set out to develop generic conditions under which a classical random oracle proof implies security in the quantum-accessible random oracle model. We introduce the concept of a history-free reduction which is a category of classical random oracle reductions that basically determine oracle answers independently of the history of previous queries, and we prove that such reductions imply security in the quantum model. We then show that certain post-quantum proposals, including ones based on lattices, can be proven secure using history-free reductions and are therefore postquantum secure. We conclude with a rich set of open problems in this area.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology, ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Pages41-69
Number of pages29
DOIs
StatePublished - Dec 12 2011
Externally publishedYes
Event17th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2011 - Seoul, Korea, Republic of
Duration: Dec 4 2011Dec 8 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7073 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2011
CountryKorea, Republic of
CitySeoul
Period12/4/1112/8/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Encryption
  • Quantum
  • Random Oracle
  • Signatures

Fingerprint Dive into the research topics of 'Random oracles in a quantum world'. Together they form a unique fingerprint.

  • Cite this

    Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., & Zhandry, M. (2011). Random oracles in a quantum world. In Advances in Cryptology, ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 41-69). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7073 LNCS). https://doi.org/10.1007/978-3-642-25385-0_3