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

Lev Stambler · 2025

Read Quantum One-Time Memories from Stateless Hardware, Random Access Codes, and Simple Nonconvex Optimization by Lev Stambler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-04168.txt.

Introduction

Lev Stambler designs a quantum memory that can be read only once. A one-time memory stores two bits but lets the receiver learn just one of them, a building block for secure computing. Earlier designs leaned on special hardware that keeps state.

Stambler's version uses stateless hardware plus quantum random access codes, which squeeze two bits into one qubit. Reading one bit scrambles the other. To prove security, he sets up a hard optimization problem over possible measurements. Its solution bounds how much a cheater could learn. The proof covers an attacker who queries the hardware many times.

Catalog record

CREATORLev Stambler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-04168

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum One-Time Memories from Stateless Hardware, Random Access Codes, and Simple Nonconvex Optimization Lev Stambler Abstract 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. [ BGZ21 , BSS21 ] . Unlike the aforementioned work, our approach leverages quantum random access codes (QRACs) to encode two classical bits, b 0 b_{0} and b 1 b_{1} , into a single qubit state ℰ ⁡ ( b 0 ​ b 1 ) \mathcal{E}\left(b_{0}b_{1}\right) 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 ℂ 2 \mathbb{C}^{2} . This optimization gives an upper bound on the probability of distinguishing bit b 1 − α b_{1-\alpha} given that the probability that the receiver recovers bit b α b_{\alpha} is high. Assuming the optimization is sufficiently accurate, we then prove soundness against a polynomial number of classical queries to the hardware. 1 Introduction One-time programs (and variants) were first formally introduced in Ref. [ GKR08 ] and sit at the top of the cryptographic wish list. Unfortunately, one-time programs are impossible to achieve in the standard model and idealized quantum model [ GKR08 , BGS12 ] . Still, if hardware assumptions enable a primitive known as one-time memories, then one-time programs can be built [ GKR08 ] . Ref. [ BGS12 ] also showed how to build (classical and quantum) one-time programs from OTMs in the Universal Composability (UC) model A one-time memory (OTM) is a cryptographic primitive which can be used to build one-time programs and non-interactive secure two party computation [ Yao82 , GIS+10 ] . OTMs can be thought of as a non-interactive version of oblivious transfer (OT) where a sending party, Alice, sends a one-time memory to a receiving party, Bob. The memory encodes two classical strings, m_{0} and m_{1} , and Bob can only learn one of the strings. After Bob reads m_{b} , any encoding of m_{1-b} is “erased” and Bob cannot recover m_{1-b} . Currently, OTMs rely on hardware-specific assumptions such as tamper-proof hardware [ Smi81 , Kat07 ] and trusted execution environments (TEEs) [ PRM09 , ZCD+19 ] . Unfortunately, so-called “replay” attacks have been carried out on TEE based OTMs [ SYG+19 ] . A series of works [ Liu14 , Liu15 , Liu23 , BS23 ] make a separate set of assumptions on quantum hardware to build one-time memories. Ref. [ BGZ21 ] began a line of work on constructing one-time memories assuming stateless trusted hardware. Indeed, if we cannot immunize trusted hardware against replay attacks, then we can use trusted hardware in conjunction with quantum states to build one-time memories. Importantly, to build one-time memories from (stateless) trusted hardware and quantum states, we must assume that the adversary cannot make quantum queries to the hardware [ BGZ21 ] . Ref. [ BGZ21 ] proposes a protocol using Wiesner coding to build one-time memories from stateless hardware and quantum states but only prove security for a linear number of queries to the hardware. Behera et al. [ BSS21 ] provide a construction for noise-tolerant quantum tokens using Wiesner coding and stateless hardware. Ref. [ BSS21 ] then prove security for a polynomial number of queries to the stateless hardware as well as provide a secure and noise-tolerant construction for one-time memories. Moreover, Chung et al. [ CGLZ19 ] construct disposable backdoors using random subspace states and stateless hardware. Ref. [ CGLZ19 ] also provides a construction for one-time memories using random subspace states and stateless hardware. In a more complexity-theoretic focused work, Li et al. [ LLPY23 ] show that \mathsf{BQP/qploy}\neq\mathsf{BQP/poly} and \mathsf{QMA}\neq\mathsf{QCMA} relative to an classical -accessible oracle (where the oracle can only be queried classically). We note that this is a similar setting in our work where we model the stateless hardware as a classical-accessible oracle. Interestingly, the existance of one-time programs in the presence of stateless hardware seems to provide a plausible seperation between providing a classical-accessible oracle and a quantum-accessible oracle: as noted by Ref. [ BGS12 ] , one-time programs are impossible with quantum-accessible oracles, but in this work we construct one-time memories with classical-accessible oracles. We leave further exploration of this connection to future work. 1.1 Main Result Our main result is the construction of one-time memories from stateless hardware and quantum random access codes (QRACs) [ ANTSV99 ] in lieu of Wiesner states. Moreover, one of our key contributions is a simple proof of soundness which leverages a nonconvex optimization over POVMs for states in \mathbbm{C}^{2} (single qubit states) 1 1 1 We note that an \epsilon -net technique in combination with brute force search could potentially be used to solve our optimization problem with provable guarantees. We leave this as an open question for future work. . Specifically, we use QRACs to encode two classical bits, b_{0},b_{1} , into a single qubit state, \mathcal{E}\left(b_{0}b_{1}\right) , where the receiver can recover one of the bits with some probability of error. We first provide a simple nonconvex optimization which upper-bounds the trace distance between \mathcal{E}\left(b_{0}0\right) and \mathcal{E}\left(b_{0}1\right) given that the receiver performed some POVMs which can recover b_{0} with high probability. Then, to construct our OTMs for messages m_{0},m_{1} , we sample 2 n -bit strings, r_{0},r_{1} . We encode r_{0},r_{1} into n QRAC states, \mathcal{E}\left(r_{0}^{1}r_{1}^{1}\right)\otimes\ldots\otimes\mathcal{E}\left(r_{0}^{n}r_{1}^{n}\right) . To “unlock” message m_{b} , the receiver must recover a certain fraction of r_{b} . We then show that in order to recover r_{b} , the receiver must “collapse” the ability to distinguish between \mathcal{E}\left(r_{b}^{i}0\right) and \mathcal{E}\left(r_{b}^{i}1\right) for most i\in[n] . For simplicty, we will model the trusted hardware as a black box which only accepts classical queries. 2 Preliminaries In this section, we will introduce the necessary background for our construction of one-time memories. 2.1 Quantum Random Access Code (QRAC) A quantum random access code is a uniquely quantum primitive that allows a sender to encode multiple messages into a single quantum state. A receiver can then perform a measurement on the state to recover one of the messages with some probability of error. 2.1 2\mapsto 1 Quantum Random Access Code (QRAC) [ ANTSV99 ] . A QRAC is an ordered tuple (\mathcal{E},\mu_{0},\mu_{1}) where \mathcal{E}:\mathbbm{F}_{2}^{2}\rightarrow\mathbbm{C}^{2} and 2 orthonormal measurements \mu_{\alpha}=\set{\ket{\phi_{\alpha}^{0}},\ket{\phi_{\alpha}^{1}}} for \alpha\in\set{0,1} . For our purposes, we will consider a fixed 2\mapsto 1 QRAC. Specifically, we will use the optimal 2\mapsto 1 QRAC from Ref. [ ANTSV99 ] . Define \ket{\psi_{\theta}}=\cos(\theta)\ket{0}+\sin(\theta)\ket{1} . Then, the optimal 2\mapsto 1 QRAC is given by the following mapping: \displaystyle\mathcal{E}\left(00\right)\mapsto\ket{\psi_{\pi/8}}\bra{\psi_{\pi/8}}\;\;\;\; \displaystyle\mathcal{E}\left(01\right)\mapsto\ket{\psi_{-\pi/8}}\bra{\psi_{-\pi/8}} \displaystyle\mathcal{E}\left(10\right)\mapsto\ket{\psi_{5\pi/8}}\bra{\psi_{5\pi/8}}\;\; \displaystyle\mathcal{E}\left(11\right)\mapsto\ket{\psi_{-5\pi/8}}\bra{\psi_{-5\pi/8}}\;\; and the measurements are given by projecting onto \mu_{0}=\set{\ket{0}\bra{0},\ket{1}\bra{1}} (the Z basis) and \mu_{1}=\set{\ket{\psi_{\pi/4}}\bra{\psi_{\pi/4}},\ket{\psi_{-\pi/4}}\bra{\psi_{-\pi/4}}} (the X basis). We also know that the optimal success probability of this QRAC is \cos^{2}(\pi/8)<0.854 [ ANTSV99 ] . 2.2 POVMs, Trace Distance, and Distinguishing Probability We will use a few basic definitions and theorems from quantum information theory. For a more in-depth treatment, see Nielsen and Chuang [ NC01 ] . 2.2 POVM. Let \mathcal{H} be a Hilbert space. A Positive Operator-Valued Measure (POVM) on \mathcal{H} is a collection of operators \set{M_{i}}_{i\in[m]} such that M_{i}\geq 0 for all i and \sum_{i=1}^{m}M_{i}=I . POVMs are useful

Read the complete text