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).
Versions
Powerpoint XP presentation
home | research | links | cv | pictures
|