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:2609.32603

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

Boyang Chen, Tianren Liu, Luojian Wei

quant-phcs.CRSubmitted Sep 26, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

Abstract

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$.

AI Summary

One-time memory (OTM) lets a receiver recover either of two encoded messages while learning nothing beyond one choice. The paper asks whether simulation-secure OTM can be constructed without restricting quantum circuit depth or storage. It works in the classically accessible random-oracle model (CAROM): adversaries may perform arbitrary quantum computation but can query the oracle only on classical inputs. The construction uses independently sampled BB84 words, oracle-generated tags that identify correctly measured words, and message masks formed from oracle outputs indexed by the words and the full basis pattern. For two $\lambda$-bit messages, $n$ words of length $\ell$ require $n\ell$ qubits and $(n+2)\lambda$ classical bits. Correctness error is at most $n2^{-\lambda}$. Against an adversary making at most $q$ classical oracle queries, the simulation advantage is bounded by $2^{1-n}+(n+1)(\tfrac12+\tfrac{q+1}{2^{\ell/2+1}})^n$. If $q\leq 2^{\ell/2-1}-1$, this becomes at most $(n+3)(3/4)^n$. The proof reduces single-word recovery with oracle queries to oracle-free list recovery, bounds the latter using overlap between computational and Hadamard bases, and applies perfect parallel repetition to obtain a multiword bound. A simulator programs mask responses when the first message branch is completed; failure requires completion of both branches. Security depends on classical-only oracle access, not merely a conventional computational assumption. Instantiation with a public hash function is discussed heuristically rather than proved. The construction removes depth and storage restrictions but retains this oracle-access restriction.

Little sign of AI-generated textAI use disclosedStrong assumptionsOverclaims
We used OpenAI Codex to assist with drafting and editing portions of the introduction and technical overview, as well as with formatting checks.

Error found: Token.Gen supplies the single basis bit θ_i to a mask oracle requiring the full basis pattern θ; using θ instead makes generation consistent with evaluation and the security proof. The proof of the true Projector sum bound contains an invalid equality and a reversed inequality, so that preliminary proof needs replacement.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Towards Simple and Useful One-Time Programs in the Quantum Random Oracle Model

Lev Stambler

We construct simulation-secure one-time memories (OTM) in the random oracle model, and present a plausible argument for their security against quantum adversaries with bounded and adaptive depth. Our contributions include: (1) A simple scheme where we use only single-qubit Wiesner states and conjunction obfuscation (constructible from LPN): no complex entanglement or quantum cryptography is required. (2) A new POVM bound where e prove that any measurement achieving $(1 - ε)$ success on one basis has conjugate-basis guessing probability at most $\frac{1}{2m} + O(ε^\frac{1}{4})$. (3) Simultation-secure OTMs in the quantum random oracle model where an adversary can only query the random oracle classically. (4) Adaptive depth security where, via an informal application of a lifting theorem from Arora et al., we conjecture security against adversaries with polynomial quantum circuit depth between random oracle queries. Security against adaptive, depth-bounded, quantum adversaries captures many realistic attacks on OTMs built from single-qubit states; our work thus paves the way for practical and truly secure one-time programs. Moreover, depth bounded adaptive adversarial models may allow for encoding one-time memories into error corrected memory states, opening the door to implementations of one-time programs which persist for long periods of time.

quant-pharXiv:2601.13258•Jan 20, 2026•0 citations

Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More

Qipeng Liu

With the power of quantum information, we can achieve exciting and classically impossible cryptographic primitives. However, almost all quantum cryptography faces extreme difficulties with the near-term intermediate-scale quantum technology (NISQ technology); namely, the short lifespan of quantum states and limited sequential computation. At the same time, considering only limited quantum adversaries may still enable us to achieve never-before-possible tasks. In this work, we consider quantum cryptographic primitives against limited quantum adversaries - depth-bounded adversaries. We introduce a model for (depth-bounded) NISQ computers, which are classical circuits interleaved with shallow quantum circuits. Then, we show one-time memory can be achieved against any depth-bounded quantum adversaries introduced in the work, with their depth being any pre-fixed polynomial. Therefore we obtain applications like one-time programs and one-time proofs. Finally, we show our one-time memory has correctness even against constant-rate errors.

Leibniz international proceedings in informatics•Jan 1, 2023•2 citations

Practical Quantum Public Key Encryption from One-way Functions

Kyohei Sudo, Keisuke Fujii, Keisuke Hara +3 more

