**Universal Arguments and their Applications**

*Boaz Barak and Oded Goldreich*

**Abstract: **We put forward a new type of
computationally-sound proof systems, called universal-arguments,
which are related but different from both CS-proofs (as defined
by Micali) and arguments (as defined by Brassard, Chaum and
Crepeau). In particular, we adopt the instance-based
prover-efficiency paradigm of CS-proofs, but follow the
computational-soundness condition of argument systems (i.e., we
consider only cheating strategies that are implementable by
polynomial-size circuits).

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 format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20011203:182203 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]