Cryptography Reference
In-Depth Information
4.1.2. Gaining Knowledge
Recall that we have motivated zero-knowledge proofs as proofs by which the verifier
gains “no knowledge” (beyond the validity of the assertion). The reader may rightfully
wonder what knowledge is and what a gain in knowledge is. When discussing zero-
knowledge proofs, we avoid the first question (which is quite complex) and treat the
second question directly. Namely,
without
presenting a definition of knowledge, we
present a generic case in which it is certainly justified to say that no knowledge is
gained. Fortunately, this approach seems to suffice as far as cryptography is concerned.
To motivate the definition of zero-knowledge, consider a conversation between two
parties,
Alice
and
Bob
. Assume first that this conversation is unidirectional; specifi-
cally,
Alice
only talks, and
Bob
only listens. Clearly, we can say that
Alice
gains
no knowledge from the conversation. On the other hand,
Bob
may or may not gain
knowledge from the conversation (depending on what
Alice
says). For example,
if all that
Alice
says is “1
2,” then clearly
Bob
gains no knowledge from
the conversation, because he already knows that fact. If, on the other hand,
Alice
reveals to
Bob
a proof that
+
1
=
P
=
NP
, then he certainly gains knowledge from the
conversation.
To give a better flavor of the definition, we now consider a conversation between
Alice
and
Bob
in which
Bob
asks
Alice
questions about a large graph (that is known
to both of them). Consider first the case in which
Bob
asks
Alice
whether or not
the graph
1
is Eulerian. Clearly,
Bob
gains no knowledge from
Alice
's answer, be-
cause he could easily have determined the answer by himself (by running a linear-
time decision procedure
2
). On the other hand, if
Bob
asks
Alice
whether or not the
graph is Hamiltonian, and
Alice
(somehow) answers this question, then we cannot
say that
Bob
has gained no knowledge (because we do not know of an efficient pro-
cedure by which
Bob
could have determined the answer by himself, and assuming
P
=
NP
, no such efficient procedure exists). Hence, we say that
Bob
has gained
knowledge
from the interaction if his
computational ability
, concerning the publicly
known graph,
has increased
(i.e., if after the interaction he can easily compute some-
thing that he could not have efficiently computed before the interaction). On the other
hand, if whatever
Bob
can efficiently compute about the graph
after interacting
with
Alice
he can also efficiently compute
by himself
(from the graph), then we say that
Bob
has gained no knowledge
from the interaction. That is,
Bob
gains knowledge
only if he receives the result of a computation that is infeasible for him. The question
of how
Alice
could conduct this infeasible computation (e.g., answer
Bob
's ques-
tion of whether or not the graph is Hamiltonian) has been ignored thus far. Jumping
ahead, we remark that
Alice
may be a mere abstraction or may be in possession
of additional hints that enable her to efficiently conduct computations that are other-
wise infeasible (and in particular are infeasible for
Bob
, who does not have these
hints).
1
See Footnote 13.
2
For example, by relying on Euler's theorem, which asserts that a graph is Eulerian if and only if it is connected
and all its vertices have even degrees.
