You are looking at a specific version 20081216:124657 of this paper. See the latest version.

Paper 2008/524

Round-Optimal Zero-Knowledge Proofs of Knowledge for NP

Li Hongda and Feng dengguo and 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.