Cryptography Reference
In-Depth Information
are not 3-colorable must contain at least one bad template and hence will be rejected
with noticeable probability. Following is an abstract description of the resulting zero-
knowledge interactive proof system for
G
3
C
.
•
Common input:
A simple graph
G
=
(
V
,
E
).
•
Prover's first step:
Let
ψ
be a 3-coloring of
G
. The prover selects a random permutation
)
def
π
over
{
1
,
2
,
3
}
and sets
φ
(
v
=
π
(
ψ
(
v
)) for each
v
∈
V
. Hence, the prover forms a
random relabeling of the 3-coloring
ψ
. The prover sends the verifier a sequence of
|
V
|
locked and non-transparent boxes such that the
v
th box contains the value
φ
(
v
).
•
Verifier's first step:
The verifier uniformly selects an edge (
u
,v
∈
)
E
and sends it to the
prover.
•
Motivating remark:
The verifier asks to inspect the colors of vertices
u
and
.
•
Prover's second step:
The prover sends to the verifier the keys to boxes
u
and
v
v
.
•
Verifier's second step:
The verifier opens boxes
u
and
v
and accepts if and only if they
contain two different elements in
{
1
,
2
,
3
}
.
Clearly, if the input graph is 3-colorable, then the prover can cause the verifier to always
accept. On the other hand, if the input graph is not 3-colorable, then any content placed
in the boxes must be invalid on at least one edge, and consequently the verifier will
reject with probability at least 1
. Hence, the foregoing protocol exhibits a noticeable
gap in the acceptance probabilities between the case of inputs in
G
3
C
and the case of
inputs not in
G
3
C
. The zero-knowledge property follows easily in this abstract setting,
because one can simulate the real interaction by placing a random pair of different colors
in the boxes indicated by the verifier. We stress that this simple argument will not be
possible in the digital implementation, because the boxes are not totally unaffected by
their contents (but rather are affected, yet in an indistinguishable manner). Finally, we
remark that confidence in the validity of the claim (that the input graph is 3-colorable)
can be increased by sequentially applying the foregoing proof sufficiently many times.
(In fact, if the boxes are perfect, as assumed, then one can also use parallel repetitions;
however, the boxes are not perfect in the digital implementation presented next.)
/
|
E
|
4.4.2.2. The Interactive Proof
We now turn to the digital implementation of the abstract protocol. In this implemen-
tation the boxes are implemented by a commitment scheme. Namely, for each box, we
invoke an
independent
execution of the commitment scheme. This will enable us to
execute the reveal phase for only some of the commitments, a property that is crucial
to our scheme. For simplicity of exposition, we use the simple commitment scheme
presented in Construction 4.4.2 (or, more generally, any
one-way-interaction
commit-
ment scheme). We denote by
C
s
(
σ
) the commitment of the sender, using coins
s
,tothe
(ternary) value
σ
.
Construction 4.4.7 (A Zero-Knowledge Proof for Graph 3-Coloring):
def
=|
Common input:
A simple (3-colorable) graph G
=
(
V
,
E
)
. Let n
V
|
and V
=
{
1
,...,
n
}
.
