Cryptology ePrint Archive: Report 2021/964

Secure Quantum Computation with Classical Communication

James Bartusek

Abstract: We construct a constant-round composable protocol for blind and verifiable classical delegation of quantum computation, and show applications to secure quantum computation with classical communication. In particular, we give the first maliciously-secure multi-party protocols for BQP (bounded-error quantum polynomial-time) computation that only require a single party to have quantum capabilities. Assuming QLWE (the quantum hardness of learning with errors), we obtain the following. - 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.

The only previously known approach for obtaining composable security of blind classical verification of quantum computation (Gheorghiu and Vidick, FOCS 2019) has inverse polynomial security and requires polynomially many rounds of interaction.

The property we require of classical verification of quantum computation that enables composability is 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 interaction. 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).

Category / Keywords: cryptographic protocols / quantum cryptography, MPC

Date: received 16 Jul 2021, last revised 16 Jul 2021

Contact author: bartusek james at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210722:091255 (All versions of this report)

Short URL: ia.cr/2021/964


[ Cryptology ePrint archive ]