2
$\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"?

$\endgroup$
3
$\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] $$

$\endgroup$
  • $\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$ – Tom Ridley Nov 13 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$ – Dmitry Khovratovich Nov 15 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$ – Dmitry Khovratovich Nov 15 at 9:27

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.