Cryptography Reference
In-Depth Information
f
(
x
), when the average is taken over a random
r
)cannotbedecreased
by repeating
B
several times (e.g., for every
x
,itmaybethat
B
always
answer correctly on three quarters of the pairs (
f
(
x
)
,r
), and always err
on the remaining quarter). What is required is an
alternative way of
using
the algorithm
B
, a way that does not double the original error
probability of
B
.
The key idea is to generate the
r
's in a way that allows to apply
algorithm
B
only once per each
r
(and
i
), instead of twice. Specifically,
we will use algorithm
B
to obtain a “guess” for
b
(
x, r
e
i
), and obtain
b
(
x, r
)inadifferentway(whichdoesnotuse
B
). The good news is
that the error probability is no longer doubled, since we only use
B
to
get a “guess” of
b
(
x, r
⊕
e
i
). The bad news is that we still need to know
b
(
x, r
), and it is not clear how we can know
b
(
x, r
) without applying
B
. The answer is that we can guess
b
(
x, r
) by ourselves. This is fine if
we only need to guess
b
(
x, r
) for one
r
(or logarithmically in
⊕
many
r
's), but the problem is that we need to know (and hence guess) the
value of
b
(
x, r
) for polynomially many
r
's. The obvious way of guessing
these
b
(
x, r
)'s yields an exponentially small success probability. Instead,
we generate these polynomially many
r
's such that, on one hand they
are “suciently random” whereas, on the other hand, we can guess all
the
b
(
x, r
)'s with noticeable success probability.
4
Specifically, generat-
ing the
r
's in a specific
pairwise independent
manner will satisfy both
(seemingly contradictory) requirements. We stress that in case we are
successful (in our guesses for all the
b
(
x, r
)'s), we can retrieve
x
with
high probability. Hence, we retrieve
x
with noticeable probability.
A word about the way in which the pairwise independent
r
's are gen-
erated (and the corresponding
b
(
x, r
)'s are guessed) is indeed in place.
To generate
m
=poly(
|
x
|
)many
r
's, we uniformly (and independently)
select
de
=log
2
(
m
+ 1) strings in
|
x
|
}
|x|
. Let us denote these strings
by
s
1
, ..., s
. We then guess
b
(
x, s
1
) through
b
(
x, s
). Let us denote
these guesses, which are uniformly (and independently) chosen in
{
0
,
1
,
by
σ
1
through
σ
. Hence, the probability that all our guesses for the
b
(
x, s
i
)'s are correct is 2
−
=
{
0
,
1
}
1
poly(
|x|
)
. The different
r
's correspond to the
different
non-empty
subsets of
{
1
,
2
, ...,
}
. Specifically, for every such
4
Alternatively, we can try all polynomially many possible guesses.
