|
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 2 NP. Specifically, we construct a probabilistic machine with an NP oracle which, on input 1 n, |
