Making zero-knowledge provers efficient

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 kappa; (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 ∈ P. Namely, we construct a probabilistic machine with an NP oracle which, on input 1n and δ > 0 runs in time polynomial in n and lg δ-1, and outputs a random string from a distribution within distance δ of the uniform distribution on S ∩ {0,1}n.