2
$\begingroup$

The definition of a pseudorandom function is:

Let $F:\{0,1\}^*\times \{0,1\}^* \to \{0,1\}^*$ be an efficient, length-preserving, keyed function. $F$ is a pseudorandom function if for all probabilistic polynomial-time distinguishers $D$, there is a negligible function $\text{negl}$ such that: $$\bigl|Pr[D^{F_k(\cdot)}(1^n)=1]-Pr[D^{f(\cdot)}(1^n)=1]\bigr|\leq \text{negl}(n),$$ where the first probability is taken over uniform choice of $k\in \{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $f\in \text{Func}_n$ and the randomness of $D$.

We want to show whether or not the following function is a pseudorandom function.

Let $F$ be a length-preserving pseudorandom function. For the following construction of a keyed function $F':\{0,1\}^n\times \{0,1\}^{n-1}\to \{0,1\}^{4n}$, state whether $F'$ is a pseudorandom function: if yes prove it, if not show an attack. $$F'_k(x)\stackrel{\text{def}}{=}F_k(0\parallel x\parallel 0)\parallel F_k(0\parallel x\parallel 1) \parallel F_k(1 \parallel x \parallel 0) \parallel F_k(1 \parallel x \parallel 1).$$

The problem I am having is applying the definition to the function $F'$. Can I have some assistance?

Remark The question that been linked to this question, does not use the definition to show that it's pseudorandom function.

Looking at a similar problem. I started with strings of length $n=2$, $$F'_k(0)\stackrel{\text{def}}{=}F_k(000)\parallel F_k(001) \parallel F_k(100) \parallel F_k(101),$$ and $$F'_k(1)\stackrel{\text{def}}{=}F_k(010)\parallel F_k(011) \parallel F_k(110) \parallel F_k(111).$$ However there isn't a connect between the two. The same is true for $n=3$. Hence why I believe that this is a pseudorandom function. Now I just need to formally prove it is so.

Is the following correct?

Attempt at a proof: We claim that $F'_k$ is a pseudorandom function. To prove this we will do a proof by contrapositive. i.e. If $F'$ is not a pseudorandom function, then $F$ is not a pseudorandom function.

Suppose $F'$ is not be a pseudorandom function. We want to show that $F$ is not a pseudorandom function. Since $F'$ is not a pseudorandom function, then its values on any two (or more) points are correlated. However since $F'$ is composed of $F$ then this implies that $F$ has values on any two (or more) points which are correlated. Hence $F$ is not a pseudorandom function.

$\endgroup$
  • $\begingroup$ So I see that I need to do this as a proof by contradiction. i.e. Suppose $F'$ is not a pseudorandom function and then show $F$ is also not a pseudorandom function. I can see why this is true, as because $F'$ is made up of $F$'s but the formal proof is still unclear $\endgroup$ – Username Unknown Sep 13 '17 at 14:49
  • $\begingroup$ I think this is answerable, but you should cite the sources for your quotes. $\endgroup$ – otus Sep 14 '17 at 4:41