1
$\begingroup$

Suppose $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$

$$F'(k, x) = F(F(k, 0^n), x) \; $$

Trying to get the intuition to prove it is secure PRG else given will be not by contrapositive... but cannot from the reduction of it. How to formulate it to prove it is secure?

$\endgroup$
4
  • $\begingroup$ A general strategy to show that the new construction is secure is: assume that the new construction $F'$ is insecure meaning you know an attacker $\mathcal A'$ that breaks it, then you need to show that you can create an attacker $\mathcal A$ that is based on $\mathcal A'$ and that breaks $F$ $\endgroup$ – Marc Ilunga Feb 19 at 13:10
  • $\begingroup$ @Maeher question is exactly that..........I also mention contrapositive but can you more elaborate on how-to from reduction here ...as i am stuck at it? $\endgroup$ – Sam Feb 19 at 19:41
  • 1
    $\begingroup$ There's a full proof of the statement in one of the answers. $\endgroup$ – Maeher Feb 19 at 20:08
  • $\begingroup$ @Maeher thanks ... I will see that..it was given at the bottom I didn't observe that. $\endgroup$ – Sam Feb 20 at 7:42