Cryptology ePrint Archive: Report 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 security against classical adversaries. 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.

Category / Keywords: cryptographic protocols / quantum cryptography, zero-knowledge, timing model

Date: received 7 Jul 2021, last revised 12 Jul 2021

Contact author: orestischar at gmail com, giulio malavolta@hotmail it

Available format(s): PDF | BibTeX Citation

Version: 20210712:110300 (All versions of this report)

Short URL: ia.cr/2021/918


[ Cryptology ePrint archive ]