Cryptography Reference
In-Depth Information
ψ
Auxiliary input to the prover:
A 3-coloring of G, denoted
.
Prover's first step (P1):
The prover selects a random permutation
π
over
{
1
,
2
,
3
}
)
def
and sets
V . The prover uses the commitment scheme
to commit itself to the color of each of the vertices. Namely, the prover uniformly
and independently selects s
1
,...,
φ
(
v
=
π
(
ψ
(
v
))
for each
v
∈
n
, computes c
i
=
s
n
∈{
0
,
1
}
C
s
i
(
φ
(
i
))
for each
i
∈
V , and sends c
1
,...,
c
n
to the verifier.
Verifier's first step (V1):
The verifier uniformly selects an edge
(
u
,v
)
∈
E and
sends it to the prover.
Prover's second step (P2):
Without loss of generality, we can assume that the
message received from the verifier is an edge, denoted
(
u
,v
)
. (Otherwise, the prover
sets
(
u
)
to be some predetermined edge of G.) The prover uses the (canonical)
reveal phase of the commitment scheme in order to reveal the colors of vertices
u and
,v
v
to the verifier. Namely, the prover sends
(
s
u
,φ
(
u
))
and
(
s
v
,φ
(
v
))
to the
verifier.
Verifier's second step (V2):
The verifier checks whether or not the values corre-
sponding to commitments u and
were revealed correctly and whether or not
these values are different. Namely, upon receiving
(
s
v
)
and
(
s
,τ
,σ
)
, the verifier
checks whether or not c
u
=
C
s
(
σ
)
,c
v
=
C
s
(
τ
)
, and
σ
=
τ
(and both
σ
and
τ
are
). If all conditions hold, then the verifier accepts. Otherwise it rejects.
Let us denote this prover's program by P
G
3
C
.
in
{
1
,
2
,
3
}
We stress that the program of the verifier and that of the prover can be implemented in
probabilistic polynomial time. In the case of the prover's program, this property is made
possible by use of the
auxiliary input
to the prover. As we shall later see, the foregoing
protocol constitutes a weak interactive proof for
G
3
C
. As usual, the confidence can be
increased (i.e., the error probability can be decreased) by sufficiently many successive
applications. However, the mere existence of an interactive proof for
G
3
C
is obvious
(since
G
3
C
∈
NP
). The punch line is that this protocol is zero-knowledge (also with
respect to auxiliary input). Using the sequential-composition-lemma (Lemma 4.3.11),
it follows that polynomially many sequential applications of this protocol will preserve
the zero-knowledge property.
Proposition 4.4.8:
Suppose that the commitment scheme used in Construc-
tion 4.4.7 satisfies the (non-uniform) secrecy and the unambiguity requirements.
Then Construction 4.4.7 constitutes an auxiliary-input zero-knowledge (general-
ized) interactive proof for G
3
C.
For further discussion of Construction 4.4.7, see Section 4.4.2.4.
4.4.2.3. The Simulator: Proof of Proposition 4.4.8
We first prove that Construction 4.4.7 constitutes a weak interactive proof for
G
3
C
.
Assume first that the input graph is indeed 3-colorable. Then if the prover follows the
specified program, the verifier will always accept (i.e., accept with probability 1). On
the other hand, if the input graph is not 3-colorable, then no matter what the prover
