Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer
1  
Looking online, I found that what you really want is a pseudo-random function family (instead of a MAC). Such a family is both endless and seekable, which means I'll probably be accepting this answer. Do you know if it follows from the existence of a PRNG that such $f_1$ and $f_2$ can be chosen to make that non-recoverable PRNG also secure? –  Ricky Demer Oct 24 '11 at 16:29

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

In the formal sense that cryptographic 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 parameter ( typically n). It falls out from this that you have to limit the output of the function to a polynomial on n.

share|improve this answer
    
How does "it fall out from this ..."? As far as I can see, it could be that for every polynomial on n, that many output bits are not distinguishable from that many random bits. –  Ricky Demer Oct 24 '11 at 5:11
    
It is for every polynomial on n. The thing is, if you let it return more than some polynomial, it would be really really odd. How can you have an attacker that can only compute in polynomial time but can read a larger than polynomial number of bits. You can't. –  imichaelmiers Oct 24 '11 at 5:34
    
What "is for every polynomial on n"? "How can ... bits. You can't." Exactly –  Ricky Demer Oct 24 '11 at 5:43
    
Also, how would that be odd at all? It could be returning n^2 bits, which is more than the polynomial n. –  Ricky Demer Oct 24 '11 at 5:45
1  
@RickyDemer $n^2$ is a polynomial in $n$. I'm not really sure what you are argumenting here. –  Paŭlo Ebermann Oct 24 '11 at 10:57

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.