Secure Quantum Computation with Classical Communication

James Bartusek

Paper 2021/964

Secure Quantum Computation with Classical Communication

James Bartusek, UC Berkeley

Abstract

The study of secure multi-party computation (MPC) has thus far been limited to the following two settings: every party is fully classical, or every party has quantum capabilities. This paper studies a notion of MPC that allows some classical and some quantum parties to securely compute a quantum functionality over their joint private inputs. In particular, we construct (constant-round, composable) protocols for blind and verifiable classical delegation of quantum computation, and give applications to the secure computation of quantum functionalities using only classical communication. Assuming QLWE (the quantum hardness of learning with errors), we obtain the following (maliciously-secure) protocols for computing any pseudo-deterministic quantum functionality. • A six-round protocol between one quantum server and multiple classical clients in the CRS (common random string) model. • A three-round protocol between one quantum server and multiple classical clients in the PKI (public key infrastructure) + QRO (quantum random oracle) model. • A two-message protocol between quantum sender and classical receiver (a quantum non-interactive secure computation protocol), in the QRO model. To enable the composability of our classical verification of quantum computation protocols, we require the notion of malicious blindness, which stipulates that the prover does not learn anything about the verifier’s delegated computation, even if it is able to observe whether or not the verifier accepted the proof. To construct a protocol with malicious blindness, we use a classical verification protocol for sampBQP computation (Chung et al., Arxiv 2020), which in general has inverse polynomial soundness error, to prove honest evaluation of QFHE (quantum fully-homomorphic encryption) ciphertexts with negligible soundness error. Obtaining a constant-round protocol requires a strong parallel repetition theorem for classical verification of quantum computation, which we show following the “nearly orthogonal projector” proof strategy (Alagic et al., TCC 2020).

Note: Updated Theorem 3.1

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published by the IACR in TCC 2021
Keywords: quantum cryptography MPC
Contact author(s): bartusek james @ gmail com
History: 2024-03-14: last of 3 revisions; 2021-07-22: received; See all versions
Short URL: https://ia.cr/2021/964
License: CC BY

BibTeX

@misc{cryptoeprint:2021/964,
      author = {James Bartusek},
      title = {Secure Quantum Computation with Classical Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2021/964},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/964}},
      url = {https://eprint.iacr.org/2021/964}
}