Building one-time memories from isolated qubits
arXiv:1304.5007 · doi:10.1145/2554797.2554823
Abstract
One-time memories (OTM'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's using quantum mechanical devices. It is known that OTM'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's that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements. 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. 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, 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 comment36 pages; v2: better organized, better motivated, and easier to read
References in corpus (22)
- Heralded entanglement between solid-state qubits separated by 3 meters
- Quantum Nonlocality without Entanglement
- Unconditionally secure quantum bit commitment is impossible
- Is Quantum Bit Commitment Really Possible?
- Insecurity of Quantum Secure Computations
- Coding Theorem and Strong Converse for Quantum Channels
- Local Distinguishability of Multipartite Orthogonal Quantum States
- Entropic uncertainty relations - A survey
- Quantum Data Hiding
- Hiding classical data in multi-partite quantum states
- Cryptography from Noisy Storage
- A framework for bounding nonlocality of state discrimination
- Complete Insecurity of Quantum Protocols for Classical Two-Party Computation
- The Bounded Storage Model in The Presence of a Quantum Adversary
- Unforgeable Noise-Tolerant Quantum Tokens
- Generic local distinguishability and completely entangled subspaces
- Multiparty data hiding of quantum information
- On the distinguishability of random quantum states
- Orthogonality And Distinguishability: Criterion For Local Distinguishability of Arbitrary Orthogonal States
- Hiding Quantum Data
- Building one-time memories from isolated qubits
- Secure Identification and QKD in the Bounded-Quantum-Storage Model
Cited by in corpus (7)
- Quantum Cryptography Beyond Quantum Key Distribution
- Building one-time memories from isolated qubits
- Privacy Amplification in the Isolated Qubits Model
- Single-shot security for one-time memories in the isolated qubits model
- Towards Quantum One-Time Memories from Stateless Hardware
- Performance of Practical Quantum Oblivious Key Distribution
- Quantum oblivious transfer: a short review