# 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$ 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 exist.

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