International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: The Round Complexity of Quantum Zero-Knowledge

Authors:
Orestis Chardouvelis
Giulio Malavolta
Download:
DOI: 10.1007/978-3-030-90459-3_5
Search ePrint
Search Google
Presentation: Slides
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.
Video from TCC 2021
BibTeX
@article{tcc-2021-31543,
  title={The Round Complexity of Quantum Zero-Knowledge},
  booktitle={Theory of Cryptography;19th International Conference},
  publisher={Springer},
  doi={10.1007/978-3-030-90459-3_5},
  author={Orestis Chardouvelis and Giulio Malavolta},
  year=2021
}