Succinct Classical Verification of Quantum Computation
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).
2-s2.0-85141683733
University of California, Berkeley
Microsoft Research Cambridge
Massachusetts Institute of Technology
University of California, Berkeley
MPI-SP
Massachusetts Institute of Technology
California Institute of Technology
Massachusetts Institute of Technology
2022
Cham
9783031159787
9783031159794
XIX, 824
Lecture Notes in Computer Science; 13508 LNCS
1611-3349
0302-9743
195
211
REVIEWED
OTHER
| Event name | Event acronym | Event place | Event date |
CRYPTO 2022 | Santa Barbara, United States | 2022-08-15 - 2022-08-18 | |
| Funder | Funding(s) | Grant Number | Grant URL |
Analog Devices | |||
Microsoft Trustworthy AI | |||
MURI | FA9550-18-1-0161 | ||
| Show more | |||