Paper 2020/1422

Non-interactive classical verification of quantum computation

Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung

Abstract

In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. We show that this same task can in fact be performed non-interactively (with setup) and in zero-knowledge. Our protocols result from a sequence of significant improvements to the original four-message protocol of Mahadev. We begin by making the first message instance-independent and moving it to an offline setup phase. We then establish a parallel repetition theorem for the resulting three-message protocol, with an asymptotically optimal rate. This, in turn, enables an application of the Fiat-Shamir heuristic, eliminating the second message and giving a non-interactive protocol. Finally, we employ classical non-interactive zero-knowledge (NIZK) arguments and classical fully homomorphic encryption (FHE) to give a zero-knowledge variant of this construction. This yields the first purely classical NIZK argument system for QMA, a quantum analogue of NP. We establish the security of our protocols under standard assumptions in quantum-secure cryptography. Specifically, our protocols are secure in the Quantum Random Oracle Model, under the assumption that Learning with Errors is quantumly hard. The NIZK construction also requires circuit-private FHE.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2020
Keywords
quantum prover interactive proofsinteractive verificationdelegated computationquantum cryptography
Contact author(s)
galagic @ gmail com
amchilds @ umd edu
abgrilo @ gmail com
shung @ umd edu
History
2020-11-15: received
Short URL
https://ia.cr/2020/1422
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1422,
      author = {Gorjan Alagic and Andrew M.  Childs and Alex B.  Grilo and Shih-Han Hung},
      title = {Non-interactive classical verification of quantum computation},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1422},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1422}},
      url = {https://eprint.iacr.org/2020/1422}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.