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