Random Oracles in a Quantum World

By Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, Mark Zhandry. International Conference on the Theory and Application of Cryptology and Information Security, 2010

526 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/1d02b4a41f21e94d5530bcb2df72fbeea5d310e0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives (2017, methodology): “• We also show how to apply Unruh’s generic transform [83– 85] to obtain a non-interactive counterpart of ZKB++ that is secure in the quantum-accessible random oracle model (QROM; see [18]).”
How to Construct Quantum Random Functions (2012, methodology): “, n − 1} • Let P (i) : [2]n−i−1 → K2 be the oracle P (i)(x) = P (0x) • Write P (i) as (P (i) 0 , P (i) 1 ) where P (i) b : [2] n−i−1 → K are the left and right halfs of the output of P (i).”
Breaking Symmetric Cryptosystems Using Quantum Period Finding (2016, background): “tives. Very recently, this direction has started to draw attention, and interesting results have been obtained. New theoretical frameworks to take into account quantum adversaries have been developed [10,12,20,23,16,2]. Simon’s algorithm [44] is central in quantum algorithm theory. Historically, it ”
Making NTRU as Secure as Worst-Case Problems over Ideal Lattices (2011, background): “As pointed out in [6], one should be extremely cautious with the random oracle in a quantum setup.”
A Modular Analysis of the Fujisaki-Okamoto Transformation (2017, unknown): “Furthermore, quantum computers may execute all “oﬄine primitives” such as hash functions on arbitrary superpositions, which motivated the introduction of the quantum (accessible) random oracle model [11].”
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM (2017, background): “Concretely, in the quantum random oracle model [17] the adversary has access to a quantum random oracle (also called quantum accessible random oracle) that can be queried up to qH times on arbitrary quantum superpositions of input strings.”