Lev Stambler

We show how to construct simulation secure one-time memories, and thus one-time programs, without computational assumptions in the presence of constraints on quantum hardware. Specifically, we build one-time memories from random linear codes and quantum random access codes (QRACs) when constrained to non-adaptive, constant depth, and D-dimensional geometrically-local quantum circuit for some constant D. We place no restrictions on the adversary's classical computational power, number of qubits it can use, or the coherence time of its qubits. Notably, our construction can still be secure even in the presence of fault tolerant quantum computation as long as the input qubits are encoded in a non-fault tolerant manner (e.g. encoded as high energy states in non-ideal hardware). Unfortunately though, our construction requires decoding random linear codes and thus does not run in polynomial time. We leave open the question of whether one can construct a polynomial time information theoretically secure one-time memory from geometrically local quantum circuits. Of potentially independent interest, we develop a progress bound for information leakage via collision entropy (Rényi entropy of order 2) along with a few key technical lemmas for a "mutual information" for collision entropies. We also develop new bounds on how much information a specific $2 \mapsto 1$ QRAC can leak about its input, which may be of independent interest as well.

In this work we present a publicly verifiable quantum money protocol which assumes close to no quantum computational capabilities. We rely on one-time memories which in turn can be built from quantum conjugate coding and hardware-based assumptions. Specifically, our scheme allows for a limited number of verifications and also allows for quantum tokens for digital signatures. Double spending is prevented by the no-cloning principle of conjugate coding states. An implementation of the concepts presented in this work can be found at https://github.com/neverlocal/otm_billz.

We introduce Verifiable One-Time Programs (VOTPs) and use them to construct single-round Open Secure Computation (OSC), a novel primitive enabling applications like (1) single-round sealed-bid auctions, (2) single-round and honest-majority atomic proposes---a building block of consensus protocols, (3) fair-exchange, and (4) single-round differentially private statistical aggregation without pre-registration. The underlying quantum requirement is minimal: only single-qubit states are needed alongside a hardware assumption on the receiver's quantum resources. However, our construction relies on advanced classical primitives (multi-key FHE, NIZKs), making classical computational overhead the primary barrier to practice. Our work therefore provides a new framework for quantum-assisted cryptography that may be implementable with near-term quantum technology.