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, 2021 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$ Mar 9, 2021 at 3:54

1 Answer 1

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, 2021 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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