Universal Arguments and their Applications

Webpage for a paper by Boaz Barak and Oded Goldreich

Abstract

We put forward a new type of computationally-sound proof systems, called universal-arguments. 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 polynomial-size circuits).

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

The paper itself (1st version), 2001.
A very significant revision of the paper, July 2007. [Additional minor revision: May 2008]
Another important revision: July 2008 [in PDF].
Post-publication revisions: May 2014.

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.

Back to either Oded Goldreich's homepage. or general list of papers.