Cryptology ePrint Archive: Report 2020/1471

On The Round Complexity of Two-Party Quantum Computation

James Bartusek and Andrea Coladangelo and Dakshita Khurana and Fermi Ma

Abstract: We investigate the round complexity of maliciously-secure two-party quantum computation (2PQC) with setup, and obtain the following results:

- A three-message protocol (two-message if only one party receives output) in the common random string (CRS) model assuming classical two-message oblivious transfer (OT) with post-quantum malicious security. This round complexity is optimal for the sequential communication setting. Under the additional assumption of reusable malicious designated-verifier non-interactive zero-knowledge (MDV-NIZK) arguments for NP, our techniques give an MDV-NIZK for QMA. Each of the assumptions mentioned above is known from the quantum hardness of learning with errors (QLWE).

- A protocol with two simultaneous rounds of communication, in a quantum preprocessing model, assuming sub-exponential QLWE. In fact, we construct a three-round protocol in the CRS model with only two rounds of online communication, which implies the above result. Along the way, we develop a new delayed simulation technique that we call "simulation via teleportation," which may be useful in other settings.

In addition, we perform a preliminary investigation into barriers and possible approaches for two-round 2PQC in the CRS model. We provide evidence that protocols admitting a natural class of simulators do not exist, and also give a proof-of-concept construction from a strong form of quantum virtual black-box (VBB) obfuscation.

Prior to our work, maliciously-secure 2PQC required round complexity linear in the size of the quantum circuit.

Category / Keywords: cryptographic protocols / secure quantum computation

Date: received 22 Nov 2020, last revised 11 Dec 2020

Contact author: bartusek james at gmail com,andrea coladangelo@gmail com,dakshita@illinois edu,fermima@alum mit edu

Available format(s): PDF | BibTeX Citation

Note: updated acknowledgments

Version: 20201212:040151 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]