2
$\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$

1 Answer 1

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$
3
  • $\begingroup$ Thank you very much! I never considered that. Excellent answer! $\endgroup$
    – xor_zero
    Nov 18, 2020 at 10:50
  • $\begingroup$ how could a distinguisher run in polynomial time if the input is exponential? $\endgroup$ Sep 20, 2023 at 23:53
  • $\begingroup$ @QuestionEverything the runtime of an algorithm is always defined as a function of its input length. So if your input length is $m=2^n$, a runtime of $m^c=2^{cn}$ for some constant $c$ is polynomial. $\endgroup$
    – Maeher
    Sep 21, 2023 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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