Optimal covering and CSPNG

Question

Consider a function $f: \{0,1\}^n \to \{0,1\}^{cn}$, where $c>1$.

A random $f$ with high probability generates optimal covering of $\{0,1\}^{cn}$, i. e.:

$\forall x \in \{0,1\}^{cn}$ $\exists y \in Im(f): |x - y| < r + O(\log n)$,

where || - Hamming norm and $r$ is number such that volume of a full-sphere with radius $r$ is equal to $|\{0,1\}^{cn}| : |\{0,1\}^n| = 2^{cn} : 2^n = 2^{(c-1)n}$.

We don't know any $f$ such that can be calculated in polynomial of $n$ time and generates optimal covering.

But what is about Cryptographically secure pseudorandom generator(PG, https://en.wikipedia.org/wiki/Pseudorandom_generator) $f$?

In this case $f$ can be calculated in polynomial of $n$ time. Unfortunately from the definition of PG it is not follows that $f$ generates optimal covering (as in the case of Nisan-Wigderson generator). But anyway if $f$ doesn't generate optimal covering it may be used for some attack on a conjecturally PG function (i. e. for proving that some conjecturally PG are not PG really), I think.

Are there a results about functions that might be PG, but don't generate optimal covering?

Answer 1

The difficulty here is the exact definition of PRF. A PRF is a function $f(k,x)$ which is computationally indistinguishable from a random function of $x$ when we pick $k$ randomly. This does not mean $f(k,x)$ for a fixed $k$ is a random function.

The other obstacle is that we do not know any PRFs, only conjectured ones. There are very few unconditional results in cryptography.