Complete Insecurity of Quantum Protocols for Classical Two-Party Computation

Abstract

A fundamental task in modern cryptography is the joint computation of a function which has two inputs, one from Alice and one from Bob, such that neither of the two can learn more about the other's input than what is implied by the value of the function. In this Letter, we show that any quantum protocol for the computation of a classical deterministic function that outputs the result to both parties (two-sided computation) and that is secure against a cheating Bob can be completely broken by a cheating Alice. Whereas it is known that quantum protocols for this task cannot be completely secure, our result implies that security for one party implies complete insecurity for the other. Our findings stand in stark contrast to recent protocols for weak coin tossing, and highlight the limits of cryptography within quantum mechanics. We remark that our conclusions remain valid, even if security is only required to be approximate and if the function that is computed for Bob is different from that of Alice.

v2: 6 pages, 1 figure, text identical to PRL-version (but reasonably formatted)

References in corpus (3)

• Post-selection technique for quantum channels with applications to quantum cryptography
• Universally Composable Quantum Multi-Party Computation
• Quantum weak coin flipping with arbitrarily small bias

Cited by in corpus (38)

• Quantum Cryptography Beyond Quantum Key Distribution
• Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
• Entanglement sampling and applications
• Quantum one-time programs
• Quantum cryptography: key distribution and beyond
• Imperfect 1-out-of-2 quantum oblivious transfer: bounds, a protocol, and its experimental implementation
• Continuous-Variable Protocol for Oblivious Transfer in the Noisy-Storage Model
• Spacetime-constrained oblivious transfer
• Practical and unconditionally secure spacetime-constrained oblivious transfer
• Multiphoton and side-channel attacks in mistrustful quantum cryptography
• One-out-of-$m$ spacetime-constrained oblivious transfer
• Building one-time memories from isolated qubits
• Verifiable Quantum Secure Modulo Summation
• Privacy Amplification in the Isolated Qubits Model
• The Impossibility of Efficient Quantum Weak Coin-Flipping
• Single-shot security for one-time memories in the isolated qubits model
• Quantifying the Leakage of Quantum Protocols for Classical Two-Party Cryptography
• Quantum non-locality, causality and mistrustful cryptography
• Delayed choice relativistic quantum bit commitment with arbitrarily long commitment time
• Can relativistic bit commitment lead to secure quantum oblivious transfer?
• Unconditionally secure relativistic multi-party biased coin flipping and die rolling
• A quantum homomorphic encryption scheme for polynomial-sized circuits
• Oblivious Transfer is in MiniQCrypt
• Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming
• Optimal bounds for semi-honest quantum oblivious transfer
• Secure Two-Party Quantum Computation Over Classical Channels
• Hybrid Quantum Cryptography from Communication Complexity
• Secure Identification in The Isolated Qubits Model
• Impossibility of Quantum Private Queries
• A framework for quantum homomorphic encryption with experimental demonstration
• On the Security of Password-Authenticated Quantum Key Exchange
• Concerning Quantum Identification Without Entanglement
• One-out-of-two Quantum Oblivious Transfer based on Nonorthogonal States
• Cryptanalysis and improvement of Wu-Cai-Wu-Zhang's quantum private comparison protocol
• Quantum preprocessing for information-theoretic security in two-party computation
• Asymptotically secure All-or-nothing Quantum Oblivious Transfer
• Quantum oblivious transfer: a short review
• Impossibility of adversarial self-testing and secure sampling