# secure PRFs and XOR

Let $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$.

Why is the function $F_1(k, (x_1, x_2)) = F(k, x_1) \oplus F(k, x_2)$ an unsecure PRF while the function $F_2(k, x) = F(k, x) \oplus x$ is a secure PRF?

• What's $F_1(k, (x, x))$ for any $x$? – Squeamish Ossifrage Apr 17 '18 at 1:49
• Suppose I have a random algorithm $A$ which distinguishes $x \mapsto F_2(k, x)$ from a uniform random function $G\colon \mathcal X \to \mathcal Y$. Can you define a random algorithm $A'$, using $A$ as a subroutine, which distinguishes $x \mapsto F(k, x)$ from a uniform random function $G\colon \mathcal X \to \mathcal Y$? If you're not sure how, can you quote the definition of the PRF-advantage of an algorithm $A$ for distinguishing $F_2$? – Squeamish Ossifrage Apr 17 '18 at 1:52
• $F_1$ is a function that gets as input a key $k \in \mathcal{K}$ and a pair of elements $x_1,x_2 \in \mathcal{X}$ and returns $F(k, x_1) \oplus F(k, x_2)$. – Daniel Apr 17 '18 at 1:52
• Yes, so what happens if $x_1 = x_2$? What is $F(k, x) \oplus F(k, x)$? – Squeamish Ossifrage Apr 17 '18 at 1:53
• Does a uniform random function $G\colon \mathcal X \to \mathcal Y$ often return an $n$-bit $0$ string? – Squeamish Ossifrage Apr 17 '18 at 1:59