1
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ Are these functions pseudo random? Why or why not? $\endgroup$ – kelalaka Mar 7 at 12:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Manish Adhikari Mar 9 at 3:54
2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thank you very much! $\endgroup$ – Titanlord Mar 8 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.