Cryptography Reference
In-Depth Information
regardless of the bottle, then there would be no way for Petra to guess correctly
with probability higher than 50% which bottle was used.)
We now get back to the formal exposition. Let us first define the language in focus: Two
graphs, 5
G 1 =
( V 1 ,
E 1 ) and G 2 =
( V 2 ,
E 2 ), are called isomorphic if there exists a 1-1
and onto mapping,
π
, from the vertex set V 1 to the vertex set V 2 such that ( u
,v
)
E 1
if and only if (
, if it exists, is called an isomorphism
between the graphs. The set of pairs of non-isomorphic graphs is denoted by GNI .
π
(
v
)
( u ))
E 2 . The mapping
π
Construction
4.2.8
(An
Interactive
Proof
System
for
Graph
Non-
Isomorphism):
Common input: A pair of two graphs, G 1 =
( V 1 ,
E 1 ) and G 2 =
( V 2 ,
E 2 ) . Suppose,
without loss of generality, that V 1 ={
1
,
2
,..., |
V 1 |}
, and similarly for V 2 .
Verifier's first step (V1): The verifier selects at random one of the two input graphs
and sends to the prover a random isomorphic copy of this graph. Namely, the
verifier selects uniformly
from the set of
permutations over the vertex set V σ . The verifier constructs a graph with vertex
set V σ and edge set
σ ∈{
1
,
2
}
and a random permutation
π
def
={
F
(
π
( u )
(
v
)) : ( u
,v
)
E σ }
and sends ( V σ ,
F ) to the prover.
Motivating remark: If the input graphs are non-isomorphic, as the prover claims,
then the prover should be able to distinguish (not necessarily by an efficient proce-
dure) isomorphic copies of one graph from isomorphic copies of the other graph.
However, if the input graphs are isomorphic, then a random isomorphic copy of
one graph will be distributed identically to a random isomorphic copy of the other
graph.
Prover's first step (P1): Upon receiving a graph G =
( V ,
E ) from the verifier, the
prover finds
τ ∈{
1
,
2
}
such that the graph G is isomorphic to the input graph G τ .
(If both
τ =
1 and r
=
2 satisfy the condition, then
τ
is selected arbitrarily. In case
no
τ ∈{
1
,
2
}
satisfies the condition,
τ
is set to 0 .) The prover sends
τ
to the verifier.
Verifier's second step (V2): If the message
σ
(chosen in Step V1), then the verifier outputs 1 (i.e., accepts the common input).
Otherwise the verifier outputs 0 (i.e., rejects the common input).
τ
received from the prover equals
This verifier program is easily implemented in probabilistic polynomial time. We do not
know of a probabilistic polynomial-time implementation of the prover's program, but
this is not required. We shall now show that the foregoing pair of interactive machines
constitutes an interactive proof system (in the general sense) for the language GNI
(Graph Non-Isomorphism).
Proposition 4.2.9: The language G N I is in the class
. Furthermore, the
programs specified in Construction 4.2.8 constitute a generalized interactive proof
system for G N I , with completeness bound 1 and soundness bound
IP
1
2 . Namely:
5 See footnote 13.
Search WWH ::




Custom Search