Cryptography Reference
In-Depth Information
protocols that are zero-knowledge with respect to the honest verifier can be transformed
into similar protocols that are zero-knowledge in general. We stress that in the current
context (of the single prescribed verifier) the formulations of
output simulatability
(as
in Definition 4.3.2) and
view simulatability
(as in Definition 4.3.3) are
NOT
equivalent,
and it is important to use the latter.
9
Definition 4.3.7 (Zero-Knowledge with Respect to an Honest Verifier):
Let
(
P
,
V
)
, L, and
view
V
(
x
)
be as in Definition 4.3.3. We say that
(
P
,
V
)
is
honest-
verifier zero-knowledge
if there exists a probabilistic polynomial-time algorithm
M such that the ensembles
{
view
V
(
x
)
}
x
∈
L
and
{
M
(
x
)
}
x
∈
L
are computationally
indistinguishable.
The preceding definition refers to computational zero-knowledge and is a restriction
of Definition 4.3.3. Versions for perfect and statistical zero-knowledge are defined
analogously.
PZK
4.3.2. An Example (Graph Isomorphism in
)
As mentioned earlier, every language in
has a trivial (i.e., degenerate) zero-
knowledge proof system. We now present an example of a non-degenerate zero-
knowledge proof system. Furthermore, we present a zero-knowledge proof system for
a language not known to be in
BPP
. Specifically, the language is the set of
pairs of iso-
morphic graphs
, denoted
GI
(see definition in Section 4.2). Again, the idea underlying
this proof system is presented through a story:
In this story, Petra von Kant claims that there is a footpath between the north gate
and the south gate of her labyrinth (i.e., a path going inside the labyrinth). Virgil
does not believe her. Petra is willing to prove her claim to Virgil, but does not
want to provide him any additional knowledge (and, in particular, not to assist
him to find an inside path from the north gate to the south gate). To prove her
claim, Petra and Virgil repeat the following process a number of times sufficient
to convince Virgil beyond reasonable doubt.
Petra miraculously transports Virgil to a random place in her labyrinth. Then
Virgil asks to be shown the way to either the north gate or the south gate. His choice
is supposed to be random, but he may try to cheat. Petra then chooses a (sufficiently
long) random walk from their current location to the desired destination and guides
Virgil along that walk.
Clearly, if the labyrinth has a path as claimed (and Petra knows her way in the
labyrinth), then Virgil will be convinced of the validity of her claim. If, on the
other hand, the labyrinth has no such path, then at each iteration, with probability
at least 50%, Virgil will detect that Petra is lying. Finally, Virgil will gain no
knowledge from the guided tour, the reason being that he can simulate a guided
BPP
9
Note that for any interactive proof of perfect completeness, the output of the honest verifier is trivially
simulatable (by an algorithm that always outputs 1). In contrast, many of the negative results presented in Section 4.5
also apply to zero-knowledge with respect to an honest verifier, as defined next. For example, only languages in
BPP
have
unidirectional
proof systems that are zero-knowledge with respect to an honest verifier.
