Paper 2001/105

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).

Metadata
Available format(s)
PS
Category
Foundations
Publication info
Published elsewhere. Posted also on ECCC.
Keywords
Probabilistic proof systemscomputationally-sound proof systems
Contact author(s)
oded @ wisdom weizmann ac il
History
2001-12-03: received
Short URL
https://ia.cr/2001/105
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/105,
      author = {Boaz Barak and Oded Goldreich},
      title = {Universal Arguments and their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2001/105},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/105}},
      url = {https://eprint.iacr.org/2001/105}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.