Universal Arguments and their Applications
Webpage for a paper by Boaz Barak and Oded Goldreich
We put forward a new type of computationally-sound proof systems,
Universal-arguments are related but different from both CS-proofs
(as defined by Micali [SICOMP, Vol. 37, pages 1253--1298, 2000])
and arguments (as defined by Brassard, Chaum, and Crepeau
[JCSS, Vol. 37, pages 156--189, 1988]).
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
We show that universal-arguments can be constructed based on standard
intractability assumptions that refer to polynomial-size circuits
(rather than based on assumptions that refer to subexponential-size
circuits as used in the construction of CS-proofs).
Furthermore, these protocols have a constant number of rounds
and are of the public-coin type.
As an application of these universal-arguments,
we weaken the intractability assumptions used in
the non-black-box zero-knowledge arguments of Barak [42nd FOCS, 2001].
Specifically, we only utilize intractability
assumptions that refer to polynomial-size circuits
(rather than assumptions that refer to circuits
of some ``nice'' super-polynomial size).
Material available on-line
COMMENT (July 2007):
The current version differs from prior versions
of this paper mainly in Section 4.1
The presentation in prior versions
relied on the existence of constant-round, public-coin
strong-WI proofs-of-knowledge for any NP set.
Unfortunately, in contrary to prior misconceptions,
such protocols are not known to exist.
Indeed, this gap can be bypassed - as done in Barak's PhD thesis
and in the current version, by using a rather ugly patch -
but our hope was to bridge the gap
(i.e., prove the existence of the said strong-WI protocols)
and maintain the original presentation.
Having failed to do so for several years,
we decided to archive the current version.
COMMENT (July 2008):
The current version corrects a marginal error regarding non-oblivious
commitment schemes; see discussion in Apdx B.
COMMENT (May 2014):
The current version corrects a minor error regarding Claim 3.5.1.
either Oded Goldreich's homepage.
or general list of papers.