On The Round Complexity of Secure Quantum Computation

James Bartusek; Andrea Coladangelo; Dakshita Khurana; Fermi Ma

Paper 2020/1471

On The Round Complexity of Secure Quantum Computation

James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma

Abstract

We construct the first constant-round protocols for secure quantum computation in the two-party (2PQC) and multi-party (MPQC) settings with security against malicious adversaries. Our protocols are in the common random string (CRS) model. - Assuming two-message oblivious transfer (OT), we obtain (i) three-message 2PQC, and (ii) five-round MPQC with only three rounds of online (input-dependent) communication; such OT is known from quantum-hard Learning with Errors (QLWE). - Assuming sub-exponential hardness of QLWE, we obtain (i) three-round 2PQC with two online rounds and (ii) four-round MPQC with two online rounds. - When only one (out of two) parties receives output, we achieve minimal interaction (two messages) from two-message OT; classically, such protocols are known as non-interactive secure computation (NISC), and our result constitutes the first maliciously-secure quantum NISC. Additionally assuming reusable malicious designated-verifier NIZK arguments for NP (MDV-NIZKs), we give the first MDV-NIZK for QMA that only requires one copy of the quantum witness. Finally, we perform a preliminary investigation into two-round secure quantum computation where each party must obtain output. On the negative side, we identify a broad class of simulation strategies that suffice for classical two-round secure computation that are unlikely to work in the quantum setting. Next, as a proof-of-concept, we show that two-round secure quantum computation exists with respect to a quantum oracle.

Note: updated acknowledgments

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published by the IACR in CRYPTO 2021
Keywords: secure quantum computation
Contact author(s): bartusek james @ gmail com
andrea coladangelo @ gmail com
dakshita @ illinois edu
fermima @ alum mit edu
History: 2021-08-13: last of 4 revisions; 2020-11-24: received; See all versions
Short URL: https://ia.cr/2020/1471
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1471,
      author = {James Bartusek and Andrea Coladangelo and Dakshita Khurana and Fermi Ma},
      title = {On The Round Complexity of Secure Quantum Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1471},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1471}},
      url = {https://eprint.iacr.org/2020/1471}
}