# Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| ... ||F_{1…1}(x)$ a PRG?

This exercise comes from Coursera's "Cryptography" course.

Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| ... ||F_{1…1}(x)$ a PRG?

$F$ is a PRF with $n$ bit key, input, and output length. I know the answer is “NO it isn't!”, but I can't understand why.

Is that because on any input $x$, the keys for every $F$ in the concatenation sequence are fixed, which implies that the $F$ functions are not randomly chosen over $2^{-n}$? Could this be a possible answer?

• Hint: $G(x)$ is much larger than $x$. Jul 31, 2015 at 0:43
• Actually, maybe not. Can you clarify how the sequence of keys is constructed? For example, if we take $n = 3$, is it $000, 001, 010, 011, 100, 101, 110, 111$ or $000, 001, 011, 111$, or something else? Jul 31, 2015 at 0:46
• Yes, and $G(x)$ has to be much larger than $x$ otherwise it's worthless. Jul 31, 2015 at 0:47
• See my other comment. Jul 31, 2015 at 0:57
• Well then my previous hint stands, but I'll make it more precise. The length of $G(x)$ is exponential in the length of $x$. Remember that a distinguisher which attempts to distinguish $G(x)$ from a uniform string runs in time polynomial in the length of $G(x)$. Jul 31, 2015 at 1:08

@fkraiem's answer is basically correct, but it only says that $G$ does not match the "syntax" of a PRG. But this is not entirely satisfactory for understanding what's really wrong with $G$ as a PRG.

In addition, $G$ may not be pseudorandom. For example, it could be the case that $F_{00\cdots 0}(x) = 0$ for every $x$, i.e., the all-zeros key is a "weak" key for $F$. This would not contradict the fact that $F$ is a PRF, and this can be proved formally. But now notice that the first bit of $G(x)$ is zero for every seed $x$, which means that $G$ is clearly not a pseudorandom generator.

• Ahm, you're saying "it could be the case that $F_{00...0}(x)=0$ for every $x$". I would reply that this is highly unlikely, it would occur with negligible probability. However, my focus is on every chosen $F$, from the definition for a function $F$ to be pseudorandom: if for all PPT distinguishers $D$, there exists a negligible function $negl$ such that $|Pr[D^{F_k()}(1^n)=1] - Pr[D^{f()}(1^n)=1]| \leq negl(n)$, where $k\leftarrow\{0,1\}^n$ is chosen uniformly at random, and $f$ is chosen uniformly at random from the set of all the functions mapping $n$-bit string to $n$-bit strings. Jul 31, 2015 at 13:05
• In this case all the keys are fixed $\Rightarrow$ $F$ is not pseudorandom, and the concatenation of all such $F$s results in a not random looking string. So $G$ is not pseudorandom. Correct me if I'm wrong. Jul 31, 2015 at 13:08
• One can design a "pathological" PRF $F$ having the property I described, which nonetheless satisfies the definition of a PRF. A PRF can have a small number of weak keys (e.g., the all-zeros key) because the probability of getting such a key when choosing uniformly at random is negligible. Jul 31, 2015 at 13:12
• When $F$ is a secure PRF having the "pathological" property I described, $G$ is not a PRG because it is not pseudorandom -- the first bit of $G(x)$ is 0 no matter what the seed $x$ is. That's all there is to it. Jul 31, 2015 at 13:23
• I'm not dismissing it, but a natural reaction to the exponential-length criticism is just to truncate the definition of $G$. But that doesn't really help, because there is more fundamental problem with $G$'s design. Jul 31, 2015 at 18:27

Because the key-, input- and output-length of $F$ are equal, if the length of the seed $x$ is $n$, there are $2^n$ keys and so $G$ must compute $F$ $2^n$ times and output a string of length $n\cdot 2^n$. Hence, $G$ runs in time exponential in $n$, which means it can't be a pseudorandom generator because a pseudorandom generator is a deterministic polynomial-time algorithm.

(In addition, since a distinguisher runs in time polynomial in the length of $G(x)$, it runs in time exponential in the length of $x$, and brute force through all possible seeds is allowed.)

It's not even necessary to consider a pathological/contrived PRF as in @ChrisPeikert's answer. Just consider $$F$$ = AES. Recall that some PRFs (including AES) are also pseudorandom permutations. Since this is a homework problem, I'll just give a hint to think about how the existence of an $$F^{-1}$$ helps to easily distinguish this output from random. This attack works even if the output is truncated to not be exponentially long.