Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Building one-time memories from isolated qubits

Published

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

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 June 17, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created January 14, 2014, Updated November 10, 2018