International Association
for Cryptologic Research

One-time memories (OTM\'s) are simple, tamper-resistant cryptographic devices, which can be used to implement sophisticated functionalities such as one-time programs. Can one construct OTM\'s whose security follows from some physical principle? This is not possible in a fully-classical world, or in a fully-quantum world, but there is evidence that OTM\'s can be built using \"isolated qubits\" -- qubits that cannot be entangled, but can be accessed using adaptive sequences of single-qubit measurements.

Here we present new constructions for OTM\'s using isolated qubits, which improve on previous work in several respects: they achieve a stronger \"single-shot\" security guarantee, which is stated in terms of the (smoothed) min-entropy; they are proven secure against adversaries who can perform arbitrary local operations and classical communication (LOCC); and they are efficiently implementable.

These results use Wiesner\'s idea of conjugate coding, combined with error-correcting codes that approach the capacity of the q-ary symmetric channel, and a high-order entropic uncertainty relation, which was originally developed for cryptography in the bounded quantum storage model.