International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Universal Arguments and their Applications

Authors:
Boaz Barak
Oded Goldreich
Download:
URL: http://eprint.iacr.org/2001/105
Search ePrint
Search Google
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).
BibTeX
@misc{eprint-2001-11517,
  title={Universal Arguments and their Applications},
  booktitle={IACR Eprint archive},
  keywords={foundations / Probabilistic proof systems, computationally-sound proof systems,},
  url={http://eprint.iacr.org/2001/105},
  note={Posted also on ECCC. oded@wisdom.weizmann.ac.il 11658 received 2 Dec 2001},
  author={Boaz Barak and Oded Goldreich},
  year=2001
}