Paper 2020/1273
Classical Verification of Quantum Computations with Efficient Verifier
Abstract
In this paper, we extend the protocol of classical verification of quantum computations (CVQC) recently proposed by Mahadev to make the verification efficient. Our result is obtained in the following three steps:
- We show that parallel repetition of Mahadev's protocol has negligible soundness error. This gives the first constant round CVQC protocol with negligible soundness error. In this part, we only assume the quantum hardness of the learning with error (LWE) problem similar to Mahadev's work.
- We construct a two-round CVQC protocol in the quantum random oracle model (QROM) where a cryptographic hash function is idealized to be a random function. This is obtained by applying the Fiat-Shamir transform to the parallel repetition version of Mahadev's protocol.
-We construct a two-round CVQC protocol with an efficient verifier in the CRS+QRO model where both prover and verifier can access a (classical) common reference string generated by a trusted third party in addition to quantum access to QRO. Specifically, the verifier can verify a
Note: Fixed typos (10/22/2020) Fixed a minor technical issue (see Footnotes 9 and 11 in pages 16 and 22, respectively). (10/30/2023)
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in TCC 2020
- Keywords
- efficient verification
- Contact author(s)
-
nc67 @ rice edu
kmchung @ iis sinica edu tw
takashi yamakawa @ ntt com - History
- 2023-10-30: last of 2 revisions
- 2020-10-14: received
- See all versions
- Short URL
- https://ia.cr/2020/1273
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1273,
author = {Nai-Hui Chia and Kai-Min Chung and Takashi Yamakawa},
title = {Classical Verification of Quantum Computations with Efficient Verifier},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1273},
year = {2020},
url = {https://eprint.iacr.org/2020/1273}
}
