Cryptology ePrint Archive: Report 2020/1510

Quantum Computationally Predicate-Binding Commitments with Application in Quantum Zero-Knowledge Arguments for NP

Jun Yan

Abstract: A quantum bit commitment scheme is to realize bit (rather than qubit) commitment by exploiting quantum communication and quantum computation. In this work, we study the binding property of the quantum string commitment scheme obtained by composing a generic quantum computationally-binding bit commitment scheme in parallel. We show that the resulting scheme satisfies a stronger quantum computational binding property than the trivial honest-binding, which we call predicate-binding. Intuitively and very roughly, the predicate-binding property guarantees that given any inconsistent predicate pair over a set of strings (i.e. no strings in this set can satisfy both predicates), if a (claimed) quantum commitment can be opened so that the revealed string satisfies one predicate with certainty, then the same commitment cannot be opened so that the revealed string satisfies the other predicate except for a negligible probability.

As an application, we plug a generic quantum perfectly(resp. statistically)-hiding computationally-binding bit commitment scheme in Blumís zero-knowledge protocol for the NP-complete language Hamiltonian Cycle. The quantum computational soundness of the resulting protocol will follow immediately from the quantum computational predicate-binding property of commitments. Combined with the perfect(resp. statistical) zero-knowledge property which can be similarly established as Watrous [Wat09], as well as known constructions of quantum computationally-binding bit commitment scheme, this gives rise to the first quantum perfect(resp. statistical) zero-knowledge argument system for all NP languages merely relying on quantum-secure one-way functions.

Category / Keywords: cryptographic protocols / quantum bit commitment, quantum computational binding, parallel composition, quantum zero-knowledge argument

Date: received 2 Dec 2020, last revised 27 May 2021

Contact author: tjunyan at jnu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20210527:075908 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]