ECCC-Report TR01-093https://eccc.weizmann.ac.il/report/2001/093Comments and Revisions published for TR01-093en-usMon, 03 Dec 2001 10:03:33 +0200
Paper TR01-093
| Universal Arguments and their Applications |
Boaz Barak,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2001/093
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).
Mon, 03 Dec 2001 10:03:33 +0200https://eccc.weizmann.ac.il/report/2001/093