TR01-093 Authors: Boaz Barak, Oded Goldreich

Publication: 3rd December 2001 10:03

Downloads: 2750

Keywords:

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).