Endless PRNG from PRNG with specific stretch? Every definition of pseudorandom generator that I've seen says it takes n-bit strings and gives poly(n)-bit strings.

Is there a proof that if there is such a pseudorandom generator then there is a pseudorandom generator that takes n-bit seeds and repeatedly outputs bits on request?

Things I would be curious about that are not essential to the answer:


Could it be made random access? (ie, one can efficiently find what its m-th output will be)
Could it be made so that a state compromise would not give useful information about earlier outputs?
Most PRNG constructions can generate arbitrarily long pseudo-random bit sequences (or at least, can quite easily extended to do such).

Of course, a limited internal state size means that there will be some point from where the sequence repeats itself. (We can make the size that large that this will not occur in practice.)

A simple way to have a seekable PRNG would be to apply a message authentication code on seek and seed:

$$ R_{\operatorname{seek}} = MAC(\operatorname{seed}, \operatorname{seek}) $$

The seed should be on the key position here.

In this case, the internal state (the seed) will stay constant, i.e. a random output sequence will be repeatable by providing the same (sequence of) seek(s) again. As the seek can get (almost) arbitrarily long, you will have an (almost) endless sequence.

(Of course, if using a counter as the seek value, the counter's size must be included in the PRNG's state size, so a limited size state does not allow an endless non-repeating sequence.)

A non-recoverable PRNG is build by applying some one-way function on the internal state in each round of operation, additionally to generating the output (with another one-way function) from the state. So, given two one-way functions $f_1$ and $f_2$ and previous state $S_{\text{old}}$, we do

$$ R = f_1(S_{\text{old}}) $$
   $$ S_{\text{new}} = f_2(S_{\text{old}}) $$

and output $R$.

This PRNG will cycle as soon as $f_1^n(S_0)$ reaches a cycle. For a random function on a $n$-bit state, after an expected number of around $2^{n/2}$ steps a cycle of expected size $2^{n/2}$  will be reached.

You can combine both ideas if you don't need that seeks are commutative (i.e. that $seek(a); seek(b)$ gives the same output as $seek(b); seek(a)$.