1
$\begingroup$

I'm learning about (complexity-theoretic) pseudorandom number generators, and I have a pretty basic question about them that I couldn't find an answer to.

Let's say we have a PRG for $P$ that can fool any algorithm running over $n$ bits in time $poly(n)$ with seed length $O(\log^{10}(n))$. This would already be a breakthrough, as it would imply $BPP$ can be decided in deterministic polylog time. But why stop there? Now, every algorithm in $BPP$ only needs $O(\log^{10}(n))$ truly random bits -- why not just use our existing PRG again, so that we only need $O(\log^{10}(O(\log^{10}(n)))) = O(\log\log(n)^{10}) \subset o(\log(n))$ bits, and then $P = BPP$? (I'm not seriously suggesting this is possible; I'm trying to understand the flaw in the reasoning.)

One immediate concern is that if we use $o(\log(n))$ random bits at the end, the distinguisher could just memorize the correct words. But is that the only obstacle? Does that mean if we had a PRG with a "half-logarithmic" seed length, we could do the above strategy?

In general, why can't we just compose PRGs to get arbitrarily better PRGs?

$\endgroup$
2
  • $\begingroup$ What is $n$? Please define all notation. $\endgroup$
    – D.W.
    Jan 19, 2023 at 19:57
  • $\begingroup$ @D.W. I have updated the question to define $n$. $\endgroup$
    – Jake
    Jan 19, 2023 at 21:04

1 Answer 1

1
$\begingroup$

Short answer: you can enumerate all possible seeds of length $O(\log^{10}(\log^{10}(n)))$ in $\text{poly}(\log n)$ time, so such a PRG cannot possible be secure against algorithms whose running time is polynomial in $\log n$, so such a PRG tells us nothing about BPP.

Slightly longer answer: Each PRG comes with a security level, a class of adversaries it is secure against. That class is specified as the set of adversaries whose running time is upper-bounded by some quantity -- the security level. Composition does not increase the security level. So at least in that sense, composition doesn't give us "better" PRGs.

Longer answer: a PRG is a family of functions that are associated with three quantities, the input length, the output length, and an upper bound on the adversary's running time. Typically, each of these may be a function of $n$. The guarantee is that the PRG will be secure against all adversaries whose running time is upper-bounded by the corresponding value. So, to make your argument more concrete, work out what are those values (especially, check out how the security level -- the upper bound on adversary running time -- of the composition of two PRGs depends on the security level of the underlying PRGs), and work out what they need to be for your claim about implications for BPP to hold, and you'll probably spot the issue.

$\endgroup$
1
  • $\begingroup$ Ah, right: to put it more precisely, the distinguisher might not be able to tell the difference between truly random bits and one application of a PRG, but this doesn't necessarily extend to one and two applications of a PRG, right? Thanks for the answer. $\endgroup$
    – Jake
    Jan 19, 2023 at 21:02

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.