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

• URL: http://arxiv.org/abs/2601.13258v1
• Date: Mon, 19 Jan 2026 17:48:14 GMT
• Title: Towards Simple and Useful One-Time Programs in the Quantum Random Oracle Model
• Authors: Lev Stambler,
• Abstract summary: We construct simulation-secure one-time memories (OTM) in the random oracle model.<n>We present a plausible argument for their security against quantum adversaries with bounded and adaptive depth.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• NISQ Security and Complexity via Simple Classical Reasoning [41.17296890645859]
  We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings.<n>We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries.<n>We derive the first direct product theorems in the average case, in the hybrid setting-i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games.
  arXiv  Detail & Related papers  (2025-09-11T23:31:39Z)
• Pseudorandom quantum authentication [0.8204952610951527]
  We introduce the pseudorandom quantum authentication scheme (PQAS)<n>It is an efficient method for quantum states that relies solely on the existence of pseudorandom unitaries (PRUs)
  arXiv  Detail & Related papers  (2025-01-01T20:46:37Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Quantum One-Time Protection of any Randomized Algorithm [0.03320194947871346]
  A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once.<n>We propose a scheme for building quantum one-time tokens for any randomized classical program, which include generative AI models.
  arXiv  Detail & Related papers  (2024-11-05T18:00:29Z)
• Certified Randomness from Quantum Supremacy [5.313318620422295]
  We propose an application for near-term quantum devices, namely, generating cryptographically certified random bits. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling. We show that our protocol's output is unpredictable even to a computationally unbounded adversary.
  arXiv  Detail & Related papers  (2023-03-02T23:28:31Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Post-Quantum Multi-Party Computation [32.75732860329838]
  We study multi-party computation for classical functionalities (in the plain model) with security against malicious-time quantum adversaries. We assume superpolynomial quantum hardness of learning with errors (LWE), and quantum hardness of an LWE-based circular security assumption. Along the way, we develop cryptographic primitives that may be of independent interest.
  arXiv  Detail & Related papers  (2020-05-23T00:42:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.