1

Let $H_k(x)$ be known to be a PRF from the family of PRFs defined by

  • $H_k(x): \{0,1\}^{n} \times \{0,1\}^{n} \rightarrow \{0,1\}^{n}$, and then define
  • $F_k(x) = H_k(x \oplus H_k(x))||H_k(x)$.

Here, addition is over $n$-bit integers modulo 2.

Question : Is $F_k(x)$ a PRF?

This question was presented at the end of my lecture notes but left as an exercise to the reader, and my intuition leads me to believe that this is not necessarily a PRF as I think there exists a counterexample where if the chosen $k$ yields a bad PRF from the family, then an attacker can choose inputs that will cause it to be obvious if the outputs are from $F_{k}$ versus a random function. However, I'm struggling to think of a way to define this $H_{k}$ for a bad $k$.

Any thoughts are helpful!

John Smith
  • 19
  • 4
  • 6
    So, say you query $0^n$, what happens if you query the first half of the response again? – Maeher Oct 11 '18 at 17:58
  • 1
    @Maeher ah I think I see, so if an adversary makes multiple queries where the first half of the bits remain the same but the second half of the bits change, then it is easy to distinguish from random because the first half of output bits will stay same but second half will change? – John Smith Oct 11 '18 at 18:07
  • 2
    Hint: the definition of PRF allows an adversary to make use of the result of the first query to perform the second. – fgrieu Oct 11 '18 at 18:11
  • 2
    @kelalaka Please stop editing $F_k(x)$ to $F(k,x)$ just because you think it's "more readable". You are in the minority in thinking this, and even if you weren't, edits that conflict with the author's intent are not acceptable. – fkraiem Oct 11 '18 at 19:22

0 Answers0