Yi-Kai Liu (Theory Seminar Sp13)

liu.jpg"Building one-time memories from isolated qubits"
Yi-Kai Liu
Applied and Computational Mathematics Division
National Institute of Standards and Technology
Thursday, April 25, 2013, 2:00 pm
EBU3B, Room 4217

One-time memories (OTM's) are a simple type of tamper-resistant cryptographic hardware, which can be used to implement one-time programs, a strong form of secure computation. 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 old 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. An interesting open problem is to replace our random codes with efficiently-decodable codes, to get computationally-efficient OTM's that are secure against computationally-bounded LOCC adversaries.

In addition, we construct data-hiding states, which allow an LOCC sender to encode an (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.

ArXiv 1204.5007 http://arxiv.org/abs/1304.5007