Cryptography Reference
In-Depth Information
1.
If G
1
and G
2
are not isomorphic (i.e.,
(
G
1
,
G
2
)
∈
G N I ), then the verifier always
accepts (when interacting with the prover).
2.
If G
1
and G
2
are isomorphic (i.e.,
(
G
1
,
G N I ), then no matter with what
machine the verifier interacts, it rejects the input with probability at least
G
2
)
∈
1
2
.
Proof:
Clearly, if
G
1
and
G
2
are not isomorphic, then no graph can be isomorphic
to both
G
1
and
G
2
. It follows that there exists a unique
τ
such that the graph
G
(received by the prover in Step P1) is isomorphic to the input graph
G
τ
. Hence,
τ
found by the prover in Step P1 always equals
σ
chosen in Step V1. Part 1 follows.
On the other hand, if
G
1
and
G
2
are isomorphic, then the graph
G
is isomorphic
to both input graphs. Furthermore, we shall show that in this case the graph
G
yields no information about
σ
, and consequently no machine can (on input
G
1
,
G
2
and
G
) set
τ
such that it will equal
σ
with probability greater than
1
2
. Details
follow.
Let
π
be a permutation on the vertex set of a graph
G
=
(
V
,
E
). We denote by
π
(
G
) the graph with vertex set
V
and edge set
{
(
π
(
u
)
,π
(
v
)):(
u
,v
)
∈
E
}
. Let
ξ
be a random
variable uniformly distributed over the set of permutations on
V
. We stress that
these two random variables are independent. We are interested in the distribution
of the random variable
be a random variable uniformly distributed over
{
1
,
2
}
, and let
(
G
ξ
). We are going to show that although
(
G
ξ
)is
determined by the random variables
and
ξ
, the random variables
ξ
and
(
G
ξ
)
are statistically independent. In fact, we show the following:
Claim 4.2.9.1:
If the graphs
G
1
and
G
2
are isomorphic, then for every graph
G
that is isomorphic to
G
1
(and
G
2
), it holds that
1
2
G
]
G
]
Pr
[
ξ
=
1
|
(
G
ξ
)
=
=
Pr
[
ξ
=
2
|
(
G
ξ
)
=
=
def
={
π
:
π
(
G
1
)
=
G
}
S
2
def
Proof:
We
=
{
π
:
π
(
G
2
)
=
G
}
are of the same cardinality. This follows from the observa-
tion that there is a 1-1 and onto correspondence between the set
S
1
and the set
S
2
(the correspondence is given by the isomorphism between the graphs
G
1
and
G
2
). Hence,
first
claim
that
the
sets
S
1
and
G
|
ξ
=
G
]
Pr
[
(
G
ξ
)
=
1]
=
Pr
[
(
G
1
)
=
=
Pr
[
∈
S
1
]
=
Pr
[
∈
S
2
]
G
|
ξ
=
=
Pr
[
(
G
ξ
)
=
2]
Using Bayes' rule, the claim follows.
Intuitively, Claim 4.2.9.1 says that for every pair (
G
1
,
G
2
) of isomorphic graphs,
the random variable
ξ
, and so no prover can
fool the verifier into accepting with probability greater than
(
G
ξ
) yields no information on
1
2
. Specifically, we let
R
be an arbitrary randomized process (representing a possible cheating-prover
strategy that depends on (
G
1
,
G
2
)) that given the verifier's message in Step V1
197
