# Technical Report CS0685

 TR#: CS0685 Class: CS Title: A UNIFORM-COMPLEXITY TREATMENT OF ENCRYPTION AND ZERO-KNOWLEDGE (Revised Version of TR 568 \& 627) Authors: O. Goldreich PDF - Revised CS0685.revised.pdf Abstract: 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 {\bf 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. 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 {\em all} instances. For practical purposes, it suffices to require that it is {\em 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 {\bf NP}, using only a uniform complexity assumption. Properties of uniformly zero-knowledge proofs are investigated and their utility is demonstrated. Copyright The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0685), rather than to the URL of the PDF files directly. The latter URLs may change without notice.