Technical Report CS0861

Authors: M. Bellare and E. Petrank
Abstract: We look at the question of how powerful a prover must be to give a zero-knowledge proof. We present the first unconditional bounds on the complexity of a statistical ZK prover. The result is that if a language possesses a statistical zero-knowledge then it also possesses a statistical zero-knowledge proof in which the prover runs in probabilistic, polynomial time with an NP oracle. Previously, this was only known given the existence of one-way permutations. Extending these techniques to protocols of knowledge complexity $(k(n) > 0$, we derive bounds on the time complexity of languages of ``small'' knowledge complexity. Underlying these results is a technique for efficiently generating an ``almost'' random element of a set $S \in NP$. Specifically, we construct a probabilistic machine with an NP oracle which, on input $1^n$ and $\delta > 0$ runs in time polynomial in $n$ and $lg \delta^{-1}$, and outputs a random string from a distribution within distance $\delta$ of the uniform distribution on $S \cap \{0,1\}^n$.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion