@article {1426, title = {Building one-time memories from isolated qubits}, journal = {Innovations in Theoretical Computer Science (ITCS)}, year = {2013}, month = {2013/04/18}, pages = {269-286}, abstract = { One-time memories (OTM{\textquoteright}s) are simple tamper-resistant cryptographic devices, which can be used to implement one-time programs, a very general form of software protection and program obfuscation. Here we investigate the possibility of building OTM{\textquoteright}s using quantum mechanical devices. It is known that OTM{\textquoteright}s cannot exist in a fully-quantum world or in a fully-classical world. Instead, we propose a new model based on "isolated qubits" -- qubits that can only be accessed using local operations and classical communication (LOCC). This model combines a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits), and can be implemented using current technologies, such as nitrogen vacancy centers in diamond. In this model, we construct OTM{\textquoteright}s that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements. Our construction resembles Wiesner{\textquoteright}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. In addition, we conjecture that our random codes can be replaced by some class of efficiently-decodable codes, to get computationally-efficient OTM{\textquoteright}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. }, doi = {10.1145/2554797.2554823}, url = {http://arxiv.org/abs/1304.5007v2}, author = {Yi-Kai Liu} }