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.  Search WWH ::

Custom Search