Cryptography Reference
In-Depth Information
does, the
n
commitments sent in Step P1 cannot correspond to a 3-coloring of the
graph (since such coloring does not exist). We stress that the unique correspondence of
commitments to values is guaranteed by the unambiguity property of the commitment
scheme. It follows that there must exist an edge (
u
,v
)
∈
E
such that
c
u
and
c
v
, sent in
Step P1, are not commitments to two
different
elements of
{
1
,
2
,
3
}
. Hence, no matter
how the prover behaves, the verifier will reject with probability at least 1
/
|
E
|
. Therefore,
there is a noticeable (in the input length) gap between the acceptance probabilities in
the case in which the input is in
G
3
C
and in the case in which it is not.
We shall now show that
P
G
3
C
, the prover program specified in Construction 4.4.7, is
indeed zero-knowledge for
G
3
C
. The claim is proved without reference to auxiliary-
input (to the verifier), but an extension of the argument to auxiliary-input zero-
knowledge is straightforward. Again, we use the alternative formulation of zero-
knowledge (i.e., Definition 4.3.3) and show how to simulate
V
∗
's view of the interaction
with
P
G
3
C
for every probabilistic polynomial-time interactive machine
V
∗
.Asinthe
case of the Graph Isomorphism proof system (i.e., Construction 4.3.8), it is easy to
simulate the verifier's view of the interaction with
P
G
3
C
,
provided that
the verifier fol-
lows the specified program. However, we need to simulate the view of the verifier in
the general case (in which the verifier uses an
arbitrary
polynomial-time interactive
program). Following is an overview of our simulation (i.e., of our construction of a
simulator
M
∗
for an arbitrary
V
∗
).
The simulator
M
∗
incorporates the code of the interactive program
V
∗
. On input
a graph
G
E
), the simulator
M
∗
(not having access to a 3-coloring of
G
) first
uniformly and independently selects
n
values
e
1
,...,
=
(
V
,
and constructs a
commitment to each of them. (These
e
i
's constitute a “pseudo-coloring” of the graph
in which the endpoints of each edge will be colored differently with probability
e
n
∈{
1
,
2
,
3
}
2
3
.)
In doing so, the simulator behaves very differently from
P
G
3
C
, but nevertheless the
sequence of commitments thus generated is computationally indistinguishable from
the sequence of commitments to a valid 3-coloring sent by
P
G
3
C
in Step P1. If
V
∗
,
when given the commitments generated by the simulator, asks to inspect an edge (
u
,v
)
such that
e
u
=
e
v
, then the simulator can indeed answer correctly, and in doing so
it completes a simulation of the verifier's view of the interaction with
P
G
3
C
.How-
ever, if
V
∗
asks to inspect an edge (
u
,v
) such that
e
u
=
e
v
, then the simulator has
no way to answer correctly, and we let it halt with output
⊥
. We stress that we do
not assume that the simulator “knows” a priori which edge the verifier
V
∗
will ask to
inspect. The validity of the simulator stems from a different source. If the verifier's
request were oblivious of the prover's commitment, then with probability
2
3
the veri-
fier would have asked to inspect an edge that was properly colored. Using the secrecy
property of the commitment scheme, it follows that the verifier's request is “almost
oblivious” of the values in the commitments. The zero-knowledge claim follows (yet,
with some effort). Further details follow. We start with a detailed description of the
simulator.
Simulator
M
∗
.
On input a graph
G
=
(
V
,
E
), where
n
=|
V
|
, the simulator
M
∗
pro-
ceeds as follows:
