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)
- 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
-
CC BY