### Succinct Classical Verification of Quantum Computation

##### Abstract

We construct a classically verifiable succinct interactive argument for quantum computation (BQP) with communication complexity and verifier runtime that are poly-logarithmic in the runtime of the BQP computation (and polynomial in the security parameter). Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning with Errors (LWE). This is the first succinct argument for quantum computation in the plain model; prior work (Chia-Chung-Yamakawa, TCC '20) requires both a long common reference string and non-black-box use of a hash function modeled as a random oracle. At a technical level, we revisit the framework for constructing classically verifiable quantum computation (Mahadev, FOCS '18). We give a self-contained, modular proof of security for Mahadev's protocol, which we believe is of independent interest. Our proof readily generalizes to a setting in which the verifier's first message (which consists of many public keys) is compressed. Next, we formalize this notion of compressed public keys; we view the object as a generalization of constrained/programmable PRFs and instantiate it based on indistinguishability obfuscation. Finally, we compile the above protocol into a fully succinct argument using a (sufficiently composable) succinct argument of knowledge for NP. Using our framework, we achieve several additional results, including - Succinct arguments for QMA (given multiple copies of the witness), - Succinct non-interactive arguments for BQP (or QMA) in the quantum random oracle model, and - Succinct batch arguments for BQP (or QMA) assuming post-quantum LWE (without iO).

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
succinct arguments delegation of computation quantum cryptography
Contact author(s)
bartusek james @ gmail com
yael @ microsoft com
alexjl @ mit edu
fermima @ alum mit edu
giulio malavolta @ hotmail it
vinodv @ mit edu
vidick @ caltech edu
lisayang @ mit edu
History
2022-06-29: approved
See all versions
Short URL
https://ia.cr/2022/857

CC BY-SA

BibTeX

@misc{cryptoeprint:2022/857,
author = {James Bartusek and Yael Tauman Kalai and Alex Lombardi and Fermi Ma and Giulio Malavolta and Vinod Vaikuntanathan and Thomas Vidick and Lisa Yang},
title = {Succinct Classical Verification of Quantum Computation},
howpublished = {Cryptology ePrint Archive, Paper 2022/857},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/857}},
url = {https://eprint.iacr.org/2022/857}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.