Paper 2023/421
Interactive Oracle Arguments in the QROM and Applications to Succinct Verification of Quantum Computation
, Boston UniversityAbstract
This work is motivated by the following question: can an untrusted quantum server convince a classical verifier of the answer to an efficient quantum computation using only polylogarithmic communication? We show how to achieve this in the quantum random oracle model (QROM), after a non-succinct instance-independent setup phase. We introduce and formalize the notion of post-quantum interactive oracle arguments for languages in QMA, a generalization of interactive oracle proofs (Ben-Sasson-Chiesa-Spooner). We then show how to compile any non-adaptive public-coin interactive oracle argument (with private setup) into a succinct argument (with setup) in the QROM. To conditionally answer our motivating question via this framework under the post-quantum hardness assumption of LWE, we show that the ZX local Hamiltonian problem with at least inverse-polylogarithmic relative promise gap has an interactive oracle argument with instance-independent setup, which we can then compile. Assuming a variant of the quantum PCP conjecture that we introduce called the weak ZX quantum PCP conjecture, we obtain a succinct argument for QMA (and consequently the verification of quantum computation) in the QROM (with non-succinct instance-independent setup) which makes only black-box use of the underlying cryptographic primitives.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. The Cryptographers' Track at RSA Conference (CT-RSA 2024)
- Keywords
- succinct argumentsinteractive oracle proofsdelegation of quantum computationQROMBQPQMA
- Contact author(s)
- islam @ bu edu
- History
- 2024-02-24: last of 2 revisions
- 2023-03-23: received
- See all versions
- Short URL
- https://ia.cr/2023/421
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2023/421,
author = {Islam Faisal},
title = {Interactive Oracle Arguments in the QROM and Applications to Succinct Verification of Quantum Computation},
howpublished = {Cryptology ePrint Archive, Paper 2023/421},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/421}},
url = {https://eprint.iacr.org/2023/421}
}
