Cryptography Reference
In-Depth Information
given as auxiliary-input an NP-witness to the assertion (to be proved).
3
That is:
Theorem 4.2.
((75), using (85; 101)):
If one-way functions exist then
every set
S
has a zero-knowledge interactive proof. Furthermore,
the prescribed prover strategy can be implemented in probabilistic
polynomial-time, provided it is given as auxiliary-input an NP-witness
for membership of the common input in
S
.
∈NP
Theorem 4.2 makes zero-knowledge 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
zero-knowledge under sequential composition). Clearly, the prescribed
prover is implemented in probabilistic polynomial-time, and always
convinces the verifier (provided that it is given a valid 3-coloring of
the common input graph). In case the graph is not 3-colorable 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
3-Colorability (with error probability exp(
−t
)). As the reader might
have guessed, the zero-knowledge property is the hardest to establish,
|
E
|
3
The auxiliary-input 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 auxiliary-input that is given to
malicious verifiers (in the definition of auxiliary-input zero-knowledge). The former is typ-
ically an NP-witness 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.
