An Equivalence between Zero Knowledge and Commitments

Abstract. We show that a language in NP has a zero-knowledge proto-col if and only if the language has an “instance-dependent ” commitment scheme. An instance-dependent commitment schemes for a given lan-guage is a commitment scheme that can depend on an instance of the language, and where the hiding and binding properties are required to hold only on the YES and NO instances of the language, respectively. The novel direction is the only if direction. Thus, we confirm the widely held belief that commitments are not only sufficient for zero knowledge protocols, but necessary as well. Previous results of this type either held only for restricted types of protocols or languages, or used nonstandard relaxations of (instance-dependent) commitment schemes.