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:1511.01363 · Leibniz international proceedings in informatics

Quantum One-Time Memories from Stateless Hardware

Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou

Published Nov 4, 2015• 5 citations
arXivHTMLPDF

Abstract

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 show how to use quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. This is in sharp contrast with the classical case, where stateless hardware tokens alone cannot yield OTMs. In addition, our scheme is technologically simple. We prove security in the quantum universal composability framework, employing semi-definite programming results of Molina, Vidick and Watrous [TQC 2013] and combinatorial techniques of Pastawski et al. [Proc. Natl. Acad. Sci. 2012].

DOI
10.4230/lipics.tqc.2020.6

Related papers

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

Non-Interactive Oblivious Transfer and One-Time Programs from Noisy Quantum Storage

Ricardo Faleiro, Manuel Goulão, Leonardo Novo +1 more

Few primitives are as intertwined with the foundations of cryptography as Oblivious Transfer (OT). Not surprisingly, with the advent of quantum information processing, a major research path has emerged, aiming to minimize the requirements necessary to achieve OT by leveraging quantum resources, while also exploring the implications for secure computation. Indeed, OT has been the target of renewed focus regarding its newfound quantum possibilities (and impossibilities), both towards its computation and communication complexity. For instance, non-interactive OT, known to be impossible classically, has been strongly pursued. In its most extreme form, non-interactive chosen-input OT (one-shot OT) is equivalent to a One-Time Memory (OTM). OTMs have been proposed as tamper-proof hardware solutions for constructing One-Time Programs -- single-use programs that execute on an arbitrary input without revealing anything about their internal workings. In this work, we leverage quantum resources in the Noisy-Quantum-Storage Model to achieve: 1. Unconditionally-secure two-message non-interactive OT -- the smallest number of messages known to date for unconditionally-secure chosen-input OT. 2. Computationally-secure one-shot OT/OTM, with everlasting security, assuming only one-way functions and sequential functions -- without requiring trusted hardware, QROM, or pre-shared entanglement. 3. One-Time Programs without the need for hardware-based solutions or QROM, by compiling our OTM construction with the [GKR08, GIS+10] compiler.

arXiv:2410.08367•Oct 10, 2024•0 citations

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

Building one-time memories from isolated qubits

Yi-Kai Liu

