secure PRF or not

Question

I am new in Cryptography and I saw this question in a note I solved it but I'm not sure about my answers.

Let $F : \{0, 1\}^n × \{0, 1\}^n→ \{0, 1\}^n$ be a secure PRF (i.e. a PRF where the key space, input space, and output space are all $\{0, 1\}^n$) and say $n = 128$. Which of the following is a secure PRF. In the following functions, + operation indicates the binary sum module $2^n$ where an n-bit string is interpreted as number in $Z_{2^n}$ and $≪$ operation indicates left rotation.

1. $F ′(k1||k2), x) = F (k1, x) ⊕ F (k2, x)$
2. $F ′(k, x) = (x + k) ⊕ (x ≪ 1)$
3. $F ′(k, x) = (x + k) ⊕ (k ≪ 1)$
4. $F ′(k, x) = (x + k) ⊕ (k ≪ 1) ⊕ (x ≪ 1)$

I think number 1 is PRF because the input key of each F is different, and number 2, 3, 4 are PRF because $x+k$ term could be any string of $\{0, 1\}^n$. Is that correct?

Answer 1

I think number 1 is PRF because the input key of each F is different

That is correct, though I might not give full marks for your reasoning. The XOR of two PRFs is PRF. The probability that a random $k1||k2$ has $k1 = k2$ is negligible.

number 2, 3, 4 are PRF because $x+k$ term could be any string of $\{0, 1\}^n$. Is that correct?

This is wrong. You can come up with distinguishers for them. I've spoilered my solutions below if you want to try them individually.

2:

In the second case, you can calculate $(F'(k, x) \oplus x) - x$ to find the key, and thus find the value for any $x$ so it is not PRF.

3:

In the third case, you can look at the low bit: $f_1 = x_1 \oplus k_1 \oplus k_n$. So by calculating $k_1 \oplus k_n$ from one value of $F'$ you can predict the value for any $x$. Again, not PRF, since you have a distinguisher for the low bit.

4:

The fourth case reduces to the third, because you can just XOR out the $x \ll 1$ term.

Answer 2

Here's a more elaborate proof for number 1. Given a distinguisher $D'$ for $F'$, we construct a distinguisher $D$ for $F$ as follows: we first pick a uniform $k_2$ of length $n$, and we run $D'$. When $D'$ asks to call its oracle on a string $x$, we give it $O_D(x) \oplus F_{k_2}(x)$ instead of $O_{D'}(x)$, where $O_D$ (resp. $O_{D'}$) is the oracle of $D$ (resp. $D'$). At the end, we output whatever $D'$ outputs.

If $O_D$ implements $F_{k_1}$ for a uniform $k_1$, $O_D(x) \oplus F_{k_2}(x)$ will be distributed identically to $F'_{k_1||k_2}(x)$ for a uniform $k_1||k_2$, whereas if $O_D$ implements a uniform $f$, it will be distributed identically to $f(x)$ for a uniform $f$. Those two cases can be distinguished by $D'$ by hypothesis, and thus $D$ can distinguish $F_{k_1}$ from a uniform $f$.