Quantum one-time programs

Abstract

One-time programs are modelled after a black box that allows a single evaluation of a function, and then self-destructs. Because software can, in principle, be copied, general one-time programs exists only in the hardware token model: it has been shown that any function admits a one-time program as long as we assume access to physical devices called one-time memories. Quantum information, with its well-known property of no-cloning, would, at first glance, prevent the basic copying attack for classical programs. We show that this intuition is false: one-time programs for both classical and quantum maps, based solely on quantum information, do not exist, even with computational assumptions. We complement this strong impossibility proof by an equally strong possibility result: assuming the same basic one-time memories as used for classical one-time programs, we show that every quantum map has a quantum one-time program that is secure in the universal composability framework. Our construction relies on a new, simpler quantum authentication scheme and corresponding mechanism for computing on authenticated data.

62 pages, 5 figures

References in corpus (17)

• Simple Proof of Security of the BB84 Quantum Key Distribution Protocol
• Quantum Teleportation is a Universal Computational Primitive
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Universal blind quantum computation
• Programmable quantum gate arrays
• Authentication of Quantum Messages
• Quantum Copy-Protection and Quantum Money
• Universally Composable Quantum Multi-Party Computation
• Quantum one-time programs
• Interactive Proofs For Quantum Computations
• Complete Insecurity of Quantum Protocols for Classical Two-Party Computation
• Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority
• On Universal and Fault-Tolerant Quantum Computing
• Composable security of delegated quantum computation
• Quantum Money from Hidden Subspaces
• Simulatable security for quantum protocols
• Universal quantum circuit for n-qubit quantum gate: A programmable quantum gate

Cited by in corpus (35)

• Security in Quantum Cryptography
• Unconditionally verifiable blind computation
• Quantum Cryptography Beyond Quantum Key Distribution
• Verification of quantum computation: An overview of existing approaches
• Quantum computing on encrypted data
• Quantum homomorphic encryption for circuits of low $T$-gate complexity
• Robustness and device independence of verifiable blind quantum computing
• Quantum one-time programs
• Composable security of delegated quantum computation
• How to Verify a Quantum Computation
• Semiquantum key distribution with secure delegated quantum computation
• Optimised resource construction for verifiable quantum computation
• Quantum authentication with key recycling
• Zero-knowledge proof systems for QMA
• Cryptographic approach to Quantum Metrology
• Computational Security of Quantum Encryption
• Quantum Fully Homomorphic Encryption With Verification
• Quantum processing by remote quantum control
• Efficient Simulation for Quantum Message Authentication
• Quantum advantage for probabilistic one-time programs
• On the possibility of classical client blind quantum computing
• Probabilistic one-time programs using quantum entanglement
• Blind quantum computing with two almost identical states
• Privacy Amplification in the Isolated Qubits Model
• On optimising quantum communication in verifiable quantum computing
• Secure Software Leasing
• Single-shot security for one-time memories in the isolated qubits model
• Single-Use Delegatable Signatures Based on Smart Contracts
• Towards Quantum One-Time Memories from Stateless Hardware
• New security notions and feasibility results for authentication of quantum data
• Public verifiable measurement-only blind quantum computation based on entanglement witnesses
• Erasable Bit Commitment from Temporary Quantum Trust
• New Approaches for Quantum Copy-Protection
• Accessing inaccessible information via quantum indistinguishability
• One-Time Programs made Practical