Secure Two-Party Quantum Computation Over Classical Channels

Abstract

Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output. In this work, we consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. Our first result shows that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. In particular, we show that the existence of a secure quantum computing protocol that relies only on classical channels would contradict the quantum no-cloning argument. We circumvent this impossibility following three different approaches. The first is by considering a weaker security notion called one-sided simulation security. This notion protects the input of one party (the quantum Bob) in the standard simulation-based sense and protects the privacy of the other party's input (the classical Alice). We show how to realize a protocol that satisfies this notion relying on the learning with errors assumption. The second way to circumvent the impossibility result, while at the same time providing standard simulation-based security also against a malicious Bob, is by assuming that the quantum input has an efficient classical representation. Finally, we focus our attention on the class of zero-knowledge functionalities and provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties. The direct implication of our result is that Mahadev's protocol for classical verification of quantum computations (FOCS'18) can be turned into a zero-knowledge proof of quantum knowledge with classical verifiers. To the best of our knowledge, we are the first to instantiate such a primitive.

arXiv comment(v2) changed the title, added new results, and improved readability. 55 pages

References in corpus (15)

• Quantum Teleportation is a Universal Computational Primitive
• Measurement-based quantum computation with cluster states
• Cluster-state quantum computation
• Methodology for quantum logic gate constructions
• Determinism in the one-way model
• Universally Composable Quantum Multi-Party Computation
• Interactive Proofs For Quantum Computations
• Complete Insecurity of Quantum Protocols for Classical Two-Party Computation
• Composable security of delegated quantum computation
• The Impossibility Of Secure Two-Party Classical Computation
• Multiparty Delegated Quantum Computing
• One-way Quantum Computation - a tutorial introduction
• Secure multi-party quantum computation with few qubits
• The Quantum Cut-and-Choose Technique and Quantum Two-Party Computation
• Composable secure multi-client delegated quantum computation