Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1008.0931 · Lecture notes in computer science

Random Oracles in a Quantum World

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

Published Jan 1, 2011• 510 citations
arXivHTMLPDF
DOI
10.1007/978-3-642-25385-0_3

Related papers

Classical vs Quantum Random Oracles

Takashi Yamakawa, Mark Zhandry

Lecture notes in computer science•Jan 1, 2021•50 citations

Succinct Arguments in the Quantum Random Oracle Model

Alessandro Chiesa, Peter Manohar, Nicholas Spooner

Lecture notes in computer science•Jan 1, 2019•71 citations

Formations for the Quantum Random Oracle.

Aaram Yun

•Jan 1, 2021•0 citations

Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model

Boyang Chen, Tianren Liu, Luojian Wei

Quantum information enables many cryptographic primitives that are impossible in the classical world. A line of works has developed cryptographic protocol under the assumption that quantum adversaries are restricted to noisy intermediate-scale quantum (NISQ) computing power, enabling strong one-time functionalities. But the advent of early fault-tolerant quantum computers eras will allow deeper logical quantum circuits, calling into questions the applicability of these NISQ-based assumptions. In this work, we adapt the classically accessible random oracle model (CAROM) as in [BDF+11] and [AK22], in which adversaries are only allowed to classically query the random oracle. The restriction is well motivated for NISQ quantum adversaries and may remain plausible in the presence of early fault-tolerant quantum computers. Then, we show that an efficient simulation-secure one-time memory (OTM) is possible under CAROM. Our protocol uses only BB84 states and has quadratic communication: for a $λ$-bit message and integer-valued parameters $n=n(λ)$ and $\ell=\ell(λ)$, the construction uses $n\ell$ qubits and $(n+2)λ$ classical bits, and for any quantum adversary with at most $2^{\ell/2-1}-1$ classical queries to the random oracle, its simulation advantage is at most $(n+3)\left(\frac{3}{4}\right)^n.$ Hence exponentially small simulation advantage in $n$.

quant-pharXiv:2609.32603•Sep 29, 2026•0 citations

A Note on Separating Classical and Quantum Random Oracles.

Takashi Yamakawa, Mark Zhandry

•Jan 1, 2020•3 citations

Quantum Biased Oracles

亮周 河内, Akinori Kawachi

•Jan 1, 2005•0 citations
Quantum information enables many cryptographic primitives that are impossible in the classical world. A line of works has developed cryptographic protocol under the assumption that quantum adversaries are restricted to noisy intermediate-scale quantum (NISQ) computing power, enabling strong one-time functionalities. But the advent of early fault-tolerant quantum computers eras will allow deeper logical quantum circuits, calling into questions the applicability of these NISQ-based assumptions. In this work, we adapt the classically accessible random oracle model (CAROM) as in [BDF+11] and [AK22], in which adversaries are only allowed to classically query the random oracle. The restriction is well motivated for NISQ quantum adversaries and may remain plausible in the presence of early fault-tolerant quantum computers. Then, we show that an efficient simulation-secure one-time memory (OTM) is possible under CAROM. Our protocol uses only BB84 states and has quadratic communication: for a λλλ-bit message and integer-valued parameters n=n(λ)n=n(λ)n=n(λ) and ℓ=ℓ(λ)\ell=\ell(λ)ℓ=ℓ(λ), the construction uses nℓn\ellnℓ qubits and (n+2)λ(n+2)λ(n+2)λ classical bits, and for any quantum adversary with at most 2ℓ/2−1−12^{\ell/2-1}-12ℓ/2−1−1 classical queries to the random oracle, its simulation advantage is at most (n+3)(34)n.(n+3)\left(\frac{3}{4}\right)^n.(n+3)(43​)n. Hence exponentially small simulation advantage in nnn.