Cryptography Reference
In-Depth Information
The two formulations of validity are equivalent in the case of
-relations. The
idea underlying the equivalence is that, in the current context, success probability and
expected running time can be converted from one to the other.
NP
Proposition 4.7.4:
Let R be an
-relation, and let V be an interactive ma-
chine. Referring to this relation R, machine V satisfies (with error
NP
) the validity
condition of Definition 4.7.2 if and only if V satisfies (with error
κ
) the alternative
validity condition of Definition 4.7.3.
κ
Proof Sketch:
Suppose that
V
satisfies the alternative formulation (with error
κ
),
and let
K
be an adequate extractor and
q
an adequate polynomial. Using the hy-
pothesis that
R
is an
NP
-relation, it follows that when invoking
K
we can
determine whether or not
K
has succeeded. Thus, we can iteratively invoke
K
until it succeeds. If
K
succeeds with probability
s
(
x
,
y
,
r
)
≥
(
p
(
x
,
y
,
r
)
−
κ
(
|
x
|
))
/
q
(
|
x
|
), then the expected number of invocations is 1
/
s
(
x
,
y
,
r
), which is
as required in Definition 4.7.2.
Suppose that
V
satisfies (with error
κ
) the validity requirement of Definition
4.7.2, and let
K
be an adequate extractor and
q
an adequate polynomial (such
that
K
runs in expected time
q
(
|
x
|
/
(
p
(
x
,
y
,
r
)
−
κ
|
x
|
)
(
))). Let
p
be a polyno-
mial bounding the length of solutions for
R
(i.e., (
x
,
s
)
∈
R
implies
|
s
|≤
p
(
|
x
|
)).
Then we proceed with up to
p
(
) iterations: In the
i
th iteration, we emulate
the computation of
K
P
x
,
y
,
r
(
x
) with time bound 2
i
+
1
|
x
|
). In case the current
iteration yields a solution, we halt outputting this solution. Otherwise, with prob-
ability
·
q
(
|
x
|
1
1
2
we halt with a
special failure symbol). In case the last iteration is completed without obtaining a
solution, we simply find a solution by exhaustive search (using time 2
p
(
|
x
|
)
2
, we continue to the next iteration (and with probability
·
poly(
)). Observe that the
i
th iteration is executed with probability at most
2
−
(
i
−
1)
, and so our expected running time is at most
|
x
|
p
(
|
x
|
)
·
2
p
(
|
x
|
)
·
poly(
|
x
|
)
2
−
(
i
−
1)
·
(2
i
+
1
·
q
(
|
x
|
))
+
2
−
p
(
|
x
|
)
i
=
1
=
4
·
p
(
|
x
|
)
·
q
(
|
x
|
)
+
poly(
|
x
|
)
To evaluate the success probability of the new extractor, note that the probabil-
ity that
K
P
x
,
y
,
r
(
x
) will run for more than twice its expected running time (i.e.,
twice
q
(
1
|
x
|
)
/
(
p
(
x
,
y
,
r
)
−
κ
(
|
x
|
))) is less than
2
. Also observe that in iteration
def
=−
i
log
2
(
p
(
x
,
y
,
r
)
−
κ
(
|
x
|
)) we emulate these many steps (i.e., 2
q
(
|
x
|
)
/
(
p
(
x
)) steps). Thus, the probability that we can extract a solution in
one of the first
i
iterations is at least
,
y
,
r
)
−
κ
(
|
x
|
1
2
2
−
(
i
−
1)
·
=
p
(
x
,
y
,
r
)
−
κ
(
|
x
|
), as required
in the alternative formulation.
Comment.
The proof of Proposition 4.7.4 actually establishes that the formulation of
Definition 4.7.2 implies the formulation of Definition 4.7.3 with
q
1. Thus, the for-
mulation of Definition 4.7.3 with
q
≡
1 is equivalent to its general formulation (i.e.,
265
≡
