Cryptology ePrint Archive: Report 2014/455

Single-shot security for one-time memories in the isolated qubits model

Yi-Kai Liu

Abstract: 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.

Category / Keywords: foundations / quantum cryptography; information theory; oblivious transfer

Original Publication (in the same form): IACR-CRYPTO-2014

Date: received 12 Jun 2014

Contact author: yikailiu00 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140615:111447 (All versions of this report)

Short URL: ia.cr/2014/455

Discussion forum: Show discussion | Start new discussion