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 perfectly(resp. statistically)-hiding computationally-binding bit commitment scheme (which can be realized based on quantum-secure one-way permutations(resp. functions)) in parallel. We show that the resulting scheme satisfies a stronger quantum computational binding property, which we will call predicate-binding, than the trivial honest-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 in previous work, this gives rise to the first quantum perfect(resp. statistical) zero-knowledge argument system (with soundness error 1/2) for all NP languages based solely on quantum-secure one-way permutations(resp. functions).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
quantum bit commitmentquantum computational bindingparallel compositionquantum zero-knowledge argument
Contact author(s)
tjunyan @ jnu edu cn
History
2021-09-21: last of 9 revisions
2020-12-02: received
See all versions
Short URL
https://ia.cr/2020/1510
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1510,
      author = {Jun Yan},
      title = {Quantum Computationally Predicate-Binding Commitments with Application in Quantum Zero-Knowledge Arguments for NP},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1510},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1510}},
      url = {https://eprint.iacr.org/2020/1510}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.