Cryptography Reference
In-Depth Information
We shall use here the alternative formulation of (perfect) zero-knowledge and
show how to simulate
V
∗
's view of the interaction with
P
GI
for every probabilistic
polynomial-time interactive machine
V
∗
. As mentioned earlier, it is not hard to
simulate the verifier's view of the interaction with
P
GI
when the verifier follows
the specified program. However, we need to simulate the view of the verifier in the
general case (in which it uses an arbitrary polynomial-time interactive program).
Following is an overview of our simulation (i.e., of our construction of a simulator
M
∗
for each
V
∗
).
The simulator
M
∗
incorporates the code of the interactive program
V
∗
.Onin-
put (
G
1
,
G
2
), the simulator
M
∗
first selects at random one of the input graphs (i.e.,
either
G
1
or
G
2
) and generates a random isomorphic copy, denoted
G
, of this
input graph. In doing so, the simulator behaves differently from
P
GI
, but the graph
generated (i.e.,
G
) is distributed identically to the message sent in Step P1 of the
interactive proof. Say that the simulator has generated
G
by randomly permuting
G
1
.Now,if
V
∗
asks to see the isomorphism between
G
1
and
G
, then the simulator
can indeed answer correctly, and in doing so it completes a simulation of the veri-
fier's view of the interaction with
P
GI
.However,if
V
∗
asks to see the isomorphism
between
G
2
and
G
, then the simulator (which, unlike
P
GI
, does not “know”
φ
)
has no way to answer correctly, and we let it halt with output
⊥
. We stress that the
simulator “has no way of knowing” whether
V
∗
will ask to see an isomorphism
to
G
1
or to
G
2
. The point is that the simulator can try one of the possibilities at
random, and if it is lucky (which happens with probability exactly
1
2
), then it can
output a distribution that will be identical to the view of
V
∗
when interacting with
P
GI
(on common input (
G
1
,
G
2
)). A key fact (see Claim 4.3.9.1, following) is
that the distribution of
G
is stochastically independent of the simulator's choice
of which of the two input graphs to use, and so
V
∗
cannot affect the probability
that the simulator will be lucky. A detailed description of the simulator follows.
def
=
(
G
1
,
G
2
), simulator
M
∗
proceeds as follows:
Simulator
M
∗
.
On input
x
1.
Setting the random tape of V
∗
: Let
q
(
) denote a polynomial bounding the running
time of
V
∗
. The simulator
M
∗
starts by uniformly selecting a string
r
·
q
(
|
x
|
)
to be used as the content of the random tape of
V
∗
. (Alternatively, one could
produce coins for
V
∗
“on the fly,” that is, during Step 3, which follows.)
2.
Simulating the prover's first step
(P1): The simulator
M
∗
selects at random, with
uniform probability distribution, a “bit”
∈{
0
,
1
}
from the
set of permutations over the vertex set
V
τ
. It then constructs a graph with vertex
set
V
τ
and edge set
τ
∈{
1
,
2
}
and a permutation
ψ
def
={
F
(
ψ
(
u
)
,ψ
(
v
)) : (
u
,v
)
∈
E
τ
}
,
and sets
G
def
F
).
3.
Simulating the verifier's first step
(V1): The simulator
M
∗
initiates an execution of
V
∗
by placing
x
on
V
∗
's common-input tape, placing
r
(selected in Step 1) on
V
∗
's
random tape, and placing
G
(constructed in Step 2) on
V
∗
's incoming-message
tape. After executing a polynomial number of steps of
V
∗
, the simulator can read
=
(
V
τ
,
