# Wrong Proof of Secure PRF

Disclaimer, this is not homework; I found the question statement here: Security of this PRF

To restate the question:

Given $$F$$ a secure PRF with input size $$\lambda$$. Define $$F'$$ as $$F'(k,x\mathbin\|x') = F(k, 0\mathbin\|x)\oplus F(k, 1\mathbin\|x')$$ with $$x$$ and $$x'$$ of $$\lambda-1$$ bits. Is $$F'$$ a secure PRF?

The given answer is no and it's clear that the PRF $$F'$$ is not secure. But I tried to provide a false proof that $$F'$$ is secure (but it's not) and cannot see what step the proof goes wrong.

First, to restate the counterexample:

More specifically, for sake of simplicity let $$F'_k$$ be a keyed PRF $$F'$$ with key $$k$$ from the family of unkeyed PRFs $$\{F' : \{0, 1\}^{2(\lambda - 1)} \times \{0, 1\}^{2(\lambda - 1)} \to \{0, 1\}^{\lambda - 1} \}$$ and consider the following $$\mathsf{PPT}$$ adversary $$\mathcal{A}$$. $$\mathcal{A}$$ asks for the evaluation of the oracle $$\mathcal{O}$$ on $$x_0 \mathbin\| x_1$$, $$x_0 \mathbin\| x_2$$, $$x_1 \mathbin\| x_2$$, and $$x_1 \mathbin\| x_1$$. Then $$\mathcal{A}$$ computes the XOR of the first three oracle outputs and checks if the XOR is equal to the fourth oracle output. Observe that if $$\mathcal{A}$$ is given oracle access to $$F'_k$$, then $$\mathcal{A}$$ receives \begin{align*} F'_k (x_0 \mathbin\| x_1) &= F_k (0 \mathbin\| x_0) \oplus F_k (1 \mathbin\| x_1)\\ F'_k (x_0 \mathbin\| x_2) &= F_k (0 \mathbin\| x_0) \oplus F_k (1 \mathbin\| x_2)\\ F'_k (x_1 \mathbin\| x_2) &= F_k (0 \mathbin\| x_1) \oplus F_k (1 \mathbin\| x_2)\\ F'_k (x_1 \mathbin\| x_1) &= F_k (0 \mathbin\| x_1) \oplus F_k (1 \mathbin\| x_1) \end{align*} and the XOR of the first three is exactly equal to the fourth and $$\mathcal{A}$$ guesses correctly with probability 1 given this case of the oracle. In the random case, $$\mathcal{O}$$ is equal to some truly random function $$U$$ and receives $$U(x_0 \mathbin\| x_1) \oplus U (x_0 \mathbin\| x_2) \oplus U (x_1 \mathbin\| x_2)$$ is unlikely to be equal to $$U (x_1 \mathbin\| x_1)$$, namely the probability is negligible. Hence $$\mathcal{A}$$ is a distinguisher.

Here is my "false proof" in an attempt at proving the statement "$$F'$$ is a secure PRF" and I'd really appreciate clarification on what step is incorrect.

Suppose $$F_k'$$ is not a PRF. Then there exists a $$\mathsf{PPT}$$ distinguisher $$\mathcal{A}'$$ and a constant $$c$$ and natural number $$n \in \mathbb{N}$$ such that $$\mathcal{A}'$$ distinguishes $$F_k'$$ from a truly random function with distinguishing advantage $$\geq \frac{1}{n^c}$$. We now construct a distinguisher $$\mathcal{A}$$ (an oracle machine with access to $$\mathcal{O}$$ which is either from PRF family $$\{F\}$$ or truly random function $$\{U\}$$) for $$F$$ as follows. $$\mathcal{A}$$ runs $$\mathcal{A}'$$. $$\mathcal{A}'$$ asks for queries of the form $$x_0 \mathbin\| x_1$$ as described above and $$\mathcal{A}$$ then queries the oracle $$\mathcal{O}$$ with $$0 \mathbin\| x_0$$ and $$1 \mathbin\| x_1$$, computes the XOR $$\mathcal{O}(0 \mathbin\| x_0) \oplus \mathcal{O}(1 \mathbin\| x_1)$$, and sends that to $$\mathcal{A}'$$. $$\mathcal{A}'$$ will query polynomially many times in $$\mathcal{A}'$$'s input length so $$\mathcal{A}$$ will have to make twice as many, namely $$O((2(\lambda-1))^l)$$ queries for some constant $$l$$, which is still polynomial in $$\lambda$$. Finally, $$\mathcal{A}$$ will output whatever $$\mathcal{A}'$$ outputs. Note then $$\Pr[\mathcal{A}^{\{F\}}(1^{\lambda}) = 1] = \Pr[\mathcal{A}'^{\{F'\}}(1^{2(\lambda -1)}) = 1]$$ by construction since $$\mathcal{A}$$ effectively simulates oracle access to $$\{F'\}$$ when $$\mathcal{O} = F_k$$ for some $$k$$. If $$\mathcal{O} = \{U\}$$ for truly random functions $$U$$, then $$\Pr[\mathcal{A}^{\{U\}}(1^{\lambda}) = 1] = \Pr[\mathcal{A}'^{\{U\}}(1^{2(\lambda -1)}) = 1]$$ because $$U(0 \mathbin\| x_0) \oplus U(1 \mathbin\| x_1)$$ is still truly random. Then the distinguishing advantage of the new adversary $$\mathcal{A}$$ is also non-negligible and hence $$F$$ is not a secure PRF.

Again, where did I go wrong in this "false proof"?

The problem is in the last equation: $$Pr[\mathcal{A}^{\{U\}}(1^{\lambda})=1]=Pr[\mathcal{A'}^{\{U\}}(1^{\lambda})=1]$$
It does not hold because $$\mathcal{A}^{\{U\}}$$ is the result of $$\mathcal{A}'$$ using $$U$$ instead of $$F_k$$. This is actually equivalent to $$F'$$ and will be distinguished by $$\mathcal{A}'$$, so we get $$Pr[\mathcal{A}^{\{U\}}(1^{\lambda})=1]=Pr[\mathcal{A'}^{\{F'(U)\}}(1^{\lambda})=1]\neq Pr[\mathcal{A'}^{\{U\}}(1^{\lambda})=1]$$
• Thanks for the response, Dmitry! To clarify: (1) the xor of two truly random function outputs, namely, $U(0 || x_0) \oplus U(1 || x_1)$ is not the output of a truly random function; in fact, using $U$ instead of $F_k$ in the manner used by $\mathcal{A}$ results in the same XOR behavior in both cases, right? (2) Is the last statement the easiest way or a complete explanation to see that $\mathcal{A}'$ using $U$ instead of $F_k$ is equivalent to $F'$? (3) Lastly in the oracle access notation $\mathcal{A}'^{\{F'(U)\}}$, why is $U(0 || x_0) \oplus U(1 || x_1)$ equivalent to $F'_k(U(x_0 || x_1))$? – Tom Ridley Nov 13 at 6:30
• (1) It is not the output of a truly RF as long as there are distinct $x_0$ and $x_1$ – Dmitry Khovratovich Nov 15 at 9:25
• (2) Well, maybe one can get a more elaborate explanation. (3) It is not equivalant to $F'_k(U(x_0||x_1))$, by $F'(U)$ I denote the $F'$ where $F$ is replaced by $U$. – Dmitry Khovratovich Nov 15 at 9:27