Cryptography Reference
In-Depth Information
commitment scheme. We claim that the resulting protocol is a perfect zero-knowledge
argument (i.e., computationally sound proof) for the original language.
Proposition 4.8.9:
Consider a modification of Construction 4.4.7 such that the
commitment scheme used by the prover is replaced by a perfectly hiding com-
mitment scheme. Then the resulting protocol is a perfect zero-knowledge weak
argument for Graph 3-Colorability.
By a
weak argument
we mean a protocol in which the gap between the completeness
and the computational-soundness conditions is noticeable. In our case, the verifier
always accepts inputs in
G
3
C
, whereas no efficient prover can fool him into accepting
graphs
G
=
(
V
,
E
) not in
G
3
C
with probability that is non-negligibly greater than
1
−
1
|
E
|
. Specifically, we shall show that no efficient prover can fool him into accepting
graphs
G
1
2
|
E
|
. Recall that by
(sequentially) repeating this protocol polynomially many times the (computational-
soundness) error probability can be made negligible.
=
(
V
,
E
) not in
G
3
C
with probability greater than 1
−
Proof Sketch:
We start by proving that the resulting protocol is perfect zero-
knowledge for
G
3
C
. We use the same simulator as in the proof of Proposi-
tion 4.4.8. However, this time analyzing the properties of the simulator is much
easier and yields stronger results, the reason being that here the prover's commit-
ment is perfectly hiding, whereas there it is only computationally hiding. Thus,
here the prover's commitments are distributed independently of the committed
values, and consequently the verifier acts in total oblivion of the values. It follows
that the simulator outputs a transcript with probability exactly
3
, and for similar
reasons this transcript is distributed identically to the real interaction. The perfect
zero-knowledge property follows.
The completeness condition is obvious, as in the proof of Proposition 4.4.8.
It is left to prove that the protocol satisfies the (weak) computational-soundness
requirement. This is indeed the more subtle part of the current proof (in contrast
to the proof of Proposition 4.4.8, in which proving soundness is quite easy). The
reason is that here the prover's commitment is only computationally binding,
whereas there it is perfectly binding. Thus, here we use a reducibility argument to
show that a prover's ability to cheat, with too high a probability, on inputs not in
G
3
C
translates to an algorithm contradicting the unambiguity of the commitment
scheme. Details follow.
We assume, to the contradiction, that there exists a (polynomial-time) cheat-
ing prover
P
∗
and an infinite sequence of integers such that for each integer
n
in
this sequence, there exist graphs
G
n
=
(
V
n
,
E
n
)
∈
G
3
C
and a string
y
n
such that
P
∗
(
y
n
) leads the verifier to accept
G
n
with probability greater than 1
−
1
2
|
E
n
|
. Let
def
=|
V
n
|
. Let
c
1
,...,
c
k
be the sequence of commitments (to the vertex colors)
sent by the prover in Step P1. Recall that in the next step, the verifier sends a
uniformly chosen edge (of
E
n
), and the prover must answer by revealing dif-
ferent colors for its endpoint; otherwise the verifier rejects. A straightforward
k
