Why is this PRF not secure? [closed]

Question

So, I'm taking Cryptography I by Dan Boneh on Coursera and I was reviewing the definition of security for a PRF while solving exercises, and I stumbled upon this question from a homework Dan Boneh gave for a winter class of 2020. Where it's cleared stated that F1 is not a secure PRF, but I can't get my head over it.

If $k_1$ and $k_2$ are from the same Keyspace, I'm assuming they are chosen independently, why is this PRF not secure? Is that because we can assume that $k_1$ might be equal to $k_2$? And then query $x = y = 0^n$, that way we could argue the following:

• Receive $z = G((k_1,k_2),(x,y))$, where $G$ is either $F_1$ or a random function.
• Output $b = 1$ if $z = 0^n$ and $0$ otherwise, then

$F_1((k_1,k_2),(0^n,0^n)) = F(k_1, 0^n) ⊕ F(k_2,0^n) = 0^n$

Which would return a non-negligible advantage $(1-2^{-n})$?

Sorry if it doesn't make sense, it's a concept I'm still trying to understand.

Answer 1

Here is the attack: You query:

• $F_1((k_1,k_2),a,b)$ and get $y1$
• $F_1((k_1,k_2),c,b)$ and get $y2$
• $F_1((k_1,k_2),a,d)$ and get $y3$

Now you can compute

• $F_1((k_1,k_2),c,d) = y_1 \oplus y_2 \oplus y_3$

But this value should be unpredictable if the PRF was secure:

Proof:

• $y_1 \oplus y_2 \oplus y_3= (F(k_1,a)\oplus F(k_2,b))\oplus( F(k_1,c)\oplus F(k_2,b))\oplus( F(k_1,d)\oplus F(k_2,b))= F(k_1,c)\oplus F(k_2,d)=F_1((k_1,k_2),c,d)$

Answer 2

x1 and x2 don't get mixed together properly you can predict the output of combinations. In particular we get this (with only 2 queries)

$F_1((0,0),(0,1)) = F_1((0,0),(1,0))$

But if you use different random Ks it still won't help much, you still have a problem can query a few related points and predict a new point, which is the 4 points in the hint, I will stop short from full solution.