Random Oracles in a Quantum World
arXiv:1008.0931 · doi:10.1007/978-3-642-25385-0_3
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 states. 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 post-quantum secure. We conclude with a rich set of open problems in this area.
38 pages, v2: many substantial changes and extensions, merged with a related paper by Boneh and Zhandry
References in corpus (2)
Cited by in corpus (39)
- Random Oracles in a Quantum World
- Breaking Symmetric Cryptosystems using Quantum Period Finding
- Quantum Cryptography Beyond Quantum Key Distribution
- Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model
- Quantum Physical Unclonable Functions: Possibilities and Impossibilities
- Quantum Relational Hoare Logic
- Quantum Money from Hidden Subspaces
- Semantic Security and Indistinguishability in the Quantum World
- Non-interactive classical verification of quantum computation
- Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication
- Computational Security of Quantum Encryption
- Uncloneable Quantum Encryption via Oracles
- Client-Server Identification Protocols with Quantum PUF
- Verifiable Quantum Advantage without Structure
- Quantum copy-protection of compute-and-compare programs in the quantum random oracle model
- Succinct Blind Quantum Computation Using a Random Oracle
- Quantum contract signing with entangled pairs
- Parallel Quantum Algorithm for Hamiltonian Simulation
- A Unified Framework For Quantum Unforgeability
- Delegating Quantum Computation in the Quantum Random Oracle Model
- New security notions and feasibility results for authentication of quantum data
- Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security
- Quantum Merkle Trees
- Online-Extractability in the Quantum Random-Oracle Model
- Classical Encryption and Authentication under Quantum Attacks
- Pseudorandom Unitaries in the Haar Random Oracle Model
- Tight adaptive reprogramming in the QROM
- A quantum related-key attack based on Bernstein-Vazirani algorithm
- Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries
- Improved Quantum Lifting by Coherent Measure-and-Reprogram
- How to Sign Quantum Messages
- Quantum-access security of the Winternitz one-time signature scheme
- Tight Quantum Time-Space Tradeoffs for Function Inversion
- Performance Analysis of TLS for Quantum Robust Cryptography on a Constrained Device
- A Note on Output Length of One-Way State Generators and EFIs
- Quantum security of hash functions and property-preservation of iterated hashing
- Quantum Indistinguishability for Public Key Encryption
- The Fiat-Shamir Transformation in a Quantum World
- Certified Everlasting Zero-Knowledge Proof for QMA