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

Knowledge versus Information
We wish to stress that knowledge (as discussed here) is very different from informa-
tion (in the sense of information theory). Two major aspects of the difference are as
follows:
1. Knowledge is related to computational difficulty, whereas information is not. In the
foregoing examples, there is a difference between the knowledge revealed in the case in
which Alice answers questions of the form “Is the graph Eulerian?” and the case in which
she answers questions of the form “Is the graph Hamiltonian?” From an information-
theory point of view there is no difference between the two cases (i.e., in each case the
answer is determined by the question, and so Bob gets no information).
2. Knowledge relates mainly to publicly known objects, whereas information relates mainly
to objects on which only partial information is publicly known. Consider the case in
which Alice answers each question by flipping an unbiased coin and telling Bob the
outcome. From an information-theoretic point of view, Bob gets from Alice information
concerning an event. However, we say that Bob gains no knowledge from Alice , because
he could toss coins by himself.
4.2. Interactive Proof Systems
In this section we introduce the notion of an interactive proof system and present a
non-trivial example of such a system (specifically to claims of the form “the following
two graphs are not isomorphic”). The presentation is directed toward the introduction
of zero-knowledge interactive proofs. Interactive proof systems are interesting for their
own sake and have important complexity-theoretic applications. 3
4.2.1. Definition
The definition of an interactive proof system refers explicitly to the two computational
tasks related to a proof system: “producing” a proof and verifying the validity of a
proof. These tasks are performed by two different parties, called the prover and the
verifier , which interact with one another. In some cases, the interaction may be very
simple and, in particular, unidirectional (i.e., the prover sends a text, called the proof,
to the verifier). In general, the interaction may be more complex and may take the
form of the verifier interrogating the prover. We start by defining such an interrogation
process.
4.2.1.1. Interaction
Interaction between two parties is defined in the natural manner. The only point worth
noting is that the interaction is parameterized by a common input (given to both parties).
In the context of interactive proof systems, the common input represents the statement
to be proved. We first define the notion of an interactive machine and next the notion
3 See the suggestions for further reading at the end of the chapter.