A Uniform-Complexity Treatment of Encryption and Zero-Knowledge

Webpage for a paper by Oded Goldreich

Abstract

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.

Material available on-line

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

Comments by Salil Vadhan

• 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).