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},
note = {\url{https://eprint.iacr.org/2008/524}},
url = {https://eprint.iacr.org/2008/524}
}
