1
$\begingroup$

I am just beginning to read into pseudorandom generators and I came across this definition for a PRG:

$G_n : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}, \quad \text{ where $l(n)$ is a polynomial}$

Is there a reason why $l(n)$ has to be polynomial? Wouldn't there be an even better security guarantee if it was an exponential function? Simply because the adversary in the definition of pseudorandomness also is a probabilistic polynomial-time adversary.

$\endgroup$
6
$\begingroup$

There are two problems here. The first one is, that a PRG with an exponential output length can no longer be an efficient (i.e. polynomial time) algorithm, since it needs exponential time to even write its output.

The second problem is that any such algorithm is insecure. The distinguisher against a PRG receives a string $y\in \{0,1\}^{\ell(n)}$, that is either the output of the PRG, or a uniformly random string. It is required to be efficient, i.e. it must run in time polynomial in its input length. If the input length is exponential, say $\ell(n)=2^n$, then it can run in time polynomial in $2^n$. That is enough time to enumerate all possible seed values $s\in\{0,1\}^n$, compute $y':=G_n(s)$ and check whether $y' = y$. Since for uniformly random $y$, the probability that such a seed exists is (really really) negligible, this leads to a trivial distinguishing attack.

$\endgroup$
1
  • $\begingroup$ Thank you very much! I never considered that. Excellent answer! $\endgroup$
    – xor_zero
    Nov 18 '20 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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