Cryptography Reference
InDepth Information
given as auxiliaryinput an NPwitness to the assertion (to be proved).
3
That is:
Theorem 4.2.
((75), using (85; 101)):
If oneway functions exist then
every set
S
has a zeroknowledge interactive proof. Furthermore,
the prescribed prover strategy can be implemented in probabilistic
polynomialtime, provided it is given as auxiliaryinput an NPwitness
for membership of the common input in
S
.
∈NP
Theorem 4.2 makes zeroknowledge a very powerful tool in the design of
cryptographic schemes and protocols (see below). We comment that the
intractability assumption used in Theorem 4.2 seems essential; see (105;
122).
Analyzing the protocol of Figure 4.2.
Let us consider a sin
gle execution of the main loop (and rely on the preservation of
zeroknowledge under sequential composition). Clearly, the prescribed
prover is implemented in probabilistic polynomialtime, and always
convinces the verifier (provided that it is given a valid 3coloring of
the common input graph). In case the graph is not 3colorable then, no
matter how the prover behaves, the verifier will reject with probability
at least 1
/
(because at least one of the edges must be improperly col
ored by the prover). We stress that the verifier selects uniformly which
edge to inspect after the prover has committed to the colors of all ver
tices. Thus, Figure 4.2 depicts an interactive proof system for Graph
3Colorability (with error probability exp(
−t
)). As the reader might
have guessed, the zeroknowledge property is the hardest to establish,

E

3
The auxiliaryinput given to the prescribed prover (in order to allow for an e
cient imple
mentation of its strategy) is not to be confused with the auxiliaryinput that is given to
malicious verifiers (in the definition of auxiliaryinput zeroknowledge). The former is typ
ically an NPwitness for the common input, which is available to the user that invokes the
prover strategy (cf. the generic application discussed below). In contrast, the auxiliary
input that is given to malicious verifiers models arbitrary partial information that may be
available to the adversary.