Technical Report CS0627

TR#:CS0627
Class:CS
Title: A UNIFORM-COMPLEXITY TREATMENT OF ENCRYPTION AND ZERO-KNOWLEDGE (Revised Version of TR568)
Authors: Oded Go1dreich
PDFCS0627.pdf
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 modeled by probabilistic polynomial-time machines and that they have access only to objects generated by probabilistic polynomial-time procedures. The advantage in our ~pproach 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 wolk of Goldwasser and Micali. are in fact equivalent. Such a result was known before only for the non-uniform formalization [fdRS]. Non-uniformity is implicit in all previous treatments of zero knowledge in the sense that a zeroknowledge 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 wodes (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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1990/CS/CS0627), 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 1990
To the main CS technical reports page

Computer science department, Technion
admin