Secure Two-Party Quantum Computation Over Classical Channels

Abstract

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