Paper 2022/857

Succinct Classical Verification of Quantum Computation

James Bartusek, University of California, Berkeley
Yael Tauman Kalai, Microsoft Research, Massachusetts Institute of Technology
Alex Lombardi, Massachusetts Institute of Technology
Fermi Ma, University of California, Berkeley, Simons Institute
Giulio Malavolta, Max Planck Institute for Security and Privacy
Vinod Vaikuntanathan, Massachusetts Institute of Technology
Thomas Vidick, California Institute of Technology
Lisa Yang, Massachusetts Institute of Technology
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).

Metadata
Available format(s)
PDF
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
2022-06-28: received
See all versions
Short URL
https://ia.cr/2022/857
License
Creative Commons Attribution-ShareAlike
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.