Quantum advantage for probabilistic one-time programs
arXiv:1709.09724 · doi:10.1038/s41467-018-07591-2
Abstract
One-time programs, computer programs which self-destruct after being run only once, are a powerful building block in cryptography and would allow for new forms of secure software distribution. However, ideal one-time programs have been proved to be unachievable using either classical or quantum resources. Here we relax the definition of one-time programs to allow some probability of error in the output and show that quantum mechanics offers security advantages over purely classical resources. We introduce a scheme for encoding probabilistic one-time programs as quantum states with prescribed measurement settings, explore their security, and experimentally demonstrate various one-time programs using measurements on single-photon states. These include classical logic gates, a program to solve Yao's millionaires problem, and a one-time delegation of a digital signature. By combining quantum and classical technology, we demonstrate that quantum techniques can enhance computing capabilities even before full-scale quantum computers are available.
References in corpus (20)
- On the Measurement of Qubits
- Near optimal single photon sources in the solid state
- Unconditionally secure quantum bit commitment is impossible
- Insecurity of Quantum Secure Computations
- A wavelength-tunable fiber-coupled source of narrowband entangled photons
- Phase-stable source of polarization-entangled photons using a polarization Sagnac interferometer
- Quantum state discrimination and its applications
- Experimental Superposition of Orders of Quantum Gates
- On-demand generation of background--free single photons from a solid-state source
- Quantum Copy-Protection and Quantum Money
- Why Quantum Bit Commitment And Ideal Quantum Coin Tossing Are Impossible
- Optimal lower bounds for quantum automata and random access codes
- Finding optimal strategies for minimum-error quantum-state discrimination
- Quantum one-time programs
- Optimal bounds for parity-oblivious random access codes
- Experimental implementation of bit commitment in the noisy-storage model
- An Experimental Implementation of Oblivious Transfer in the Noisy Storage Model
- (4,1)-Quantum Random Access Coding Does Not Exist
- Privacy Amplification in the Isolated Qubits Model
- Single-shot security for one-time memories in the isolated qubits model
Cited by in corpus (12)
- One-Time Universal Hashing Quantum Digital Signatures without Perfect Keys
- Beating the fault-tolerance bound and security loopholes for Byzantine agreement with a quantum solution
- Imperfect 1-out-of-2 quantum oblivious transfer: bounds, a protocol, and its experimental implementation
- Quantum cryptography beyond key distribution: theory and experiment
- Probabilistic one-time programs using quantum entanglement
- Forty Thousand Kilometers Under Quantum Protection
- Single-Use Delegatable Signatures Based on Smart Contracts
- Discrete-Modulated Continuous-Variable Quantum Key Distribution in Satellite-to-Ground Communication
- Continuous-variable quantum digital signatures that can withstand coherent attacks
- Accessing inaccessible information via quantum indistinguishability
- Incomplete quantum oblivious transfer with perfect one-sided security
- Flexible Cloud/User-Centric Entanglement and Photon Pair Distribution with Synthesizable Optical Router