Given that F is a secure PRF in the example $$F'(k,x)= F(k,x)\mathbin\|F(k,F(k,x))$$ I'm not sure why this isn't a secure PRF? Under what condition $F(k, F(k,x))$ when concatenated to $F(k,x)$ the adversary will be able to distinguish between $F'$ and true random function?

  • 1
    $\begingroup$ What happens if a second query to F can depend on the output of a first query? How would this allow you to break this? $\endgroup$ – SEJPM Oct 26 '20 at 19:39
  • 1
    $\begingroup$ A related question Is $f(K, f(K, x))$ a pseudorandom function? $\endgroup$ – kelalaka Oct 26 '20 at 20:06
  • 1
    $\begingroup$ What's the relationship between input/output domains of $F$ for the definition to make sense? Then what's $F'$ input/output domains? Now assume you have a black box that implements $F'$ for a fixed unknown $k$, and made a first query with some $x$ of $\ell\gg1$ bits, and got some answer $y$. How do you craft the second query to confirm beyond reasonable doubt that the blackbox implements $F'$? Note: the question is easier than for $F(k,F(k,x))$. $\endgroup$ – fgrieu Oct 26 '20 at 20:13
  • 1
    $\begingroup$ @Alex: you are on good tracks, but you need to reformulate that in the framework of an attack/adversary/algorithm in a position to use an oracle/block box/API that (sometime) implements $F'$ without giving a direct access to $F$, since the question is about $F'$ being a PRF. That oracle/block box/API is assumed to sometime use, in the manner defined by $F'(k,x)= F(k,x)\mathbin\|F(k,F(k,x))$, a sub-oracle/block box/API implementing $F$; and sometime implement a true PRF. The goal of the attack/adversary/algorithm is to distinguish between the two cases. $\endgroup$ – fgrieu Oct 27 '20 at 6:48
  • 1
    $\begingroup$ @Alex: Yes, you got it. Depending on the academic context, this is a correct answer; or it needs more formalization, like: stating what you described as an algorithm, called the distinguisher, invoking $F'$ as a sub-function, producing an output 1 if it concludes $F'$ is of the form $F(k,x)\mathbin\|F(k,F(k,x))$; computing the (or a minimum) advantage of that distinguisher w.r.t. an algorithm that outputs 1 or 0 at random, and show that it is non-vanishing when the parameter controlling the width of things increases. You could do this and make an answer out of it. $\endgroup$ – fgrieu Oct 30 '20 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.