We show that universal-arguments can be constructed based on standard intractability assumptions that refer to polynomial-size circuits (rather than assumptions referring to subexponential-size circuits as used in the construction of CS-proofs). As an application of universal-arguments, we weaken the intractability assumptions used in the recent non-black-box zero-knowledge arguments of Barak. Specifically, we only utilize intractability assumptions that refer to polynomial-size circuits (rather than assumptions referring to circuits of some ``nice'' super-polynomial size).
Category / Keywords: foundations / Probabilistic proof systems, computationally-sound proof systems, Publication Info: Posted also on ECCC. Date: received 2 Dec 2001 Contact author: oded at wisdom weizmann ac il Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Version: 20011203:182203 (All versions of this report) Discussion forum: Show discussion | Start new discussion