About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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.