Cryptography Reference
In-Depth Information
cific application, it is typically very hard to classify the set of “harmful
breakings”.
4.2
The actual definition
A proof is whatever convinces me.
Shimon Even (1935-2004)
Before defining zero-knowledge proofs, we have to define proofs. The
standard notion of a static (i.e., non-interactive) proof will not do,
because static zero-knowledge proofs exist only for sets that are easy
to decide (i.e, are in
) (76), whereas we are interested in zero-
knowledge proofs for arbitrary NP-sets. Instead, we use the notion of
an interactive proof (introduced exactly for that reason in (81)). That
is, here a proof is a (multi-round) randomized protocol for two parties,
called
verifier
and
prover
, in which the prover wishes to convince the
verifier of the validity of a given assertion. Such an
interactive proof
should allow the prover to convince the verifier of the validity of any
true assertion (i.e.,
completeness
), whereas no prover strategy may fool
the verifier to accept false assertions (i.e.,
soundness
). Both the
com-
pleteness
and
soundness
conditions should hold with high probability
(i.e., a negligible error probability is allowed). The prescribed verifier
strategy is required to be ecient. No such requirement is made with
respect to the prover strategy; yet we will be interested in “relatively
ecient” prover strategies (see below).
1
BPP
1
We stress that the relative eciency of the prover strategy refers to the strategy employed
in order to prove valid assertions; that is, relative eciency of the prover strategy is a
strengthening
of the completeness condition (which is indeed
required
for cryptographic
applications). This should not be confused with the relaxation (i.e., weakening) of the
soundness condition that restricts its scope to feasible adversarial prover strategies (rather
than to all possible prover strategies). The resulting notion of “computational soundness”
is discussed in Section 4.4.1, and indeed
su
ces
in most cryptographic applications. Still,
we believe that it is simpler to present the material in terms of interactive proofs (rather
than in terms of computationally sound proofs).
