Building one-time memories from isolated qubits

Published

January 14, 2014

Author(s)

Yi-Kai Liu

Abstract

One-time memories (OTM's) are a simple type of tamper-resistant cryptographic hardware, that can be used to implement many forms of secure computation, such as one-time programs. Here we investigate the possibility of building OTM's using "isolated qubits" -- qubits that can only be accessed using local operations and classical communication (LOCC). Isolated qubits can be implemented using current technologies, such as nitrogen vacancy centers in diamond. We construct OTM's that are information-theoretically secure against one-pass LOCC adversaries using 2-outcome measurements. (Also, these OTM's can be prepared and accessed by honest parties using only LOCC operations.) This result is somewhat surprising, as OTM's cannot exist in a fully-quantum world or in a fully-classical world; yet they can be built from the combination of a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits). Our construction resembles Wiesner's original idea of quantum conjugate coding, implemented using random error-correcting codes; our proof of security uses entropy chaining to bound the supremum of a suitable empirical process. In addition, we conjecture that our random codes can be replaced by some class of efficiently-decodable codes, to get computationally-efficient OTM's that are secure against computationally-bounded LOCC adversaries. In addition, we construct data-hiding states, that allow an LOCC sender to encode a (n-O(1))-bit messsage into n qubits, such that at most half of the message can be extracted by a one-pass LOCC receiver, but the whole message can be extracted by a general quantum receiver.

Proceedings Title

Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS 2014)

Conference Dates

January 12-14, 2014

Conference Location

Princeton, NJ

Pub Type

Conferences

Download Paper

DOI Link

Keywords

quantum computation, cryptography, information theory, empirical processes

Citation

Liu, Y. (2014), Building one-time memories from isolated qubits, Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS 2014), Princeton, NJ, [online], https://doi.org/10.1145/2554797.2554823 (Accessed November 21, 2024)