On the Concurrent Composition of Quantum Zero-Knowledge

Prabhanjan Ananth; Kai-Min Chung; Rolando L.  La Placa

Paper 2020/1528

On the Concurrent Composition of Quantum Zero-Knowledge

Prabhanjan Ananth, Kai-Min Chung, and Rolando L. La Placa

Abstract

We study the notion of zero-knowledge secure against quantum polynomial-time verifiers (referred to as quantum zero-knowledge) in the concurrent composition setting. Despite being extensively studied in the classical setting, concurrent composition in the quantum setting has hardly been studied. We initiate a formal study of concurrent quantum zero-knowledge. Our results are as follows: - Bounded Concurrent QZK for NP and QMA: Assuming post-quantum one-way functions, there exists a quantum zero-knowledge proof system for NP in the bounded concurrent setting. In this setting, we fix a priori the number of verifiers that can simultaneously interact with the prover. Under the same assumption, we also show that there exists a quantum zero-knowledge proof system for QMA in the bounded concurrency setting. - Quantum Proofs of Knowledge: Assuming quantum hardness of learning with errors (QLWE), there exists a bounded concurrent zero-knowledge proof system for NP satisfying quantum proof of knowledge property. Our extraction mechanism simultaneously allows for extraction probability to be negligibly close to acceptance probability (extractability) and also ensures that the prover's state after extraction is statistically close to the prover's state after interacting with the verifier (simulatability). The seminal work of [Unruh EUROCRYPT'12], and all its followups, satisfied a weaker version of extractability property and moreover, did not achieve simulatability. Our result yields a proof of quantum knowledge system for QMA with better parameters than prior works.

Note: quantum pok result is now based on QLWE (earlier it was based on a stronger assumption)

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: zero-knowledge quantum cryptography
Contact author(s): prabhanjan va @ gmail com
History: 2021-01-11: last of 4 revisions; 2020-12-08: received; See all versions
Short URL: https://ia.cr/2020/1528
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1528,
      author = {Prabhanjan Ananth and Kai-Min Chung and Rolando L.  La Placa},
      title = {On the Concurrent Composition of Quantum Zero-Knowledge},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1528},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1528}
}