Is F_k_1(x) \xor F_k_2(x) a pseudorandom function?

Question

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?

Answer 1

The simplest way to show something like this would be to take advantage of the triangle inequality with a hybrid argument: $$ \Delta(A, B) \le \Delta(A, C) + \Delta(C, B)\,, $$ where $C$ is some intermediate construction.

In this case, you begin with $F_{k_1}(x) \oplus F_{k_2}(x)$, where $k_1$ and $k_2$ are sampled independently and uniformly at random. We can replace $F_{k_1}$ by a truly random function $f_1$, and now we have $$ f_1(x) \oplus F_{k_2}\,, $$ and the distance from the original construction is the distance from $F_{k_1}$ to $f_1$ which is, by definition, $\mathrm{Adv}^{\mathrm{PRF}}_{F_{k_1}}(D_1)$ for some distinguisher $D_1$ that makes $q$ queries to $F_{k_1}$ and has runtime $t$.

Doing the same for $F_{k_2}$, we have $$ f_1(x) \oplus f_2(x)\, $$ adding the distance $\mathrm{Adv}^{\mathrm{PRF}}_{F_{k_2}}(D_2)$ similarly as before. Since the xor of two uniformly random strings is just as uniform as a single one, we can move to the random function $$ f_3(x)\,, $$ without any degradation in advantage. The total advantage is the sum of all these steps: $$ \mathrm{Adv}^{\mathrm{PRF}}_{F_{k_1,k_2}}(D) \le \mathrm{Adv}^{\mathrm{PRF}}_{F_{k_1}}(D_1) + \mathrm{Adv}^{\mathrm{PRF}}_{F_{k_2}}(D_2) + 0\,. $$