Every definition of pseudorandom generator that I\'ve seen says it takes n-bit s

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.