Succinct Classical Verification of Quantum Computation

James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, Lisa Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

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, andSuccinct batch arguments for BQP (or QMA) assuming post-quantum LWE (without iO).

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
EditorsYevgeniy Dodis, Thomas Shrimpton
PublisherSpringer Science and Business Media Deutschland GmbH
Pages195-211
Number of pages17
ISBN (Print)9783031159787
DOIs
StatePublished - 2022
Externally publishedYes
Event42nd Annual International Cryptology Conference, CRYPTO 2022 - Santa Barbara, United States
Duration: Aug 15 2022Aug 18 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13508 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference42nd Annual International Cryptology Conference, CRYPTO 2022
Country/TerritoryUnited States
CitySanta Barbara
Period8/15/228/18/22

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Succinct Classical Verification of Quantum Computation'. Together they form a unique fingerprint.

Cite this