quasiP-Natural Property again SIZE($n^e$) for fixed e.

Question

The Natural Proof theorem says :

• If for a fixed $c>1$ $G_k \in SIZE(k^c)$ is $2^{k^\epsilon}$-hard then not exists a $quasiP$-Natural Property that for all $e$ sufficently large is usefull against $SIZE(n^e)$.

The idea in the proof is that if you can distinguish a random function from a function in $SIZE(n^e)$ you can invert a pseudorandom generator. $SIZE(n^e)$ is big enough to compute pseudorandom function generator (based on the pseudorandom string generator $G_k$)

can we say that?

• If for any k,n (where if we fix n then we can choose any $k=n^{O(1)}$) $G:\{0,1\}^k\times \{0,1\}^n \rightarrow \{0,1\}$ is a pseudorandom functions genereator (for a sub-exponential adversaries) computable in $SIZE(n^e)$ then not exists a $quasiP$-Natural Property usefull against $SIZE(n^e)$.

I think that it's wrong, because for any fixed $e$ you can find a $quasiP$-Natural Property against $SIZE(n^e)$. But I can't see why

Answer 1

If $G: \{0,1\}^k \rightarrow \{0,1\}^{2k}$ is a polynomial time computable pseudorandom generator with security $t(k)$, that is such that every adversary running in time $\leq t(k)$ has distinguishing probability $\leq 1/t(k)$, then we can construct a family of functions $f: \{0,1\}^n \rightarrow \{0,1\}$ such that each function is computable by circuit of size $k(n)^c$, where $c$ is an absolute constant, but the truth-table of a random function from the family is indistinguishable from the truth-table of a truly random function by properties computable in time roughly $t(k(n))$, where we are free to choose $k(n)$ any way we want. Such a family of function contradicts the existence of a natural property computable in time $t(k(n))$ and useful against circuits of size $k(n)^c$.

Now it is a matter to instantiate the parameters. If we believe that there are one-way functions secure against sub-exponential adversaries, then we can take $t(k) = 2^{k^{\epsilon}}$ for an absolute constant $\epsilon >0$. If there were a quasi-polytime natural property that is useful against size($n^e$) for every $e$, then we can take $k(n)= n^{e}$ for every $e$, and the property would still be able to distinguish our family of functions computed by circuits of size $n^{ce}$ from truly random functions, even though no property computable in time $\leq t(k(n)) = 2^{n^{\epsilon e}}$ can do that. This quasi-polytime computable property is computable in time $\leq 2^{n^d}$ for some absolute constant $d$, and we reach a contradiction when $e > d/\epsilon$. (Recall that $d,\epsilon$ are absolute constants and that we can take $e$ as large as we want.)

The point here is the order of quantifiers. If you are looking for a specific polynomial circuit size, like $n^{10}$, you can have a quasi-polytime natural property that is useful against those circuits, because you can actually explicitly check in time roughly $2^{n^{10}}$ if a given function is computable by a circuit of size $n^{10}$. If, however, you want a quasy-polytime natural property that is simultaneously useful against all circuit sizes $n^e$ for all $e$ (that is, for each $e$, the property becomes useful after a sufficiently large $n$), then you are impyling the existence of sub-exponential distinguishers for pseduroandom generators and sub-exponential inverters for one-way functions.