Cryptography Reference
In-Depth Information
the outgoing message of
V
∗
, denoted
σ
. To simplify the rest of the description,
we
normalize
σ
by setting
σ
=
1if
σ
=
2 (and leave
σ
unchanged if
σ
=
2).
4.
Simulating the prover's second step
(P2): If
σ
=
τ
, then the simulator halts with
G
,ψ
).
5.
Failure of the simulation:
Otherwise (i.e.,
output (
x
,
r
,
σ
=
τ
), the simulator halts with out-
put
⊥
.
Using the hypothesis that
V
∗
is polynomial-time, it follows that so is the sim-
ulator
M
∗
. It is left to show that
M
∗
outputs
1
2
⊥
with probability at most
and
that, conditioned on not outputting
, the simulator's output is distributed as the
verifier's view in a “real interaction with
P
GI
.” The following claim is the key to
the proof of both claims.
⊥
Claim 4.3.9.1:
Suppose that the graphs
G
1
and
G
2
are isomorphic. Let
ξ
be a
random variable uniformly distributed in
be a random variable
uniformly distributed over the set of permutations over
V
ξ
. Then for every graph
G
that is isomorphic to
G
1
(and
G
2
), it holds that
{
1
,
2
}
, and let
1
2
Pr
[
ξ
=
1
|
(
G
ξ
)
=
G
]
=
Pr
[
ξ
=
2
|
(
G
ξ
)
=
G
]
=
where, as in Claim 4.2.9.1,
(
G
) denotes the graph obtained from the graph
G
by relabeling its nodes using the permutation
π
π
.
Claim 4.3.9.1 is identical to Claim 4.2.9.1 (used to demonstrate that Construc-
tion 4.2.8 constitutes an interactive proof for
GNI
).
10
As in the rest of the proof of
Proposition 4.2.9, it follows that any random process with output in
{
1
,
2
}
,given
2
. Hence, given
G
(constructed by the
simulator in Step 2), the verifier's program yields (normalized)
σ
, so that
σ
=
τ
with probability exactly
1
(
G
ξ
), outputs
ξ
with probability exactly
1
2
. We conclude that the simulator outputs
⊥
with proba-
1
bility
2
. It remains to prove that, conditioned on not outputting
⊥
, the simulator's
output is identical to “
V
∗
's view of real interactions.” Namely:
Claim 4.3.9.2:
Let
x
=
(
G
1
,
G
2
)
∈
GI
. Then for every string
r
, graph
H
, and
permutation
ψ
, it holds that
view
P
GI
)
[
M
∗
(
x
)
M
∗
(
x
)
Pr
V
∗
(
x
)
=
(
x
,
r
,
H
,ψ
=
Pr
=
(
x
,
r
,
H
,ψ
)
|
= ⊥
]
Proof:
Let
m
∗
(
x
) describe
M
∗
(
x
) conditioned on its not being
⊥
. We first ob-
serve that both
m
∗
(
x
) and view
P
GI
V
∗
(
x
) are distributed over quadruples of the form
(
x
,
r
,
·
,
·
), with uniformly distributed
r
∈{
0
,
1
}
q
(
|
x
|
)
. Let
ν
(
x
,
r
) be a random vari-
able describing the last two elements of view
P
GI
V
∗
(
x
) conditioned on the second
element equaling
r
. Similarly, let
µ
(
x
,
r
) describe the last two elements of
m
∗
(
x
)
(conditioned on the second element equaling
r
). We need to show that
ν
(
x
,
r
)
10
In Construction 4.2.8, the graph
(
G
ξ
) was presented to the prover, and Claim 4.2.9.1 was used to establish
the soundness of the proof system (i.e., analyze what happens in case (
G
1
,
G
2
)
∈
GNI
, which means (
G
1
,
G
2
)
∈
GI
). Here the graph
(
G
ξ
) is presented to the verifier, and the claim is used to establish the zero-knowledge
property (and so also refers to (
G
1
,
G
2
)
∈
GI
).