One-time memories (OTM's) are simple tamper-resistant cryptographic devices, which can be used to implement one-time programs, a very general form of software protection and program obfuscation. Here we investigate the possibility of building OTM's using quantum mechanical devices. It is known that OTM's cannot exist in a fully-quantum world or in a fully-classical world. Instead, we propose a new model based on isolated qubits - qubits that can only be accessed using local operations and classical communication (LOCC). This model combines a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits), and can be implemented using current technologies, such as nitrogen vacancy centers in diamond. In this model, we construct OTM's that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements.

arXiv:1304.5007•Conference on Innovations in Theoretical Computer Science•Jan 12, 2014•12 citations

Quantum One-Time Programs, Revisited

Aparna Gupte, Jiahui Liu, Justin Raizes +2 more

One-time programs (Goldwasser, Kalai and Rothblum, CRYPTO 2008) are functions that can be run on any single input of a user's choice, but not on a second input. Classically, they are unachievable without trusted hardware, but the destructive nature of quantum measurements seems to provide a quantum path to constructing them. Unfortunately, Broadbent, Gutoski and Stebila showed that even with quantum techniques, a strong notion of one-time programs, similar to ideal obfuscation, cannot be achieved for any non-trivial quantum function. On the positive side, Ben-David and Sattath (Quantum, 2023) showed how to construct a one-time program for a certain (probabilistic) digital signature scheme, under a weaker notion of one-time program security. There is a vast gap between achievable and provably impossible notions of one-time program security, and it is unclear what functionalities are one-time programmable under the achievable notions of security. In this work, we present new, meaningful, yet achievable definitions of one-time program security for probabilistic classical functions. We show how to construct one time programs satisfying these definitions for all functions in the classical oracle model and for constrained pseudorandom functions in the plain model. Finally, we examine the limits of these notions: we show a class of functions which cannot be one-time programmed in the plain model, as well as a class of functions which appears to be highly random given a single query, but whose one-time program form leaks the entire function even in the oracle model.

arXiv:2411.01876•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•10 citations

Quantum One-Time Memories from Stateless Hardware, Random Access Codes, and Simple Nonconvex Optimization

Lev Stambler

We present a construction of one-time memories (OTMs) using classical-accessible stateless hardware, building upon the work of Broadbent et al. and Behera et al.. Unlike the aforementioned work, our approach leverages quantum random access codes (QRACs) to encode two classical bits, $b_0$ and $b_1$, into a single qubit state $\mathcal{E}(b_0 b_1)$ where the receiver can retrieve one of the bits with a certain probability of error. To prove soundness, we define a nonconvex optimization problem over POVMs on $\mathbb{C}^2$. This optimization gives an upper bound on the probability of distinguishing bit $b_{1-α}$ given that the probability that the receiver recovers bit $b_α$ is high. Assuming the optimization is sufficiently accurate, we then prove soundness against a polynomial number of classical queries to the hardware.

arXiv:2501.04168•Jan 7, 2025•6 citations
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 show how to use quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. This is in sharp contrast with the classical case, where stateless hardware tokens alone cannot yield OTMs. In addition, our scheme is technologically simple. We prove security in the quantum universal composability framework, employing semi-definite programming results of Molina, Vidick and Watrous [TQC 2013] and combinatorial techniques of Pastawski et al. [Proc. Natl. Acad. Sci. 2012].
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.
Few primitives are as intertwined with the foundations of cryptography as Oblivious Transfer (OT). Not surprisingly, with the advent of quantum information processing, a major research path has emerged, aiming to minimize the requirements necessary to achieve OT by leveraging quantum resources, while also exploring the implications for secure computation. Indeed, OT has been the target of renewed focus regarding its newfound quantum possibilities (and impossibilities), both towards its computation and communication complexity. For instance, non-interactive OT, known to be impossible classically, has been strongly pursued. In its most extreme form, non-interactive chosen-input OT (one-shot OT) is equivalent to a One-Time Memory (OTM). OTMs have been proposed as tamper-proof hardware solutions for constructing One-Time Programs -- single-use programs that execute on an arbitrary input without revealing anything about their internal workings. In this work, we leverage quantum resources in the Noisy-Quantum-Storage Model to achieve: 1. Unconditionally-secure two-message non-interactive OT -- the smallest number of messages known to date for unconditionally-secure chosen-input OT. 2. Computationally-secure one-shot OT/OTM, with everlasting security, assuming only one-way functions and sequential functions -- without requiring trusted hardware, QROM, or pre-shared entanglement. 3. One-Time Programs without the need for hardware-based solutions or QROM, by compiling our OTM construction with the [GKR08, GIS+10] compiler.
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.
One-time memories (OTM's) are simple tamper-resistant cryptographic devices, which can be used to implement one-time programs, a very general form of software protection and program obfuscation. Here we investigate the possibility of building OTM's using quantum mechanical devices. It is known that OTM's cannot exist in a fully-quantum world or in a fully-classical world. Instead, we propose a new model based on isolated qubits - qubits that can only be accessed using local operations and classical communication (LOCC). This model combines a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits), and can be implemented using current technologies, such as nitrogen vacancy centers in diamond. In this model, we construct OTM's that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements.
One-time programs (Goldwasser, Kalai and Rothblum, CRYPTO 2008) are functions that can be run on any single input of a user's choice, but not on a second input. Classically, they are unachievable without trusted hardware, but the destructive nature of quantum measurements seems to provide a quantum path to constructing them. Unfortunately, Broadbent, Gutoski and Stebila showed that even with quantum techniques, a strong notion of one-time programs, similar to ideal obfuscation, cannot be achieved for any non-trivial quantum function. On the positive side, Ben-David and Sattath (Quantum, 2023) showed how to construct a one-time program for a certain (probabilistic) digital signature scheme, under a weaker notion of one-time program security. There is a vast gap between achievable and provably impossible notions of one-time program security, and it is unclear what functionalities are one-time programmable under the achievable notions of security. In this work, we present new, meaningful, yet achievable definitions of one-time program security for probabilistic classical functions. We show how to construct one time programs satisfying these definitions for all functions in the classical oracle model and for constrained pseudorandom functions in the plain model. Finally, we examine the limits of these notions: we show a class of functions which cannot be one-time programmed in the plain model, as well as a class of functions which appears to be highly random given a single query, but whose one-time program form leaks the entire function even in the oracle model.
We present a construction of one-time memories (OTMs) using classical-accessible stateless hardware, building upon the work of Broadbent et al. and Behera et al.. Unlike the aforementioned work, our approach leverages quantum random access codes (QRACs) to encode two classical bits, b0b_0b0​ and b1b_1b1​, into a single qubit state E(b0b1)\mathcal{E}(b_0 b_1)E(b0​b1​) where the receiver can retrieve one of the bits with a certain probability of error. To prove soundness, we define a nonconvex optimization problem over POVMs on C2\mathbb{C}^2C2. This optimization gives an upper bound on the probability of distinguishing bit b1−αb_{1-α}b1−α​ given that the probability that the receiver recovers bit bαb_αbα​ is high. Assuming the optimization is sufficiently accurate, we then prove soundness against a polynomial number of classical queries to the hardware.