You are looking at a specific version 20210712:110300 of this paper. See the latest version.

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 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
quantum cryptographyzero-knowledgetiming 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.