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

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?

• Your construction seems problematic. A distinguisher can distinguish between a real random function $f(m) = f_1(m) \oplus f_2(m) = y$ and a function $F(m) = F_{k_1, k_2}(m) \oplus F_{k_2, k_1}(m) = 0$ if y = 1 which is a likelyhood of 0.5 if the order of $k_1$ and $k_2$ matter. – Martin Kromm Sep 21 '19 at 13:19
• I'm sorry, but I'm not really sure what you are trying to say here. There is no order to $k_1, k_2$. I"m not sure why 𝐹(𝑚)=𝐹𝑘1,𝑘2(𝑚)⊕𝐹𝑘2,𝑘1(𝑚)=0 if y = 1 either. Could you explain further? – Math Lady Sep 22 '19 at 0:53

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\,.$$