We construct a quantum public key encryption scheme from oneway functions in the random oracle model. While our construction only has indistinguishability against restricted adversaries, who perform individual attacks and can only make classical queries to the random oracle, it possesses two practical advantages that were not achieved in previous works. First, legitimate participants can discard noisy quantum public keys. Second, the scheme only requires products of single-qubit states, and it does not require quantum computing or quantum memory for legitimate participants. Although the security does not hold against adversaries capable of large-scale quantum computation, we believe that our protocol is well-suited for the near-term stage of the quantum era.

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 6, 2025•0 citations

Protecting Quantum Computers against Untrusted Users

Shiv Akshar Yadavalli, Joel Rajakumar, Alexander Schuckert +1 more

Publicly accessible fault-tolerant quantum computers must preserve scientific utility while limiting cryptanalytic power. We propose the restricted model of computation, 1/2BQP_1: a quantum server provides random computational-basis inputs, revealed only after execution, and one designated output bit. This interface permits arbitrary circuits and system sizes. We conjecture that a classical client making polynomially many adaptive requests cannot efficiently factor RSA moduli. The model subsumes the well-known one-clean-qubit model DQC1, retaining its applications to infinite-temperature multi-time correlations, out-of-time-order correlators, and suitably normalized partition functions. We propose a candidate for separating 1/2BQP_1 from DQC1 based on testing classical predictions of quantum spin dynamics. We argue security in two steps. First, we show that one-bit readout makes the quantum stages of standard factoring algorithms classically simulable, even when their preparation and postprocessing are redesigned within a broad family around a single arithmetic-oracle call. This covers the quantum stages of Shor, Ekera-Hastad, Kitaev, and Regev factoring constructions. Second, we examine the workaround of coherently implementing rational reconstruction to release a factor bit. Random inputs obstruct this straightforward attack: known techniques accommodate logarithmic-depth classical circuits, but rational reconstruction has resisted such parallelization for decades. Therefore, we show that security of our protocol is built on not only classical hardness for factoring, but also conjectured circuit lowerbounds for rational reconstruction.

quant-pharXiv:2610.06812•Oct 6, 2026•2 citations

Towards Quantum One-Time Memories from Stateless Hardware

Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou

