Cryptography Reference
In-Depth Information
s
1
,τ
1
)
through
(
s
t
,σ
t
,
s
t
,τ
t
)
, the verifier checks whether or not for each j
(
s
1
,σ
1
,
it holds that c
u
j
,
j
=
C
s
j
(
σ
j
)
,c
v
j
,
j
=
C
s
j
(
τ
j
)
, and
σ
j
=
τ
j
(and both
σ
j
and
τ
j
are
in
{
1
,
2
,
3
}
). If all conditions hold, then the verifier accepts. Otherwise it rejects.
We first assert that Construction 4.9.1 is indeed an interactive proof for
G
3
C
. Clearly,
the verifier always accepts a common-input in
G
3
C
. Suppose that the common input
graph,
G
E
), is not in
G
3
C
. Using the perfect-binding feature of the prover's
commitment, we can refer to the values committed to in Step P1 and say that each of
the “committed colorings” sent by the prover in Step P1 contains at least one illegally
colored edge. Using the perfect secrecy of the commitments sent by the verifier in
Step V0, we deduce that at Step P1 the prover has “no idea” which edges the verifier asks
to see (i.e., as far as the information available to the prover is concerned, all possibilities
are equally likely). Hence, although the prover sends the “coloring commitment” after
receiving the “edge commitment,” the probability that all the “committed edges” have
legally “committed coloring” is at most
1
−
=
(
V
,
t
1
≈
e
−
n
<
2
−
n
|
E
|
The (Basic) Simulation Strategy.
We now proceed to show that Construction 4.9.1
is indeed zero-knowledge (in the liberal sense allowing
expected
polynomial-time
simulators). For every probabilistic polynomial-time interactive machine
V
∗
,wein-
troduce an expected polynomial-time simulator, denoted
M
∗
, that uses
V
∗
as a black
box. The simulator starts by selecting and fixing a random tape
r
for
V
∗
and by emulat-
ing the prover's preliminary Step P0, producing a message
m
. Given the input graph
G
,
the random tape
r
, and the preliminary (prover) message
m
, the commitment message
of the verifier
V
∗
is determined. Hence,
M
∗
invokes
V
∗
on input
G
, random tape
r
,
and message
m
and gets the corresponding commitment message, denoted
CM
. The
simulator proceeds in two steps.
S1.
Extracting the query edges
:
M
∗
generates a sequence of
n
·
t
random commit-
ments to dummy values (e.g., all values equal 1) and feeds it to
V
∗
. In case
V
∗
replies by revealing correctly a sequence of
t
edges, denoted (
u
1
,v
1
)
(
u
t
,v
t
),
the simulator records these edges and proceeds to the next step. In case the reply
of
V
∗
is not a valid revealing of the commitment message
CM
, the simulator halts
outputting the current view of
V
∗
(e.g.,
G
,
r
,
m
, and the commitments to dummy
values).
S2.
Generating an interaction that satisfies the query edges
(an oversimplified expo-
sition): Let (
u
1
,v
1
)
,...,
(
u
t
,v
t
) denote the sequence of edges recorded in Step S1.
Machine
M
∗
generates a sequence of
n
·
t
commitments,
c
1
,
1
,...,
c
n
,
t
, such that
for each
j
=
1
,...,
t
it holds that
c
u
j
,
j
and
c
v
j
,
j
are random commitments to two
different random values in
,...,
{
,
,
}
, and all the other
c
i
,
j
's are random commitments
to dummy values (e.g., all values equal 1). The underlying values are called
pseudo-
colorings
. The simulator feeds this sequence of commitments to
V
∗
.If
V
∗
replies
by revealing correctly the (previously recorded) sequence of edges, then
M
∗
can
complete the simulation of a “real” interaction of
V
∗
(by revealing the colors of the
1
2
3
