Cryptology ePrint Archive: Report 2010/656

A Note on Constant-Round Zero-Knowledge Proofs of Knowledge

Yehuda Lindell

Abstract: In this note, we show the existence of \emph{constant-round} computational zero-knowledge \emph{proofs of knowledge} for all $\NP$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge \emph{arguments} of knowledge was proven by Feige and Shamir (CRYPTO 1989). However, the existence of constant-round zero-knowledge proofs of knowledge for all $\NP$ is folklore, to the best of our knowledge, since no proof of this fact has been published.

Category / Keywords: foundations / zero-knowledge proofs, proofs of knowledge, constant number of rounds

Date: received 26 Dec 2010, last revised 24 Sep 2012

Contact author: lindell at cs biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20120924:192139 (All versions of this report)

Short URL: ia.cr/2010/656

Discussion forum: Show discussion | Start new discussion