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.
To the list of the CS technical reports of 1991
To the main CS technical reports page