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$ – Martin Kromm Sep 21 '19 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 '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\,. $$


Your Answer

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

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