2
$\begingroup$

Let $G$ $PRG$ and $G'(s)$ equal to the first $n$-bits of $G(s)$, where $|s| = n$. Show that $F_k(x) = G'(k) ⊕ x$ is not a $PRF$.

My attempt:
Lets assume a $k$ and 2 messages $x_1$ and $x_2$. So, for $x_1$ I have $F_k(x_1) = G'(k) ⊕ x_1$, for $x_2$ we have $F_k(x_2) = G'(k) ⊕ x_2$. If the attacker does $F_k(x_1) ⊕ F_k(x_2)$ he gets $x_1 ⊕ x_2$. And then he can simply $XOR$ that by $x_1$ or $x_2$ and then get the message from that.

I have no idea if this is the correct way to prove this. Can you give my any hint if this is the correct way to show that a function is not $PRF$, maybe I have to do a proof by contradiction ?

EDIT:

I also know that a $PRG$ must not be predictable, if it is then that's not good, so for the function $F$ to use $G'$ as the $PRG$ which is always the first $n$-bits of $G$ it's not good because it violates the pseudorandomness property. I don't know if this is correct or helpful at all.

$\endgroup$
3
$\begingroup$

For something to be a PRF, it must be impossible for a probabilistic polynomial time algorithm to distinguish it from a random function. The distinguisher you note in your attempt is correct, as a random function would not have that property (xor two calls with the same key but different x values and you get the xor of the two x values).

As a side note, these notes are very good when it comes to PRFs. Especially 3.3 and 3.4.

$\endgroup$
  • $\begingroup$ so if my proof correct? therefore $F$ is not $PRF$, right ? $\endgroup$ – southpaw22 Jun 8 '16 at 18:43
  • 1
    $\begingroup$ @southpaw22 I think the way you present your work as a distinguisher that proves not PRF could be clearer. I had to read it a few times to see how what you were doing was a distinguisher. But, you did find the correct distinguisher. $\endgroup$ – mikeazo Jun 8 '16 at 18:45

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.