A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless ( i.e. , reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver making at most 0.114 n adaptive queries to the token (for n the key size), in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also give two impossibility results showing certain assumptions in our scheme cannot be relaxed.

arXiv:1810.05226•Quantum•Apr 8, 2021•9 citations

The Hardness of Learning Quantum Circuits and Its Cryptographic Applications

Bill Fefferman, Soumik Ghosh, Makrand Sinha +1 more

We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles. Our random circuit-based constructions provide concrete instantiations of quantum cryptographic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to NISQ-friendly quantum cryptography. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against noiseless quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting.

arXiv:2504.15343•Leibniz international proceedings in informatics•Apr 21, 2025•13 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.
One-time memory (OTM) lets a receiver recover either of two encoded messages while learning nothing beyond one choice. The paper asks whether simulation-secure OTM can be constructed without restricting quantum circuit depth or storage. It works in the classically accessible random-oracle model (CAROM): adversaries may perform arbitrary quantum computation but can query the oracle only on classical inputs.
The construction uses independently sampled BB84 words, oracle-generated tags that identify correctly measured words, and message masks formed from oracle outputs indexed by the words and the full basis pattern. For two λ\lambdaλ-bit messages, nnn words of length ℓ\ellℓ require nℓn\ellnℓ qubits and (n+2)λ(n+2)\lambda(n+2)λ classical bits. Correctness error is at most n2−λn2^{-\lambda}n2−λ. Against an adversary making at most qqq classical oracle queries, the simulation advantage is bounded by 21−n+(n+1)(12+q+12ℓ/2+1)n2^{1-n}+(n+1)(\tfrac12+\tfrac{q+1}{2^{\ell/2+1}})^n21−n+(n+1)(21​+2ℓ/2+1q+1​)n. If q≤2ℓ/2−1−1q\leq 2^{\ell/2-1}-1q≤2ℓ/2−1−1, this becomes at most (n+3)(3/4)n(n+3)(3/4)^n(n+3)(3/4)n.
The proof reduces single-word recovery with oracle queries to oracle-free list recovery, bounds the latter using overlap between computational and Hadamard bases, and applies perfect parallel repetition to obtain a multiword bound. A simulator programs mask responses when the first message branch is completed; failure requires completion of both branches.
Security depends on classical-only oracle access, not merely a conventional computational assumption. Instantiation with a public hash function is discussed heuristically rather than proved. The construction removes depth and storage restrictions but retains this oracle-access restriction.
We construct simulation-secure one-time memories (OTM) in the random oracle model, and present a plausible argument for their security against quantum adversaries with bounded and adaptive depth. Our contributions include: (1) A simple scheme where we use only single-qubit Wiesner states and conjunction obfuscation (constructible from LPN): no complex entanglement or quantum cryptography is required. (2) A new POVM bound where e prove that any measurement achieving (1−ε)(1 - ε)(1−ε) success on one basis has conjugate-basis guessing probability at most 12m+O(ε14)\frac{1}{2m} + O(ε^\frac{1}{4})2m1​+O(ε41​). (3) Simultation-secure OTMs in the quantum random oracle model where an adversary can only query the random oracle classically. (4) Adaptive depth security where, via an informal application of a lifting theorem from Arora et al., we conjecture security against adversaries with polynomial quantum circuit depth between random oracle queries. Security against adaptive, depth-bounded, quantum adversaries captures many realistic attacks on OTMs built from single-qubit states; our work thus paves the way for practical and truly secure one-time programs. Moreover, depth bounded adaptive adversarial models may allow for encoding one-time memories into error corrected memory states, opening the door to implementations of one-time programs which persist for long periods of time.
With the power of quantum information, we can achieve exciting and classically impossible cryptographic primitives. However, almost all quantum cryptography faces extreme difficulties with the near-term intermediate-scale quantum technology (NISQ technology); namely, the short lifespan of quantum states and limited sequential computation. At the same time, considering only limited quantum adversaries may still enable us to achieve never-before-possible tasks. In this work, we consider quantum cryptographic primitives against limited quantum adversaries - depth-bounded adversaries. We introduce a model for (depth-bounded) NISQ computers, which are classical circuits interleaved with shallow quantum circuits. Then, we show one-time memory can be achieved against any depth-bounded quantum adversaries introduced in the work, with their depth being any pre-fixed polynomial. Therefore we obtain applications like one-time programs and one-time proofs. Finally, we show our one-time memory has correctness even against constant-rate errors.
We construct a quantum public key encryption scheme from oneway functions in the random oracle model. While our construction only has indistinguishability against restricted adversaries, who perform individual attacks and can only make classical queries to the random oracle, it possesses two practical advantages that were not achieved in previous works. First, legitimate participants can discard noisy quantum public keys. Second, the scheme only requires products of single-qubit states, and it does not require quantum computing or quantum memory for legitimate participants. Although the security does not hold against adversaries capable of large-scale quantum computation, we believe that our protocol is well-suited for the near-term stage of the quantum era.
Publicly accessible fault-tolerant quantum computers must preserve scientific utility while limiting cryptanalytic power. We propose the restricted model of computation, 1/2BQP_1: a quantum server provides random computational-basis inputs, revealed only after execution, and one designated output bit. This interface permits arbitrary circuits and system sizes. We conjecture that a classical client making polynomially many adaptive requests cannot efficiently factor RSA moduli. The model subsumes the well-known one-clean-qubit model DQC1, retaining its applications to infinite-temperature multi-time correlations, out-of-time-order correlators, and suitably normalized partition functions. We propose a candidate for separating 1/2BQP_1 from DQC1 based on testing classical predictions of quantum spin dynamics. We argue security in two steps. First, we show that one-bit readout makes the quantum stages of standard factoring algorithms classically simulable, even when their preparation and postprocessing are redesigned within a broad family around a single arithmetic-oracle call. This covers the quantum stages of Shor, Ekera-Hastad, Kitaev, and Regev factoring constructions. Second, we examine the workaround of coherently implementing rational reconstruction to release a factor bit. Random inputs obstruct this straightforward attack: known techniques accommodate logarithmic-depth classical circuits, but rational reconstruction has resisted such parallelization for decades. Therefore, we show that security of our protocol is built on not only classical hardness for factoring, but also conjectured circuit lowerbounds for rational reconstruction.
A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless ( i.e. , reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver making at most 0.114 n adaptive queries to the token (for n the key size), in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also give two impossibility results showing certain assumptions in our scheme cannot be relaxed.
We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles. Our random circuit-based constructions provide concrete instantiations of quantum cryptographic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to NISQ-friendly quantum cryptography. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against noiseless quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting.