Cryptography Reference
In-Depth Information
The Modified Simulator.
We make the simulator expected polynomial-time by mod-
ifying Step S2 as follows. We add an intermediate Step S1.5, to be performed only
if the simulator does not halt in Step S1. The purpose of Step S1.5 is to provide a
good estimate of
q
(
G
,
r
). The estimate is computed by repeating Step S1 until a fixed
(polynomial-in-
) number of correct
V
∗
revelations is reached (i.e., the estimate will
be the ratio of the number of successes divided by the number of trials). By fixing a
sufficiently large polynomial, we can guarantee that with overwhelmingly high proba-
bility (i.e., 1
|
G
|
2
−
poly(
|
G
|
)
) the estimate is within a constant factor of
q
(
G
−
,
r
). It is easily
verified that the estimate can be computed within expected time poly(
r
).
Step S2 of the simulator is modified by adding a bound on the number of times it
is performed, and if none of these executions yields a correct
V
∗
revelation, then
the simulator outputs a
special empty interaction
. Specifically, Step S2 will be per-
formed at most poly(
|
G
|
)
/
q
times, where
q
is the estimate for
q
(
G
,
r
) computed in
Step S1.5. It follows that the modified simulator has an expected running time bounded
by
q
(
G
,
r
)
·
|
G
|
)
/
q
(
G
,
)
q
(
G
,
r
)
=
poly(
|
G
|
).
It is left to analyze the output distribution of the modified simulator. We confine
ourselves to reducing this analysis to the analysis of the output of the original simu-
lator by bounding the probability that the modified simulator outputs a special empty
interaction. This probability equals
poly(
|
G
|
(
G
,
r
)
def
=
q
(
G
,
r
)
·
(1
−
p
(
G
,
r
))
poly(
|
G
|
)
/
q
(
G
,
r
)
We claim that
(
G
,
r
) is a negligible function of
|
G
|
. Assume, to the contrary, that there
exists a polynomial
P
(
·
), an infinite sequence of graphs
{
G
n
}
, and an infinite sequence
of random tapes
{
r
n
}
such that
(
G
n
,
r
n
)
>
1
/
P
(
n
). It follows that for each such
n
,we
have
q
(
G
n
,
r
n
)
>
1
/
P
(
n
). We consider two cases.
Case 1:
For infinitely many
n
's, it holds that
p
(
G
n
,
r
n
)
≥
q
(
G
n
,
r
n
)
/
2. In such
a case we get, for these
n
's,
−
p
(
G
n
,
r
n
))
poly(
|
G
n
|
)
/
q
(
G
n
,
r
n
)
(
G
n
,
r
n
)
≤
(1
1
poly(
|
G
n
|
)
/
q
(
G
n
,
r
n
)
q
(
G
n
,
r
n
)
≤
−
2
2
−
poly(
|
G
n
|
)
/
2
<
which contradicts our hypothesis that
(
G
n
,
r
n
)
>
1
/
poly(
n
).
Case 2:
For infinitely many
n
's, it holds that
p
(
G
n
,
r
n
)
<
q
(
G
n
,
r
n
)
/
2. It follows
q
(
G
n
,
r
n
)
2
1
that for these
n
's,wehave
2
P
(
n
)
, which leads
to contradiction of the computational secrecy of the commitment scheme (used
by the prover).
|
q
(
G
n
,
r
n
)
−
p
(
G
n
,
r
n
)
|
>
>
Hence, contradiction follows in both cases.
Conclusion.
We remark that one can modify Construction 4.9.1 so that weaker forms
of perfect commitment schemes can be used. We refer specifically to commitment
schemes with perfect a posteriori secrecy (see Section 4.8.2). In such schemes the
