# 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)

• Seems to me that $F'$ is $F':\{0,1\}^n\times\{0,1\}^{n}\rightarrow\{0,1\}^{2n}$, right? Without the $-1$ for $n$ – Maarten Bodewes Feb 17 '17 at 12:08
• @Maarten Bodewes: the -1 is correct; that's what allows insertion of an extra bit, and match the characteristics of $F$, which is length preserving, thus has $n$-bit input and output given the output size $2n$ of $F'$. Also that makes $F$ used with the same key and input/output size. That exercise is quite nice. – fgrieu Feb 17 '17 at 12:52

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>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.

• Thanks this is really useful. So now I think that b is not a PRF because you could have two distinct x and x' that were the same except for the head and tail of each, that then became equivalent when 0 is prepended on x and 1 appended on x' – A-P Feb 17 '17 at 13:36
• @A-P: "the same except for the head and tail of each" is not precisely the condition that makes $x$ and $x'$ suitable; try with $n=8$, $x=\mathtt{0001111}$, $x'=\mathtt{1001110}$, which match that condition. But I see that you get the idea. Note to newcomers: thanks is implemented using the upvote/uparrow button on the left of the answer; that solved it, and is the best answer would be the accept/checkbox button (not that I care much, but that's the design) – fgrieu Feb 17 '17 at 13:50
• @A-P That's the right way, and there are a lot of examples. Actually half of the values for $x,x'$ can be used to construct this, and appending $1$ at the end / removing $0$ from the beginning makes finding the match easy. The most basic example is $x = 1, x' = 0$, padded to the required length. – tylo Feb 17 '17 at 14:43
• @tylo: values of $x$ starting with a 0 or ending with a 1 (thus 75% of $x$ these when $n>2$) can be used and have a matching $x′$; but I do not see why it would be that half of the values for $(x,x')$ can be used [if that's what you meant]; and why $x$ and $x′$ are the same except for the head and tail of each (a shift is involved, except for very few $x$). – fgrieu Feb 17 '17 at 17:07
• @fgrieu I ment half of all possible values can be used for $x$ (those ending with $1$), and half of all possible values can be used for $x'$ (starting with $0$), I was thinking of them separately. – tylo Feb 19 '17 at 1:07