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 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.
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 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.
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.
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 ℓ=ℓ(λ), the construction uses nℓ qubits and (n+2)λ classical bits, and for any quantum adversary with at most 2ℓ/2−1−1 classical queries to the random oracle, its simulation advantage is at most (n+3)(43)n. Hence exponentially small simulation advantage in n.
Abstract A one-time memory (OTM) stores two bits such that either bit can be retrieved, but not both. One-time memories have been shown to allow for secure classical and quantum computations. We propose a physical construction of this mathematical cryptographic primitive, based on isolated Majorana islands. Using classical error-correcting codes, obtained from a quantum code, the scheme can be made robust to errors. Further, the one bit out of two bit OTM construction generalizes to 1-out-of- <?CDATA n?> n and <?CDATA (n−1)?> ( n − 1 ) -out-of- <?CDATA n?> n OTMs.
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.