Cryptography Reference
In-Depth Information
tour by himself, as follows: First, he selects north or south (as he does in the
real guided tour) and goes to the suitable gate (from outside the labyrinth). Next,
he takes a random walk from the gate to inside the labyrinth while unrolling a
spool of thread behind him, and finally he traces the thread back to the gate. (A
sufficiently long random walk whose length equals the length of the tour guided
by Petra will guarantee that Virgil will visit a random place in the labyrinth, and
the way back will look like a random walk from the location at the end of his
thread to the chosen gate.)
We now get back to the formal exposition.
Construction 4.3.8 (A Perfect Zero-Knowledge Proof for Graph Isomor-
phism):
Common input:
A pair of two graphs, G
1
=
(
V
1
,
E
1
)
and G
2
=
(
V
2
,
E
2
)
. Let
φ
be an isomorphism between the input graphs; namely,
φ
is a
1-1
and onto
mapping of the vertex set V
1
to the vertex set V
2
such that
(
u
,v
)
∈
E
1
if and only
if
(
φ
(
v
)
,φ
(
u
))
∈
E
2
.
Prover's first step (P1):
The prover selects a random isomorphic copy of G
2
and
sends it to the verifier. Namely, the prover selects at random, with uniform prob-
ability distribution, a permutation
from the set of permutations over the vertex
set V
2
and constructs a graph with vertex set V
2
and edge set
π
def
={
F
(
π
(
u
)
,π
(
v
)) : (
u
,v
)
∈
E
2
}
The prover sends
(
V
2
,
F
)
to the verifier.
Motivating remark:
If the input graphs are isomorphic, as the prover claims, then
the graph sent in Step P1 is isomorphic to both input graphs. However, if the input
graphs are not isomorphic, then no graph can be isomorphic to both of them.
Verifier's first step (V1):
Upon receiving a graph G
=
E
)
from the prover,
the verifier asks the prover to show an isomorphism between G
and one of the
input graphs, chosen at random by the verifier. Namely, the verifier uniformly
selects
(
V
,
and sends it to the prover (who is supposed to answer with an
isomorphism between G
σ
and G
).
σ
∈{
1
,
2
}
Prover's second step (P2):
If the message
σ
received from the verifier equals
2
, then
the prover sends
π
to the verifier. Otherwise (i.e.,
σ
=
2
), the prover sends
π
◦
φ
)
def
(i.e., the composition of
π
on
φ
, defined as
π
◦
φ
(
v
=
π
(
φ
(
v
))
) to the verifier.
(Remark: The prover treats any
σ
=
2
as
σ
=
1
.)
ψ
Verifier's second step (V2):
If the message, denoted
, received from the prover
is an isomorphism between G
σ
and G
,
then the verifier outputs
1;
otherwise it
outputs
0
.
Let us denote the prover's program by P
GI
.
The verifier program just presented is easily implemented in probabilistic polynomial
time. In case the prover is given an isomorphism between the input graphs as auxiliary
input, the prover's program can also be implemented in probabilistic polynomial time.
We now show that this pair of interactive machines constitutes a
zero-knowledge
inter-
active proof system (in the general sense) for the language
GI
(Graph Isomorphism).
