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.
