| TR#: | CS0861 |
| Class: | CS |
| Title: | MAKING ZERO-KNOWLEDGE PROVERS
EFFICIENT. |
| Authors: | M. Bellare and E. Petrank |
| 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.
To the list of the CS technical reports of 1995
To the main CS technical reports page