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?

  • $\begingroup$ 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. $\endgroup$ Sep 21, 2019 at 13:19
  • $\begingroup$ 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? $\endgroup$
    – Math Lady
    Sep 22, 2019 at 0:53

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


Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.