Round-Optimal Zero-Knowledge Proofs of Knowledge for NP

Li Hongda; Feng dengguo; Li Bao; Xue Haixia

Paper 2008/524

Round-Optimal Zero-Knowledge Proofs of Knowledge for NP

Li Hongda, Feng dengguo, Li Bao, and Xue Haixia

Abstract

It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are non-constant-round. Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is a open problem. This paper focuses on the problem and give a positive answer by presenting two constructions of constant-round (black-box) zero-knowledge proofs of knowledge for the HC (Hamiltonian Cycle) problem. By the recent result of Katz, our second construction which relies on the existence of claw-free functions has optimal round complexity (5-round) assuming the polynomial hierarchy does not collapse.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: zero knowledge
Contact author(s): hdli @ gucas ac cn
History: 2008-12-16: received
Short URL: https://ia.cr/2008/524
License: CC BY

BibTeX

@misc{cryptoeprint:2008/524,
      author = {Li Hongda and Feng dengguo and Li Bao and Xue Haixia},
      title = {Round-Optimal Zero-Knowledge Proofs of Knowledge for {NP}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/524},
      year = {2008},
      url = {https://eprint.iacr.org/2008/524}
}