Technical Report CS0568

Title: A Uniform Complexity Treatment of Encryption and Zero-Knowledge
Authors: Oded Goldreich
Abstract: We provide a treatment of encryption and zero-knowledge in terms of uniform complexity measures. This treatment is justified by our belief that all parties in a cryptographic setting should be modelled by probabilistic polynomial-time machines and that they have access only to objects generated by probabilistic polynomial-time procedures. The advantage in our approach is that it allows to construct secure encryption schemes and zero-knowledge proof systems (for all NP) 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 [MRS]. 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 main contribution of this work is in the rigorous demonstration that encryption and zero-knowledge can be treated in terms of uniform complexity and that such a treatment suffices for the practical applications considered in previous works (e.g. [GMW2]).
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion