** Next:** About this document ...
** Up:** Further results on pseudo-random
** Previous:** Construction of hard-core predicates
** Contents**

R. Impagliazzo and M. Naor^{18}proposed a pseudo-random number generator that involved only addition:

Choose
randomly, for , with
. Choose
randomly. Add the corresponding to
mod to obtain a sequence of bits. Use the first bits
as output from the generator. The remaining bits give you a new
, for which you obtain a new sum.

This generator is more
efficient than the one in section 8.1, since it uses simpler
operations and produces more than one bit of pseudo-random output
per iteration. The paper establishes connections between the
existence of efficient tests (in the sense of section 8.3)
and the average-case difficulty of subset-sum problems.
We will not try to give a precise statement of the result, but will
try to indicate some of the main ideas.

Suppose there were an efficient algorithm
which looked at the
and at
and guessed whether came from a
sum of the with probability greater than . We will
show that such an algorithm could be used to determine whether
came from a sum with probability close to 1.

In the case in which
we show that
can be used to guess, for each
,
whether is even or odd with probability greater than .
Theorem 34 can then be used to identify with probability
close to 1.

To guess the parity of , we make a guess for the
size of this set and choose a random . We have look at
a problem in which is replaced by and is replaced
by for each . If is a correct guess,
will see a sum of a subset. Otherwise, will be a random number,
and we assumed could distinguish between these two possibilities
with probability greater than .

#### Footnotes

- ... M. Naor
^{18}
- ``Efficient Cryptographic Schemes
Provably as Secure as Subset Sum,''
*Symposium on Foundations of
Computer Science*, 1989

** Next:** About this document ...
** Up:** Further results on pseudo-random
** Previous:** Construction of hard-core predicates
** Contents**
*Translated from LaTeX by Scott Sutherland *

2002-12-14