We show that uniform variants of the two definitions of security, presented in the pioneering work of Goldwasser and Micali, are in fact equivalent. Such a result was known before only for the non-uniform formalization.
Non-uniformity is implicit in all previous treatments of zero-knowledge in the sense that a zero-knowledge proof is required to ``leak no knowledge'' on all instances. For practical purposes, it suffices to require that it is infeasible to find instances on which a zero-knowledge proof ``leaks knowledge''. We show how to construct such zero-knowledge proof systems for every language in NP, using only a uniform complexity assumption. Properties of uniformly zero-knowledge proofs are investigated and their utility is demonstrated.
An alternative solution is to require the sampling/generation algorithm to output strings of length (say) at least n, when fed with that value. This makes the following point more acute.