# Is a function defined as PRF with a given key a PRG?

Let $G(s)=F_{0^n}(s)$ ($0^n$ is a fixed key given to the PRF F) for any $n∈\mathbb{N}$ and $s∈\{0,1\}^n$.

Is G, defined via PRF as above, necessarily a pseudorandom generator?

I presume that it is a PRG, since we don't really know what is the seed s. But the fact that $F_{0^n}()$ is known, makes me doubt myself.

I don't seek for a proof, just an intuition or a hint (i do understand how to prove such claims, i just don't get the "catch" in this specific case).

• You mean a function $F$ that starts by generating $n$ bits set to zero? And there is no repetition of $F$ involved? Either I don't get the question or I'm completely in the dark about what is meant. Anything generating a number of bits biased to a certain number, say 0, is certainly not an PR(B)G (B for bit instead of number). – Maarten Bodewes Mar 29 '17 at 14:04
• @MaartenBodewes F is a PRF, with a given fixed key $0^n$. I am having some hard time figuring out whether the function G, as defined above via F, is a PRG. – Alex Goft Mar 29 '17 at 14:08
• Oh, OK, that makes more sense. – Maarten Bodewes Mar 29 '17 at 14:09
• @MaartenBodewes Thank you for your answer. Can you please give me a hint to what a distinguisher for G needs to do? I guess that it has the ability to compute $F_{0^n}()$, but i am having hard time understanding what inputs to give it, since its input supposed to be the seed used by G which is, of course, not known. – Alex Goft Mar 29 '17 at 14:16

Consider a PRF $F$ which on $n$-bit keys maps $n$-bit inputs to $2n$-bit outputs. Consider $F'$ where $F'_k(x) = F_k(x)$ if $k \ne 0^n$ and $0^{2n}$ otherwise.

• When you are having trouble proving that something is true, seriously consider the possibility that it may be false. ;) – fkraiem Mar 29 '17 at 18:18
• What does it supposed to show? – Alex Goft Mar 31 '17 at 18:15
• Well, $F'$ is a PRF, but the resulting $G'$ is not a PRG... – fkraiem Mar 31 '17 at 23:43
• of course! could you please suggest a way to build a distinguisher D for F, given a distinguisher D' for F' (trying to prove that F' is PRF - assumed by contradiction that it is not a PRF). – Alex Goft Apr 2 '17 at 14:29
• If $D'$ works on $F'$, it will also work on $F$ "as is", without any modification. This is because the PRF experiments for $F$ and $F'$ are identical except with negligible probability, so any distinguisher will have a negligible difference in its success probability between the two experiments. See also this. – fkraiem Apr 3 '17 at 3:10

$G$ defined like this is not necessarily a PRG. The reason is not that the distinguisher can compute $F_{0^n}(x)$ for any $x$ that it wants, as this is also true for a PRG. The reason is that a PRF is a family of functions $\cal F$, and the assumption is that a randomly chosen function from the family is indistinguishable from a truly random function. So, as @fkraiem answered, take any real PRF $\cal F$ (assuming one such family exists), and replace $F_{0^n}\in \cal F$ with a constant function.

This may seem odd, but for a randomly chosen function, they probability that $F_{0^n}$ is chosen is negligible, so $\cal F$ is still a PRF (try to prove this first). Of course, then $F_{0^n}(x)$ for random $x$ is easily distinguishable from a random string.

A simple counterexample is to instantiate $$F$$ as a pseudorandom permutation, which fulfills the PRF requirement. In this case, $$G$$ is not a PRG because... um... the definition of a PRG requires that the output be longer than the seed, but PRPs produce outputs the same length as their inputs.

But ok, let's amend the problem to require that $$F$$ produces outputs longer than its inputs. We can then easily construct a trivially invertible $$F$$ by using two different PRPs, call them $$F^1$$ and $$F^2$$:

$$F_k(x) = F^1_k(x) \| F^2_k(x)$$

Then we have that

$$G(s) = F^1_{0^n}(s) \| F^2_{0^n}(s)$$

...and for random $$s$$ we can easily distinguish $$G(s)$$ by splitting the output in half and computing the inverses of $$F^1_{0^n}$$ and $$F^2_{0^n}$$.