Are these functions pseudo random? Why or why not? So I am stuck on this problem and have absolutely no intuition as to what the right answer is or how to prove it. Any help would be appreciated.

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}\rightarrow\{0,1\}^{2n}$, state whether $F'$ is a pseudorandom function.

a. $F_k'(x)=F_k(0||x)||F_k(1||x)$

b. $F_k'(x)=F_k(0||x)||F_k(x||1)$

The little bit of intuition that I have makes me think that a isn't pseudo random but b is because in a you know that a 1 was originally in the middle so maybe that helps, but I don't know why. Its mostly just a wild guess.

(here || denotes concatenation)
Whether $F′$ is a pseudorandom function revolves around: can it be efficiently distinguished from a random function? That is, can you design an experiment (distinguisher) that has better-than-random chance to recognize a box computing $F_k′(x)$ given $x$ for some random unknown fixed $k$, from one which computes some random function (a random oracle)?



For one of your two cases, you can, thus $F'$ is not a pseudorandom generator. To prove that, just find and expose how your distinguisher works, and prove that it works better than random.

Hint 1: one way is to find some number of distinct $x$ such that $F_k$ will be evaluated with the same input, and detect that with fair odds from the output of $F_k'$.

Hint 2: In the present situation, said number is at least 2.

Hint 3: The proof that the distinguisher works better than random requires $n&gt;2$, which can be assumed.



For the other case, you can't make a distinguisher , thus $F′$ is a pseudorandom generator. The usual formal proof technique is contraposition: assume a distinguisher for $F′$, and derive a distiguisher for $F$, which by hypothesis does not exists.

Here, there's a more intuitive approach: $F_k'(x)$ is made by concatenation of outputs of $F_k$; and such outputs are indistinguishable from random (for one not knowing $k$), except that the same input to $F_k$ yields the same output. Thus if the outputs of $F_k$ are for distinct inputs whenever we evaluate $F_k'$ for distinct inputs, then the overall output of $F_k'$ for distinct inputs is indistinguishable from random, and $F'$ is pseudorandom.