Zero-Knowledge - Foundations of Cryptography-A Primer - page 48

astring α if it can output the string α . But this seems total non-sense
too: a machine has a well-defined output - either the output equals α
or it does not. So what can be meant by saying that a machine can
do something? Loosely speaking, it may mean that the machine can
be easily modified so that it does whatever is claimed. More precisely,
it may mean that there exists an ecient machine that, using the
original machine as a black-box (or given its code as an input), outputs
whatever is claimed.
So much for defining the “knowledge of machines”. Yet, whatever
a machine knows or does not know is “its own business”. What can
be of interest and reference to the outside is whatever can be deduced
about the knowledge of a machine by interacting with it. Hence, we
are interested in proofs of knowledge (rather than in mere knowledge).
For sake of simplicity let us consider a concrete question: how can a
machine prove that it knows a 3-coloring of a graph? An obvious way is
just to send the 3-coloring to the verifier. Yet, we claim that applying
the protocol in Figure 4.2 (i.e., the zero-knowledge proof system for 3-
Colorability) is an alternative way of proving knowledge of a 3-coloring
of the graph.
The definition of a verifier of knowledge of 3-coloring refers to any
possible prover strategy. It requires the existence of an ecient uni-
versal way of “extracting” a 3-coloring of a given graph by using any
prover strategy that convinces the verify to accept the graph (with
noticeable probability). Surely, we should not expect much of prover
strategies that convince the verifier to accept the graph with negligible
probability. However, a robust definition should allow a smooth passage
from noticeable to negligible, and should allow to establish the intuitive
zero-knowledge property of a party that sends some information that
the other party has proved it knows.
Loosely speaking, we may say that an interactive machine, V ,con-
stitutes a verifier for knowledge of 3-coloring if, for any prover strategy
P , the complexity of extracting a 3-coloring of G when using machine
P as a “black box” 8 is inversely proportional to the probability that
the verifier is convinced by P (to accept the graph G ). Namely, the
8 Indeed, one may also consider non-black-box extractors as done in (12).