    ## A recent pseudo-random number generator

R. Impagliazzo and M. Naor18proposed 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. Naor18
Efficient Cryptographic Schemes Provably as Secure as Subset Sum,'' Symposium on Foundations of Computer Science, 1989    