# Which of those functions are PRFs?

Assume that $$F: \{0,1 \}^n \rightarrow \{0,1 \}^n$$ is PRF. Examine if the following functions are PRFs:

\begin{align} 1. \, F_1(k,x) &= F(k,x) \oplus x \\ 2. \, F_2(k,x) &= F\left(F(k,0^n), x\right) \\ 3. \, F_3(k,x) &= F\left(F(k,0^n), x\right)|| F(k,x) \end{align}

where $$||$$ denotes concatenation.

## Attempt:

For $$1.$$ a standard distinguisher would be: $$x_1 \oplus x_2 == y_1 \oplus y_2$$, where $$x_1, x_2$$ are two inputs and $$y_1, y_2$$ are their outputs respectively. So $$F_1$$ is not a PRF.

For $$2.$$ I believe that $$F(k,0^n) = k'$$ acts as a key, so $$F_2(k',x) = F(k',x)$$ should still be a PRF.

For $$3.$$ I would say that the concatenation of two PRFs would still be a PRF, since you combine two pseudorandom outputs together to yield $$F_3$$'s output.

Can you verify my results?

New contributor
Paris is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• For 1: $y_1\oplus y_2 = F(k,x_1) \oplus F(k,x_2) \oplus x_1 \oplus x_2$, which will only equal $x_1 \oplus x_2$ if $F(k,x_1) = F(k,x_2)$. For 3. Consider whether there's a way to find out the key used in the left half of the output. – Maeher Nov 18 at 12:12
• @Maeher So what can we say about the pseudorandomness of $1.$? – Paris Nov 18 at 12:32
• Hint: if you xor something with a value that's uniformly and independently distributed, what's the distribution of the result? – Maeher Nov 18 at 13:55
• After processing your comment, I believe that: for $1.$ since there is a neglible chance that $F(k,x_1) = F(k,x_2)$, then there's no way to distinguish between $F_1$ and a proper random function. For $3.$, if you set $x = 0^n$, the right half of the output is the key used in the left half, so not a PRF. Am I correct? – Paris Nov 18 at 14:49
• 1. That just means that your distinguisher doesn't work.You would generally be expected to do a proof by reduction to the security of $F$. 3. sounds like you're on the right track. – Maeher Nov 18 at 14:58

Unfortunately, I don't have time to go into every detail, but maybe it's enough to get you on the right track.

1. Is a PRF.

Proof Idea:

Assume we have a distinguisher $$\mathcal{D}_{F_1}$$ distinguishing $$F_1$$ from a random function with non-negligible probability. Then we can construct a distinguisher $$\mathcal{D}_F$$ distinguishing $$F$$ from a random function with non-negligible probability.

$$\mathcal{D}_F$$ is given access to an oracle $$f(\cdot)$$ that's either $$F(k, \cdot)$$ or a random function $$g(\cdot)$$.

$$\mathcal{D}_F$$ runs $$\mathcal{D}_{F_1}$$ and can answer its queries. When $$\mathcal{D}_{F_1}$$ requests $$x$$, $$\mathcal{D}_{F}$$ queries $$f$$ on $$x$$ and returns $$f(x) \oplus x$$ to $$\mathcal{D}_{F_1}$$. This simulates $$\mathcal{D}_{F_1}$$'s queries: when $$f$$ is $$F(k, \cdot)$$ we return $$F(k, x) \oplus x$$, which is exactly $$F_1(k, x)$$.

When $$\mathcal{D}_{F_1}$$ is done, we replicate its output: when it says it's talking to $$F_1$$ (output = 1), $$\mathcal{D}_F$$ outputs the same. When it says it's talking to a random function (output = 0), $$\mathcal{D}_F$$ outputs the same.

You would now have to prove that the advantage: $$|\Pr[\mathcal{D}_F^{F(k, \cdot)}(1^n)=1] - \Pr[\mathcal{D}_F^{g(\cdot)}(1^n) = 1]|$$ of $$\mathcal{D}_F$$ is non-negligible, using the assumption that the advantage of $$\mathcal{D}_{F_1}$$ is non-negligible.

This last part is usually the hard part, where errors can come up silently, so be careful about skipping steps or making invalid assumptions.

2.

Is a PRF.

Intuitively, the question of whether this is a PRF seems to reduce to whether an adversary can predict $$F(k, 0^n)$$. However, a function where this is possible for non-negligibly many $$k$$ is not a PRF.

3.

Not a PRF.

We can construct a distinguisher $$\mathcal{D}$$ with non-negligible advantage. $$\mathcal{D}$$ is given access to $$f(\cdot)$$, which is either $$F_3(k, \cdot)$$ or a random function. I denote the first half of $$z$$ as $$z_L$$ and the second half of $$z$$ as $$z_R$$.

1. $$\mathcal{D}$$ queries $$y^0 = f(0)$$
2. $$\mathcal{D}$$ computes $$y^1 = F(y^0_R, x)$$ for some random $$x$$.
3. $$\mathcal{D}$$ queries $$y^2 = f(x)$$
4. If $$y^1 = y^2_L$$, $$\mathcal{D}$$ outputs that $$f$$ is $$F_3$$.
5. Otherwise, $$\mathcal{D}$$ outputs that $$f$$ is a random function.

$$\mathcal{D}$$ has non-negligible advantage: if $$f$$ is $$F_3$$, then $$y^1 = y^2_L$$:

$$y^1 = F(y^0_R, x) = F(f(0^n), x) = F(F(k, 0^n), x)$$

$$y^2_L = f(x)_L = F_3(k, x)_L = F(F(k, 0^n), x)$$

The probability that this holds when $$f$$ is a random function is negligible.

Hope I could help!

• I'm still uncertain about the claim 2, and dubious about the argument made. What about if there's a random-like subset $\mathcal S$ of $\{0,1\}$, and when $k\in\mathcal S$ then $F(k,x)=0^n$, else if $x=0^n$ then $F(k,x)$ is a pseudo-random element of $\mathcal S$, else $F(k,x)$ is a true PRF of $(k,x)$? Now $F_2(k,x)$ is always $0^n$, yet an adversary can't predict $F(k,0^n)$. – fgrieu yesterday
• That's true, the adversary doesn't need to predict - after all it's a distinguishing game. I was only giving some intuition on how this proof could be approached, but I cannot even guarantee my answer is correct, since I have not proved it. (cont...) – cisnjxqu yesterday
• As you say, $F$ can have some weak keys $k \in S$, where the output of $F(k, x) = 0^n$. However, $S$ cannot be noticeably large, otherwise $F$ wouldn't be a PRF, since the adversary would be able to easily determine that the output is $0^n$ for all $x$ for noticeably many $k$. Therefore, $S$ must be some negligible fraction of the key domain, and will give the adversary only negligible advantage. – cisnjxqu yesterday
• Notice that my weak key set has size such that it's chosen with negligible probability $2^{-n/2}$, thus $F(k,x)$ can only be distinguished from random by one applying the algorithm implementing $F$ (feeding the result obtained from the oracle queried with $x=0^k$ into the key input of that algorithm). If the definition of the PRF challenge allows that, then indeed $F_2$ is demonstrably a PRF when $F$ is, otherwise my counterexampel $F$ seems to be a PRF, but definitely $F_2$ is not. – fgrieu yesterday
• Could you elaborate on some things: Do you mean that $|S| = 2^{\frac{n}{2}}$? If the definition of the PRF game (?) allows the adversary to evaluate $F(k, x)$ for some adversary chosen $k$ and $x$, then $F_2$ is a PRF? Could you explain why $F_2$ would not be a PRF if that's not the case? – cisnjxqu yesterday