A Uniform-Complexity Treatment of Encryption and Zero-Knowledge

Webpage for a paper by Oded Goldreich


We provide a treatment of encryption and zero-knowledge in terms of uniform complexity measures. This treatment is appropriate for cryptographic settings modeled by probabilistic polynomial-time machines. Our uniform treatment allows to construct secure encryption schemes and zero-knowledge proof systems (for all NP-sets) using only uniform complexity assumptions.

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 was published in the Journal of Cryptography, Vol. 6, No. 1, pages 21-53, 1993.

Comments by Salil Vadhan

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