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?

• 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. Nov 18, 2020 at 12:12
• @Maeher So what can we say about the pseudorandomness of $1.$? Nov 18, 2020 at 12:32
• Hint: if you xor something with a value that's uniformly and independently distributed, what's the distribution of the result? Nov 18, 2020 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? Nov 18, 2020 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. Nov 18, 2020 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
Nov 21, 2020 at 20:55
• 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...) Nov 21, 2020 at 21:08
• 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. Nov 21, 2020 at 21:09
• 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
Nov 21, 2020 at 21:20
• 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? Nov 21, 2020 at 21:34

Since @fgrieu was interested in question 2, I'm going to break with site policy and give a full answer for that part, even though this is almost certainly homework.

Theorem. Let $$F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$$ be a PRF. Then, $$F_2 : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$$, defined as $$F_2(k,x) := F(F(k,0^n),x)$$ is also a PRF.

Before we give a formal proof, let's build some intuition why this should be the case. Note that the inner invocation of $$F$$ is not on some part of the input, but instead on a constant (i.e., $$0^n$$). This means that once we fix the key $$k$$, the key used by the outer invocation of $$F$$ for all evaluations of $$F_2$$ is a fixed key $$k' := F(k,0^n)$$. Since $$k$$ is not used elsewhere in the construction, $$k'$$ should, by the security of the underlying PRF, be indistinguishable from a uniformly random key $$k''$$, as long as $$k$$ is chosen uniformly at random. This would mean than an oracle evaluating $$F_2(k,\cdot)$$ and an oracle evaluating $$F(k,\cdot)$$ should in fact be indistinguishable. Since $$F(k,\cdot)$$ is already known to be indistinguishable from a uniformly chosen random function $$f(\cdot)$$ and indistinguishablity (in the asymptotic sense) is transitive, it would follow that $$F_2$$ must also be a PRF.

So let's formalize this intuition.

Proof. Let $$A$$ be an arbitrary PPT algorithm with $$\Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|=\epsilon(n).$$ We are looking to give a negligible upper bound for $$\epsilon$$. To do this we will prove a series of claims.

Claim 1. $$\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$$

Consider the following adversary $$B$$ against the PRF security of $$F$$. Upon input $$1^n$$ and given access to an oracle, $$B$$ queries $$0^n$$ to the oracle an receives back a value $$k'$$. It then invokes $$A$$ on input $$1^n$$. Whenever $$A$$ sends a query $$x$$ to its oracle, $$B$$ responds by computing $$y:=F(k',x)$$. Eventually, $$A$$ will output a bit $$b$$ which $$B$$ also outputs.

It is easy to see that $$\Pr_k[B^{F(k,\cdot)}(1^n)=1] = \Pr_k[A^{F(F(k,0^n),\cdot)}(1^n)=1]$$ and $$\Pr_f[B^{f(\cdot)}(1^n)=1] = \Pr_f[A^{F(f(0^n),\cdot)}(1^n)=1].$$ Further, since $$F$$ is a secure PRF, it must hold that $$\Bigl|\Pr_k[B^{F(k,\cdot)}(1^n)=1]-\Pr_f[B^{f(\cdot)}(1^n)=1]\Bigr|\leq \mathsf{negl}(n)$$ and the claim follows.

Claim 2. $$\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] = \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]$$

To see that this is the case, it is easiest to think of $$f$$ as being lazily sampled when queried. Since $$f$$ is only ever invoked on $$0^n$$, sampling $$f$$ is equivalent to simply sampling $$f(0^n)$$ once as a uniformly random value $$k\in \{0,1\}$$, which is identical to the right hand side.

Claim 3. $$\Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$$

This claim is in fact just a restatement of the assumption that $$F$$ is a PRF and thus follows trivially.

Using the triangle inequality, we can conclude \begin{align} \epsilon(n) =&\quad \Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|\\ \leq&\quad\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr|\\ &+ \Bigl|\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] - \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]\Bigr|\\ &+ \Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr|\\ &\leq 2\cdot\mathsf{negl}(n) \end{align} and the theorem statement immediately follows.$$\tag*{\square}$$