Cryptography Reference
In-Depth Information
4.9.2.2. Modifying Construction 4.9.1
Recall that we are referring to a modification of Construction 4.9.1 in which the verifier
uses a perfectly binding commitment scheme (with computational secrecy), instead of
the commitment scheme with perfect secrecy used in Construction 4.9.1. In addition,
the commitment scheme used by the prover is non-oblivious.
We adopt the analysis of the first approach (i.e., of Section 4.9.1) to suit our current
needs. We start with the claim that the modified protocol is a computationally sound
proof for G 3 C . Verifying that the modified protocol satisfies the completeness condition
is easy, as usual. We remark that the modified protocol does not satisfy the (usual)
soundness condition (e.g., a “prover” of exponential computing power can break the
verifier's commitment and generate pseudo-colorings that will later fool the verifier
into accepting). Nevertheless, one can show that the modified protocol does satisfy
the computational-soundness condition (of Definition 4.8.1). Namely, we show that
for every polynomial p (
), for every polynomial-time interactive machine B , for all
sufficiently large graphs G
·
G 3 C , and for every y and z ,
1
Pr
[ B ( y ) , V G 3 C ( z ) ( x ) = 1]
p (
|
x
|
)
where V G 3 C is the verifier program in the modified protocol.
Using the information-theoretic unambiguity of the commitment scheme employed
by the prover, we can talk of a unique color assignment that is induced by the prover's
commitments. Using the fact that this commitment scheme is non-oblivious, it fol-
lows that the prover can be modified so that in Step P1 it will also output (on its
private output tape) the values to which it commits itself at this step. Using this out-
put and relying on the computational secrecy of the verifier's commitment scheme,
it follows that the color assignment generated by the prover is almost independent of
the verifier's commitment. Hence, the probability that the prover can fool the verifier
into accepting an input not in the language is at most negligibly greater than what it
would have been if the verifier had asked random queries after the prover made its
(color) commitments. The computational soundness of the (modified) protocol fol-
lows. (We remark that we do not know if the protocol is computationally sound in
the case in which the prover uses a commitment scheme that is not guaranteed to be
non-oblivious. 22 )
Showing that the (modified) protocol is zero-knowledge is even easier than it was
in the first approach (i.e., in Section 4.9.1). The reason is that when demonstrating
22 Specifically, we do not know how to rule out the possibility that after seeing the verifier's commitment of
Step V0, the cheating prover could send some strings at Step P1 such that after the verifier revealed its commitments,
the prover could open those strings in a suitable way. To illustrate the problem, suppose that two parties wish to
toss a coin by using a (perfectly binding) commitment scheme and that the protocol is as follows: First, the first
party commits to a bit, then the second party commits to a bit, next the first party reveals its bit, finally the second
party reveals its bit, and the result is defined as the XOR of the two revealed bits. Now, by copying the messages
of the first party, the second party can force the outcome always to be zero! Note that this problem does not arise
when the second party uses a non-oblivious commitment scheme. The problem also does not arise when the first
party commits via a perfectly hiding commitment scheme (and the second party still uses a perfectly binding
commitment scheme). (The latter protocol is analogous to the proof system presented in Section 4.9.1.)
Search WWH ::




Custom Search