ent settings. Indeed, this paradigm is the basis for the wide applicability
of zero-knowledge protocols in cryptography.
Zero-knowledge proofs for all IP. For the sake of elegancy, we
mention that under the same assumption used in the case of
it holds that any set that has an interactive proof also has a zero-
knowledge interactive proof (cf. (88; 24)).
Variants and issues
In this section we consider numerous variants on the notion of zero-
knowledge and the underlying model of interactive proofs. These
include computational soundness (cf. Section 4.4.1), black-box simula-
tion and other variants of zero-knowledge (cf. Section 4.4.2), as well as
notions such as proofs of knowledge, non-interactive zero-knowledge,
and witness indistinguishable proofs (cf. Section 4.4.3). We conclude
this section by reviewing relatively recent results regarding the com-
position of zero-knowledge protocols and the power of non-black-box
simulation (cf. Section 4.4.4).
A fundamental variant on the notion of interactive proofs was intro-
duced by Brassard, Chaum and Crepeau (33), who relaxed the sound-
ness condition so that it only refers to feasible ways of trying to fool
the verifier (rather than to all possible ways). Specifically, the sound-
ness condition was replaced by a computational soundness condition
that asserts that it is infeasible to fool the verifier into accepting false
statements. We warn that although the computational-soundness error
can always be reduced by sequential repetitions, it is not true that this
error can always be reduced by parallel repetitions (cf. (21)).
Protocols that satisfy the computational-soundness condition are
called arguments . 5 We mention that argument systems may be more
ecient than interactive proofs (see (90) vs. (69; 78)) as well as provide
stronger zero-knowledge guarantees (see (33) vs. (59; 2)). Specifically,
5 A related notion (not discussed here) is that of CS-proofs, introduced by Micali (99).