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 - RevisedCS0685.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.
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 (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.

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

Computer science department, Technion
admin