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.
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.
One-time memories (OTM’s) are a simple type of tamper-resistant cryptographic hardware, which can be used to implement many forms of secure computation, such as one-time programs. Here we investigate the possibility of building OTM’s using isolated qubits — qubits that can only be accessed using local operations and classical communication (LOCC). Isolated qubits can be implemented using current technologies, such as nitrogen vacancy centers in diamond. We construct OTM’s that are information-theoretically secure against one-pass LOCC adversaries using 2-outcome measurements. (Also, these OTM’s can be prepared and accessed by honest parties using only LOCC operations.) This result is somewhat surprising, as OTM’s cannot exist in a fully-quantum world or in a fully-classical world; yet they can be built from the combination of a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits). Our construction resembles Wiesner’s original idea of quantum conjugate coding, implemented using random error-correcting codes; our proof of security uses entropy chaining to bound the supremum of a suitable empirical process. In addition, we conjecture that our random codes can be replaced by some class of efficiently-decodable codes, to get computationally-efficient OTM’s that are secure against computationally-bounded LOCC adversaries. In addition, we construct data-hiding states, which allow an LOCC sender to encode an (n O(1))bit messsage into n qubits, such that at most half of the message can be extracted by a one-pass LOCC receiver, but the whole message can be extracted by a general quantum receiver.
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 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, b0 and b1, into a single qubit state E(b0b1) 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. This optimization gives an upper bound on the probability of distinguishing bit b1−α 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.
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].
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.