[Resource Topic] 2021/918: The Round Complexity of Quantum Zero-Knowledge

Welcome to the resource topic for 2021/918

The Round Complexity of Quantum Zero-Knowledge

Authors: Orestis Chardouvelis, Giulio Malavolta


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.

ePrint: https://eprint.iacr.org/2021/918

Talk: https://www.youtube.com/watch?v=9t6bMyY2TjY

Slides: https://iacr.org/submit/files/slides/2021/tcc/tcc2021/208/slides.pdf

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .