Show that G is not a PRF

Question

$\DeclareMathOperator{concat}{\|}$ I'm trying to do the following assignment:

1. Let $F : \{0,1\}^k \times \{0,1\}^n \to \{0,1\}^n$ be a PRF. Define function family $G : \{0,1\}^k \times \{0,1\}^{n-1} \to \{0,1\}^{2n}$, for all $x \in \{0,1\}^{n-1}$, by $$G_K(x) = F_K(0 \concat x) \concat F_K(x \concat 1).$$ Show that $G$ is not a PRF.

   [Remark: To do this, design an efficient PRF adversary $B$ that achieves an advantage close to 1. Remember the $B$ is an algorithm. As such it needs to specify precisely: What oracle queries does it make? What does it do with the answers it receives? How does it decide what guess to make?]

I provided an image of what I have attempted.

The symbol $\concat$ means concatenation. Can anyone can please provide some insight on how to solve this problem.

Answer 1

If the adversary takes $x, y \in \{0, 1\}^n$ such that $(0 \parallel x) = (y \parallel 1)$ then

$$G_K(x) = F_K(0 \parallel x) \parallel F_K(x \parallel 1)$$ $$G_K(y) = F_K(0 \parallel y) \parallel F_K(y \parallel 1) = F_K(0 \parallel y) \parallel F_K(0 \parallel x)$$

The left half of $G_K(x)$ is equal to the right half of $G_K(y)$, which lets the adversary distinguish $G$ from a random function.

Answer 2

@aventurin's answer is correct, and deserves to be selected. I'm going to give a cruder answer that might be helpful as well. One fruitful trick to approach this sort of problem is just to try and see what happens when you use very small values of of $n$. For example, if we try $n = 2$ and $n = 3$ we can just enumerate all possible inputs and see if we spot any patterns that might be generalizable to all choices of $n$.

For $n = 2$:

$$ \begin{align} G_K(0) & = & F_K(00) & \parallel \boxed{F_K(01)} \\ G_K(1) & = & \boxed{F_K(01)} & \parallel F_K(11) \end{align} $$

Gee, that looks promising: $G_K(0)$'s last two bits must be equal to $G_K(1)$'s first two bits (as I've highlighted by drawing boxes). Given a randomly chosen function of the same type as $G$, the probability that the last two bits of $G_K(0)$ are the same as the first two bits of $G_K(1)$ is $2^{-2}$. (Can you explain why?)

For $n = 3$, we just need to try the first two inputs in lexicographical order and we spot the same pattern:

$$ \begin{align} G_K(00) & = & F_K(000) & \parallel \boxed{F_K(001)} \\ G_K(01) & = & \boxed{F_K(001)} & \parallel F_K(011) \end{align} $$

Given a randomly chosen function of the same type as $G$, the probability that the last three bits of $G_K(00)$ are the same as the first three bits of $G_K(01)$ is $2^{-3}$.

You should be able to generalize this pattern to arbitrary choices of $n$, write the adversary as an algorithm, calculate its chances of success against $G$ and against a random function of the same type, and from that your adversary's advantage as a function of $n$.