Endless PRNG from PRNG with specific stretch?

Question

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?

Answer 1

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)$.

Answer 2

Be careful, most practical used PRGs have a very practical cicle length, meaning, they repeat after a certain number of outputs. But if you follow Paulo Ebermanns construction, with slight modifications, you can get a forward secure PRNG, that is unlikely to repeat itself in practice.

Given a pseudorandom function family $F=\{f_k:\{0,1\}^n \rightarrow \{0,1\}^n|k\in\{0,1\}^n\}$ (here you could use i.e. a secure blockcipher like AES) you build the PRNG as

$G(SEED_i) = (SEED_{i+1}||OUT_i) = (f_{SEED_i}(0)||f_{SEED_i}(1))$

where || denotes concatenation and $SEED_0$ is the real random seed. This PRNG is forward secure. So if an adversary learns the actual seed $SEED_i$ she is still unable to distinguish former outputs from real random outputs. For a proof of security see

Bellare, M. & Yee, B. Joye, M. (Ed.) Forward-Security in Private-Key Cryptography Topics in Cryptology --- CT-RSA 2003, Springer Berlin / Heidelberg, 2003, 2612, 1-18

Answer 3

The polynomial(n) is actually an artifact of formalism in provable cryptography and not of much consequence practically. Piratically there is a fixed number of bits you can get out of a PRNG before it cycles

In the formal sense that crypto proofs deal with not really. In practice, what is and isn't a polynomial (note that usually that doesn't mean some specific polynomial,its for an arbitrary polynomial ) is kinda moot since n is fixed and there exists some polynomial that will return the number of bits you want: polynomials can after all be made arbitrary large. They only work as a bound when we talk about rates of growth .

The formal definitions of a PRNG is a function that a theoretical attacker cannot distinguish from an actual RNG( i.e. a geiger counter or something) with any reasonable likelihood.

Obviously, an attacker with unlimited resources can just try all possible seeds for the PRNG and see if it gets the output from the PRNG. So we have to bound the attackers ability.

The way this is typically done, we say the attacker can only compute things in polynomial time as a function of some security paramater ( typically n). It falls out from this that you have to limit the output of the function to a polynomial on n.