Paper 2021/964

Secure Quantum Computation with Classical Communication

James Bartusek

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 BQP (bounded-error quantum polynomial-time) 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).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in Tcc 2021
Keywords
quantum cryptographyMPC
Contact author(s)
bartusek james @ gmail com
History
2021-11-05: revised
2021-07-22: received
See all versions
Short URL
https://ia.cr/2021/964
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.