I'm trying to determine if $F_{k_1, k_2}(x) = F_{k_1}(x) \oplus F_{k_2}(x)$ ($k_1 \neq k_2$ because that would be lame) is a pseudorandom function. My hunch is that it is. My reduction proof proceeds like this (but I get stuck halfway through)
Suppose $F$ is not secure. Then there is a PPT distinguisher D' s.t. for all $negl(n)$ we have: $|P(D'^{F(\cdot)}(1^n) = 1) - P(D'^{f(\cdot)}(1^n) = 1)| \geq negl(n)$
We then construct a distinguishers $D_1, D_2$ that break $F_{k_1},F_{k_2}$.
So $D_1$ gives a message m to oracle $O_1$. $D_1$ wants to find out if $O_1$ is random or if it is actually $F_{k_1}$. It receives back output $y_1$. It then asks D' if $y_1 = F_{k_1}(m) \oplus F_{k_2}(m)$. If D' says yes then we know that either $F_{k_2}(m) = 0$ or $O_1$ is random since:
$0 = y_1 \oplus y_1 =$ $F_{k_1}(m) \oplus y_1 $ $= F_{k_1}(m) \oplus F_{k_1}(m) \oplus F_{k_2}(m) = F_{k_2}(m)$.
Since we learn something about $F_{k_2}$ which can be used to break $F_{k_2}$.
Working symmetrically we can learn something about $F_{k_1}$.
Basically if you run both tests, and D' says that both $y_1$ and $y_2$ are $F_{k_1}(m) \oplus F_{k_2}(m) $ you can check if either $y_1$ or $y_2$ are 0. If neither are 0, both oracles must be random.
Am I on the right track with this? How would I write up a formal proof?