Zero-Knowledge Proof Systems - Foundations of Cryptography: Basic Tools - page 262

4.7. ∗ Proofs of Knowledge

This section addresses the concept of “proofs of knowledge.” Loosely speaking, these
are proofs in which the prover asserts “knowledge” of some object (e.g., a 3-coloring
of a graph) and not merely its existence (e.g., the existence of a 3-coloring of the graph,
which in turn implies that the graph is in the language G 3 C ). But what is meant by
saying that a machine knows something? Indeed, the main thrust of this section is to
address this question. Before doing so, we point out that “proofs of knowledge,” and in
particular zero-knowledge “proofs of knowledge,” have many applications to the design
of cryptographic schemes and cryptographic protocols. Some of these applications
are discussed in Section 4.7.4. Of special interest is the application to identification
schemes, which is discussed in Section 4.7.5. Finally, in Section 4.7.6 we introduce the
notion of strong proofs of knowledge.

4.7.1. Definition
4.7.1.1. A Motivating Discussion

What does it mean to say that a MACHINE knows something? Any standard dictionary
suggests several meanings for the verb to know, and most meanings are phrased with
reference to awareness , a notion that is certainly inapplicable in our context. We must
look for a behavioristic interpretation of the verb to know . Indeed, it is reasonable to
link knowledge with ability to do something, be it (at the least) the ability to write down
whatever one knows. Hence, we shall say that a machine knows a string if it can output

the string α . But this seems total nonsense: 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 means that the machine can be easily modified so
that it will do whatever is claimed. More precisely, it means that there exists an efficient
machine that, using the original machine as a black box, 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 the question of what can be deduced about the knowledge of a machine after
interacting with it. Hence, we are interested in proofs of knowledge (rather than in mere
knowledge).
For the 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 simply to send the
3-coloring to the verifier. Yet we claim that applying Construction 4.4.7 (i.e., the zero-
knowledge proof system for G 3 C ) sufficiently many times results in an alternative way
of proving knowledge of a 3-coloring of the graph.
Loosely speaking, we say that an interactive machine V constitutes a verifier for
knowledge of 3-coloring if the probability that the verifier is convinced by a machine
P to accept the graph G is inversely proportional to the difficulty of extracting a
3-coloring of G when using machine P as a black box. Namely, the extraction of
the 3-coloring is done by an oracle machine, called an extractor , that is given access

α