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