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.
Category / Keywords: foundations / quantum prover interactive proofs, interactive verification, delegated computation, quantum cryptography Original Publication (in the same form): IACR-TCC-2020 Date: received 13 Nov 2020 Contact author: galagic at gmail com, amchilds@umd edu, abgrilo@gmail com, shung@umd edu Available format(s): PDF | BibTeX Citation Version: 20201115:074251 (All versions of this report) Short URL: ia.cr/2020/1422