# PRF proof and length-preserving

I'm studying for my crypto exam and got stuck on following example:

Is $$F'_k(x) = F_k(0||x)||F_k(1||x)$$ with $$x \in \{0,1\}^{n-1}$$ a PseudoRandom Function PRF, under the assumption, that $$F_k$$ is a PRF?

In the solution, there is a reduction proof stating, that $$F_k'$$ is a PRF. What gets me confused is the definition for PRF, which states, that $$F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$$ has to be an efficient, length-preserving, keyed function, in order to be a PRF. In my opinion $$F'_k(x)$$ is not length-preserving and can therefore not be an PRF. Can someone explain this to me?

(here || denotes concatenation)

• Are these functions pseudo random? Why or why not? Mar 7 at 12:35
• I think are confusing it with pseudo random permutation which is bijective (and in many cases invertible) pseudo random function which has same domain and range sets. Block ciphers are often modeled as pseudo random permutations. Mar 9 at 3:54

A PRF does not have to be length-preserving. We sometimes define it that way for simplicity. In general, $$F:\{0,1\}^n \times \{0,1\}^{\ell_1(n)} \rightarrow \{0,1\}^{\ell_2(n)}$$ for polynomials $$\ell_1,\ell_2$$.