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.

- The paper itself, 1991 (revised 1998). [See PDF]

- Since indistinguishablity is defined with respect to
the parameter
**n**, whereas the protocol is only given the input generated based on**n**, a problem may arise if the generated input is much shorter than**n**(i.e., computational zero-knowledge proofs use computational hardness related to the input length). The best solution, which is advocated also regardless of this issue, is to always provide the protocol (as well as the simulator and the distinguisher) with the parameter**n**. (In fact, this is the formulation used in Salil's PhD Thesis.)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. - Insisting that the sampling/generation algorithm always outputs a string in some set may limit the former too much. Things become acute if the desired set is not recognizable in (deterministic) polynomial-time or if it contains no strings of the desired length. An alternative formulation may allow arbitrary outputs but considers only the event in which the output is in the set. For details see Appendix A in Lower Bounds for Non-Black-Box Zero Knowledge (TO BE POSTED SOON, by Barak, Lindell and Vadhan).

Back to either Oded Goldreich's homepage. or general list of papers.