International Association
for Cryptologic Research

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 a generic quantum computationally-binding bit commitment scheme composed in parallel, which can be viewed as a quantum string commitment scheme. We show that the resulting scheme satisfies a stronger quantum computational binding property than the trivial honest-binding, which we call the 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/statistically-hiding) computationally-binding bit commitment scheme in Blum's zero-knowledge protocol for the NP-complete language Hamiltonian Cycle. Then the quantum computational predicate-binding property of the commitments immediately translates into the quantum computational soundness of the protocol. Combined with the perfect/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/statistical zero-knowledge argument system for all NP languages based solely on quantum-secure one-way functions.