Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-003 | 19th September 2012 12:32

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

RSS-Feed




Revision #1
Authors: Yehuda Lindell
Accepted on: 19th September 2012 12:32
Downloads: 851
Keywords: 


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.



Changes to previous version:

Fixed some small errors; simplified the proof a little.


Paper:

TR11-003 | 10th January 2011 11:43

Constant-Round Zero-Knowledge Proofs of Knowledge





TR11-003
Authors: Yehuda Lindell
Publication: 10th January 2011 13:23
Downloads: 1187
Keywords: 


Abstract:

In this note, we show the existence of \emph{constant-round} computational zero-knowledge \emph{proofs of knowledge} for all $\cal 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). Although it is widely believed that there exist constant-round zero-knowledge proofs of knowledge for all $\cal NP$, to the best of our knowledge, no proof of this fact has been published.



ISSN 1433-8092 | Imprint