Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Succinct Classical Verification of Quantum Computation
 
conference paper

Succinct Classical Verification of Quantum Computation

Bartusek, James
•
Kalai, Yael Tauman
•
Lombardi, Alex
Show more
Dodis, Yevgeniy
•
Shrimpton, Thomas
2022
Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings. Part II
42nd Annual International Cryptology Conference (CRYPTO 2022)

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).

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-031-15979-4_7
Scopus ID

2-s2.0-85141683733

Author(s)
Bartusek, James

University of California, Berkeley

Kalai, Yael Tauman

Microsoft Research Cambridge

Lombardi, Alex

Massachusetts Institute of Technology

Ma, Fermi

University of California, Berkeley

Malavolta, Giulio

MPI-SP

Vaikuntanathan, Vinod

Massachusetts Institute of Technology

Vidick, Thomas  orcid-logo

California Institute of Technology

Yang, Lisa

Massachusetts Institute of Technology

Editors
Dodis, Yevgeniy
•
Shrimpton, Thomas
Date Issued

2022

Publisher

Springer Science and Business Media Deutschland GmbH

Publisher place

Cham

Published in
Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings. Part II
DOI of the book
https://doi.org/10.1007/978-3-031-15979-4
ISBN of the book

9783031159787

9783031159794

Total of pages

XIX, 824

Series title/Series vol.

Lecture Notes in Computer Science; 13508 LNCS

ISSN (of the series)

1611-3349

0302-9743

Start page

195

End page

211

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
Event nameEvent acronymEvent placeEvent date
42nd Annual International Cryptology Conference (CRYPTO 2022)

CRYPTO 2022

Santa Barbara, United States

2022-08-15 - 2022-08-18

FunderFunding(s)Grant NumberGrant URL

Analog Devices

Microsoft Trustworthy AI

MURI

FA9550-18-1-0161

Show more
Available on Infoscience
November 18, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/255969
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés