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

One-Time Programs in the QROM with Depth-Bounded Quantum Adversaries

Overview

This work addresses the construction of simulation-secure one-time memories (OTMs) in the quantum random oracle model (QROM), targeting adversaries with bounded and adaptive quantum circuit depth. The proposed approach is notable for using only single-qubit Wiesner states combined with conjunction obfuscation based on the Learning Parity with Noise (LPN) assumption, eschewing requirements for multi-qubit entanglement or advanced quantum cryptography. Central to the analysis is a new bound on the distinguishability achievable by positive operator-valued measures (POVMs) when attacking conjugate coding states, which underpins the security argument against both classical-query and depth-bounded quantum adversaries.

Technical Contributions

Simplicity of Construction

The scheme leverages tensor products of independent single-qubit Wiesner states to encode secrets, selecting, for each position, either the computational ($Z$) or Hadamard ($X$) basis at random. Message retrieval is tied to the ability to identify specific basis encodings, with retrieval of both messages requiring successful measurements in both bases—rendered infeasible by information-theoretic bounds. Unlike earlier schemes requiring advanced quantum features (e.g., entanglement, indistinguishability obfuscation), this construction remains conceptually simple and practically implementable with near-term hardware.

Novel POVM Bound for Multi-Qubit Conjugate Coding

A principal result is a sequential measurement bound: for $m$-qubit conjugate-coded states, any measurement (POVM) with success probability $1 - \epsilon$ of identifying the string in one basis yields an adversarial guessing probability in the conjugate basis of at most $2^{-m} + O(\epsilon^{1/4})$. This generalizes prior single-qubit security analyses to the multi-qubit regime and quantifies an exponential hardness barrier for conjugate-basis guessing. The bound is sequential—it holds even if the basis to be guessed is revealed after measurement, substantially restricting adaptive adversarial strategies.

Construction Using Conjunction Obfuscation

Security against adversaries is further enforced by using conjunction obfuscation instantiated via recent LPN-based distributional virtual black-box (VBB) obfuscators. Two obfuscations corresponding to the $X$ and $Z$ basis positions encode the decryption keys for each message. The obfuscators ensure that the adversary cannot determine which quantum measurements correspond to which basis until after successful evaluation, precluding basis-dependent measurement attacks.

Security Model

The analysis targets adversaries belonging to the class BPPQNC$_d$---those that can perform polynomial-time classical computations interleaved with quantum circuits of polynomial depth, with quantum state measured between rounds. This model captures realistic adversarial capabilities for NISQ-era hardware, where quantum coherence time and computational depth are physically constrained.

Security Analysis

Classical-Query Security

The main security theorem asserts simulation security in the QROM against quantum adversaries that are restricted to classical queries to the random oracle. The argument is built in several hybrids, relying on the VBB security of the obfuscator, the hardness of retrieving both conjunction secrets from the conjugate-coded states due to the newly proven POVM bound, and extraction via the random oracle that binds adversarial queries to specific measurement outcomes. The adversary's probability of recovering both messages is shown to be negligible in the security parameter. The probability of evaluating both obfuscated conjunctions, each associated with a disjoint secret, is exponentially small due to the bound on success in the conjugate basis.

Lifting to Depth-Bounded Quantum Security

Extending beyond classical oracle access, the scheme's security is informally lifted to hold against depth-bounded quantum adversaries via the compressed oracle (or "lifting") framework of Arora et al. This framework demonstrates that for BPPQNC$_d$ adversaries, quantum queries to specially constructed random oracles effectively reduce to classical transcripts, given the adversaries' limited coherence capabilities. Although the paper provides only an informal lifting argument, it is conjectured that the security proof extends to this more powerful adversary class contingent on formalizing the lifting lemma in this specific cryptographic context.

Implications and Future Directions

This construction advances the practical feasibility of quantum one-time programs and memories by minimizing reliance on sophisticated quantum resources and relaxing restrictive assumptions on adversarial quantum storage or hardware tokens. The results establish simulation security under realistic adversarial models suited to current and near-future quantum computational capabilities.

Theoretically, the approach raises several open questions:

• Tighter POVM Bounds: Improvements to the sequential measurement bound, currently $O(\epsilon^{1/4})$, could yield stronger security guarantees and tighter analysis.
• Noise Tolerance: Analysis of robustness under practical quantum noise models (e.g., depolarizing, dephasing), which would further inform implementation readiness.
• Quantum Memory Without Fault Tolerance: Formalizing models where quantum memory persists but full fault-tolerant computation is unattainable would reflect many real-world settings.
• Formal Lifting Theorem: Developing a rigorous, context-specific proof of security against depth-bounded quantum adversaries is required for trusted deployment.

The possibility of encoding OTMs into error-corrected quantum memory states for long-term storage is highlighted as a potential avenue for future quantum software protections, provided adversarial access remains depth-bounded.

Conclusion

This work presents a conceptually accessible and technically sound approach to constructing simulation-secure one-time memories in the QROM, secure against quantum adversaries with bounded adaptive depth. Its simplicity, reliance on only single-qubit states, and avoidance of strong quantum assumptions mark a significant theoretical and practical advance in quantum-enabled cryptography. The results and open problems chart a clear trajectory toward deployable, physically plausible quantum one-time programs and challenge the community to resolve the remaining theoretical hurdles for post-quantum secure software primitives.