Cryptography Reference
In-Depth Information
scheme of Construction 4.11.5. Specifically, the modified proof system for Graph
Coloring proceeds as follows.
Two-Prover Atomic Proof of Graph Coloring
1.
The first prover uses the prover's random tape to determine a permutation of the coloring.
In order to commit to each of the resulting colors, the first prover invokes (the commit
phase of) a two-sender bit commitment, setting the security parameter to be the number
of vertices in the graph. (The first prover plays the role of the first sender, whereas the
verifier plays the role of the receiver.)
2.
The verifier uniformly selects an edge and sends it to the second prover. In response, the
second prover reveals the colors of the endpoints of the required edge by sending the
portions of the prover's random tape used in the corresponding instance of the commit
phase.
As usual, one can see that the provers can always convince the verifier of valid claims
(i.e., the completeness condition holds). Using the unambiguity property of the two-
sender commitment scheme (and ignoring the 2
−
n
deviation from the “perfect case”),
we can think of the first prover as selecting at random, with
arbitrary
probability
distribution, a color assignment to the vertices of the graph. We stress that this claim
holds although many instances of the commit protocol are performed concurrently (see
Remark 4.11.7). If the graph is not 3-colored, then each of the possible color assignments
chosen by the first prover is illegal, and a weak soundness property follows. Yet, by
executing this protocol polynomially many times, even in parallel, we derive a protocol
satisfying the soundness requirement. We stress that the fact that parallelism is effective
here (as means for decreasing error probability) follows from the unambiguity property
of the two-sender commitment scheme and
not
from a general “parallel-composition
lemma” (which is highly non-trivial in the two-prover setting).
We now turn to the zero-knowledge aspects of this protocol. It turns out that this part
is much easier to handle than in all previous cases we have seen. In the construction
of the simulator, we take advantage on the fact that the simulator is playing the role
of both provers (and hence the unambiguity of the commitment scheme does not ap-
ply). Specifically, the simulator, playing the role of both senders, can
easily
open each
commitment any way it wants. (Here we take advantage of the specific structure of the
commitment scheme of Construction 4.11.5.) Details follow.
Simulation of the Atomic Proof of Graph Coloring
1.
The simulator generates random “commitments to nothing.” Namely, the simulator in-
vokes the verifier and answers the verifier's messages that belong to the commit phase
by a sequence of uniformly chosen strings over
{
,
,
}
0
1
2
.
2.
Upon receiving the query-edge (
u
,v
) from the verifier, the simulator uniformly selects
two different colors,
φ
v
, and opens the corresponding commitments so as to reveal
these values. The simulator has no difficulty in doing so, because, unlike the second
prover, it knows the messages sent by the verifier in the commit phase. Specifically,
given the receiver's view of the commit phase, (
r
1
···
φ
u
and
r
n
,
c
1
···
c
n
), a 0-opening (resp.,
