3
$\begingroup$

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"?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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] $$

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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))$? $\endgroup$ Commented Nov 13, 2019 at 6:30
  • $\begingroup$ (1) It is not the output of a truly RF as long as there are distinct $x_0$ and $x_1$ $\endgroup$ Commented Nov 15, 2019 at 9:25
  • $\begingroup$ (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$. $\endgroup$ Commented Nov 15, 2019 at 9:27

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.