Paper 2020/1273

Classical Verification of Quantum Computations with Efficient Verifier

Nai-Hui Chia
Kai-Min Chung
Takashi Yamakawa
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 $\mathsf{QTIME}(T)$ computation in time $\mathsf{poly}(\lambda,\log T)$ where $\lambda$ is the security parameter. For proving soundness, we assume that a standard model instantiation of our two-round protocol with a concrete hash function (say, SHA-3) is sound and the existence of post-quantum indistinguishability obfuscation and post-quantum fully homomorphic encryption in addition to the quantum hardness of the LWE problem.

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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2020/1273}},
      url = {https://eprint.iacr.org/2020/1273}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.