A recent pseudo-random number generator

R. Impagliazzo and M. Naor¹⁸proposed a pseudo-random number generator that involved only addition:

Choose $1\le a_i\le 2^n$ randomly, for $1\le i\le k$, with $k<n<(1+\epsilon)k$. Choose $S\subset \{1,\dots k\}$ randomly. Add the $a_i$ corresponding to $S$ mod $2^n$ to obtain a sequence of $n$ bits. Use the first $n-k$ bits as output from the generator. The remaining $k$ bits give you a new $S$, 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 $\cal {A}$ which looked at the $a_i$ and at $b\in\{0,1\}^{n}$ and guessed whether $b$ came from a sum of the $a_i$ with probability greater than $1/2$. We will show that such an algorithm could be used to determine whether $b$ came from a sum with probability close to 1.

In the case in which $b=\sum_{i\in S}a_i$ we show that $\cal {A}$ can be used to guess, for each $R\subset\{1,\ldots,n\}$, whether $\vert R\cap S\vert$ is even or odd with probability greater than $1/2$. Theorem 34 can then be used to identify $S$ with probability close to 1.

To guess the parity of $\vert R\cap S\vert$, we make a guess $j$ for the size of this set and choose a random $x$. We have $\cal {A}$ look at a problem in which $b$ is replaced by $b-jx$ and $a_i$ is replaced by $a_i-x$ for each $i\in R$. If $j$ is a correct guess, $\cal {A}$ will see a sum of a subset. Otherwise, $b-jx$ will be a random number, and we assumed $\cal {A}$ could distinguish between these two possibilities with probability greater than $1/2$.

Footnotes

... M. Naor¹⁸

``Efficient Cryptographic Schemes Provably as Secure as Subset Sum,'' Symposium on Foundations of Computer Science, 1989