Cryptography Reference
In-Depth Information
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)).
NP
4.4
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).
4.4.1
Computational soundness
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).
