The Round Complexity of Quantum Zero-Knowledge

Orestis Chardouvelis; Giulio Malavolta

Paper 2021/918

The Round Complexity of Quantum Zero-Knowledge

Orestis Chardouvelis and Giulio Malavolta

Abstract

We study the round complexity of zero-knowledge for QMA (the quantum analogue of NP). Assuming the quantum quasi-polynomial hardness of the learning with errors (LWE) problem, we obtain the following results: - 2-Round statistical witness indistinguishable (WI) arguments for QMA. - 4-Round statistical zero-knowledge arguments for QMA in the plain model, additionally assuming the existence of quantum fully homomorphic encryption. This is the first protocol for constant-round statistical zero-knowledge arguments for QMA. - 2-Round computational (statistical, resp.) zero-knowledge for QMA in the timing model, additionally assuming the existence of post-quantum non-parallelizing functions (time-lock puzzles, resp.). All of these protocols match the best round complexity known for the corresponding protocols for NP with post-quantum security. Along the way, we introduce and construct the notions of sometimes-extractable oblivious transfer and sometimes-simulatable zero-knowledge, which might be of independent interest.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: quantum cryptography zero-knowledge timing model
Contact author(s): orestischar @ gmail com
giulio malavolta @ hotmail it
History: 2021-09-17: last of 2 revisions; 2021-07-08: received; See all versions
Short URL: https://ia.cr/2021/918
License: CC BY

BibTeX

@misc{cryptoeprint:2021/918,
      author = {Orestis Chardouvelis and Giulio Malavolta},
      title = {The Round Complexity of Quantum Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2021/918},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/918}},
      url = {https://eprint.iacr.org/2021/918}
}