3
$\begingroup$

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)

Improve this question
$\endgroup$
2
  • $\begingroup$ Seems to me that $F'$ is $F':\{0,1\}^n\times\{0,1\}^{n}\rightarrow\{0,1\}^{2n}$, right? Without the $-1$ for $n$ $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 17, 2017 at 12:08
  • $\begingroup$ @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. $\endgroup$
    – fgrieu ♦
    Commented Feb 17, 2017 at 12:52

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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' $\endgroup$
    – A-P
    Commented Feb 17, 2017 at 13:36
  • 1
    $\begingroup$ @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) $\endgroup$
    – fgrieu ♦
    Commented Feb 17, 2017 at 13:50
  • $\begingroup$ @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. $\endgroup$
    – tylo
    Commented Feb 17, 2017 at 14:43
  • $\begingroup$ @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$). $\endgroup$
    – fgrieu ♦
    Commented Feb 17, 2017 at 17:07
  • $\begingroup$ @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. $\endgroup$
    – tylo
    Commented Feb 19, 2017 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.