Cryptography Reference
In-Depth Information
endpoints of these recorded edges). Otherwise, the entire Step S2 is repeated (until
success is achieved).
For the sake of simplicity, we ignore the preliminary message m in the rest of the analy-
sis. Furthermore, in the rest of the analysis we ignore the possibility that when invoked
in Steps S1 and S2 the verifier reveals two different edge commitments. Loosely speak-
ing, this is justified by the fact that during an expected polynomial-time computation,
such an event can occur with only negligible probability (since otherwise it contradicts
the computational unambiguity of the commitment scheme used by the verifier).
The Running Time of the Oversimplified Simulator. To illustrate the behavior of
the simulator, assume that the program V always correctly reveals the commitment
made in Step V0. In such a case, the simulator will find out the query edges in Step S1,
and using them in Step S2 it will simulate the interaction of V with the real prover.
Using ideas such as in Section 4.4 one can show that the simulation is computationally
indistinguishable from the real interaction. Note that in this case Step S2 of the simulator
is performed only once.
Consider now a more complex case in which on each possible sequence of internal
coin tosses r , program V correctly reveals the commitment made in Step V0 only with
probability
1
3 . The probability in this statement is taken over all possible commitments
generated to the dummy values (in the simulator Step S1). We first observe that the
probability that V correctly reveals the commitment made in Step V0, after receiving a
random commitment to a sequence of pseudo-colorings (generated by the simulator in
Step S2), is approximately
1
3 (otherwise we derive a contradiction to the computational
secrecy of the commitment scheme used by the prover). Hence the simulator reaches
Step S2 with probability
1
3 , and each execution of Step S2 is completed successfully
1
with probability p
3 . It follows that the expected number of times that Step S2 is
1
1
executed is
p 1.
Let us now consider the general case. Let q ( G , r ) denote the probability that on
input graph G and random tape r , after receiving random commitments to dummy
values (generated in Step S1), program V correctly reveals the commitment made
in Step V0. Likewise, we denote by p ( G , r ) the probability that (on input graph G
and random tape r ) after receiving a random commitment to a sequence of pseudo-
colorings (generated by the simulator in Step S2), program V correctly reveals the
commitment made in Step V0. As before, the difference between q ( G , r ) and p ( G , r )
is negligible (in terms of the size of the graph G ); otherwise one derives a contradiction
to the computational secrecy of the prover's commitment scheme. We conclude that the
simulator reaches Step S2 with probability q
3 ·
def
=
q ( G
,
r ), and each execution of Step S2
def
= p ( G , r ). It follows that the expected
is completed successfully with probability p
1
number of times that Step S2 is executed is q ·
p . Now, here is the bad news: We cannot
guarantee that q p is approximately 1 or is even bounded by a polynomial in the input
size (e.g., let p =
2 n
and q =
2 n / 2 , then the difference between them is negligible,
q
and yet
p is not bounded by poly( n )). This is why the foregoing description of the
simulator is oversimplified and a modification is indeed required.
Search WWH ::




Custom Search