Cryptography Reference
In-Depth Information
v
n
being assigned different
simulator in Step 2, conditioned on vertices
u
n
and
colors.
The circuit initiates an execution of
V
∗
by placing
G
n
on
V
∗
's common-input tape,
placing a uniformly selected
r
q
(
n
)
on
V
∗
's local random tape, and placing
∈{
0
,
1
}
c
n
)on
V
∗
's incoming-message tape. The circuit reads the
outgoing message of
V
∗
, denoted
m
.
the sequence (
c
1
,...,
If
m
=
(
u
n
,v
n
), then the circuit outputs 0.
Otherwise (i.e.,
m
(
u
n
,v
n
)), the circuit invokes algorithm
A
and outputs
A
G
n
,
=
s
u
n
,φ
v
n
)
r
,
(
c
1
,...,
c
n
)
,
(
u
n
)
,
s
v
n
,φ
(
Clearly, the size of
A
n
is polynomial in
n
. We now evaluate the distinguishing
ability of
A
n
. Let us first consider the probability that circuit
A
n
will output 1 on
input a random commitment to the sequence 1
n
2
n
3
n
. The reader can easily verify
that the sequence (
c
1
,...,
c
n
) constructed by circuit
A
n
is distributed identically to
the sequence sent by the prover in Step P1. Hence, recalling some of the notations
introduced earlier, we get
A
ν
u
n
,v
n
(
G
n
)
=
1
[
A
n
(
C
(1
n
2
n
3
n
))
Pr
=
1]
=
q
u
n
,v
n
(
G
n
)
·
Pr
On the other hand, we consider the probability that circuit
A
n
will output 1
on input a random commitment to a uniformly chosen 3
n
-long sequence over
{
1
,
2
,
3
}
. The reader can easily verify that the sequence (
c
1
,...,
c
n
) constructed
by circuit
A
n
is distributed identically to the sequence (
d
1
,...,
d
n
) generated by
the simulator in Step 2, conditioned on
e
u
n
=
e
v
n
. (Recall that
d
i
=
C
(
e
i
)
.
) Letting
T
3
n
denote a random variable uniformly distributed over
{
1
,
2
,
3
}
3
n
,weget
A
µ
u
n
,v
n
(
G
n
)
=
1
=
p
u
n
,v
n
(
G
n
)
Pr
=
·
Pr
[
A
n
(
C
(
T
3
n
))
1]
where
p
u
n
,v
n
(
G
n
) denotes the probability that in Step 3 of the simulation the
verifier will answer with (
u
n
,v
n
), conditioned on
e
u
n
=
e
v
n
. Using the fact that
the proof of Claim 4.4.8.1 actually establishes that
|
Pr
[
M
∗
(
G
n
)
= ⊥
]
−
2
3
|
is
negligible in
n
, it follows that
|
p
u
n
,v
n
(
G
n
)
−
p
u
n
,v
n
(
G
n
)
|
<
1
·
p
(
n
)
2
for all but at
3
most finitely many
G
n
's.
Justification for the last assertion:
Note that
p
u
n
,v
n
(
G
n
) and
p
u
n
,v
n
(
G
n
) refer to
the same event (i.e.,
V
∗
's request equals (
u
n
,v
n
)), but under a different conditional
space (i.e., either
e
u
n
=
e
v
n
or
M
∗
(
G
n
)
). In fact, it is instructive to consider in
both cases the event that
V
∗
's request equals
(
u
n
,v
n
)
and e
u
n
=
e
v
n
. Denoting the latter
event by
X
,wehave
14
= ⊥
14
For further justification of the following equations, let
X
denote the event that
V
∗
'
s
request equals
(
u
n
,v
n
),
and observe that
X
is the conjunction of
X
and
e
u
n
=
e
v
n
. Then:
p
u
n
,v
n
(
G
n
)
= Pr
[
X
|
e
u
n
=
e
v
n
],
Pr
[
X
&
e
u
n
=
e
v
n
]
/
Pr
[
e
u
n
=
e
v
n
]
=
By
definition,
which
equals
Pr
[
X
]
/
Pr
[
e
u
n
=
e
v
n
].
By definition,
p
u
n
,v
n
(
G
n
)
= Pr
[
X
|
M
∗
(
G
n
)
= ⊥
]. Note that the conjunction of
M
∗
(
G
n
)
= ⊥
and
X
implies
e
u
n
=
e
v
n
, and so the former conjunction implies
X
. On the other hand,
X
implies
M
∗
(
G
n
)
= ⊥
.
It follows that
Pr
[
M
∗
(
G
n
)
= ⊥
]
· Pr
[
X
|
M
∗
(
G
n
)
= ⊥
]
= Pr
[
X
&
M
∗
(
G
n
)
= ⊥
]
= Pr
[
X
&
M
∗
(
G
n
)
=
⊥
]
= Pr
[
X
]. We conclude that
p
u
n
,v
n
(
G
n
)
= Pr
[
X
]
/
Pr
[
M
∗
(
G
n
)
= ⊥
].
238
