Let $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ be a secure PRF. Define $F(k, x) = f(x, k)$.
Is $F(k, x)$ also a secure PRF?

  • 2
    $\begingroup$ As usual, what have you tried? $\endgroup$ – fkraiem Aug 21 '18 at 14:43
  • $\begingroup$ Big hint: every secure PRP is also a secure PRF. $\endgroup$ – Luis Casillas Aug 21 '18 at 18:02

No. A PRF assumes that the key is chosen randomly.

Example based on @LuisCasillas's comment: With a secret random key, you cannot determine the key from input output pairs. If you reverse the role of key and input, then you have the question: Can you learn "input" ($k$) from output ($f(x,k)$) and "key" ($x$)?

Yes. If $F(k, x) = f(x, k) = E_x(k)$, where $E$ is a PRP, then you can recover $k$ from one input/output pair of $F$. If your output is $c = E_x(k)$ then anyone can compute $k$ if they know $c$ and $x$. $$k = E^{-1}_x(c) = E^{-1}_x(E_x(k))$$

(Where $E$ is block encryption and $E^{-1}$ is the inverse, decryption.

This answers your question because a PRP is a PRF because a permutation is a function. (Or maybe I'm wrong on that. There should be a caveat for small blocksizes. The presence or absence of collisions could distinguish a PRP from a non-PRP PRF.)

However PRPs are an example, not the exception. It's still not safe in general. There can be chosen key attacks, related key attacks, weak key sets, etc. A specific algorithm with no weakness when used correctly is not guaranteed to also be free of weakness when used incorrectly.


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.