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$

closed as unclear what you're asking by kodlu, fkraiem, mikeazo Sep 14 '17 at 0:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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