Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

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

Revision #1
Authors: Yehuda Lindell
Accepted on: 19th September 2012 12:32
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
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.