# Technical Report CS0861

 TR#: CS0861 Class: CS Title: MAKING ZERO-KNOWLEDGE PROVERS EFFICIENT. Authors: M. Bellare and E. Petrank PDF CS0861.pdf 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$. Copyright The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0861), rather than to the URL of the PDF files directly. The latter URLs may change without notice.