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?

  • $\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$ Feb 19, 2021 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, 2021 at 19:41
  • 1
    $\begingroup$ There's a full proof of the statement in one of the answers. $\endgroup$
    – Maeher
    Feb 19, 2021 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, 2021 at 7:42


Browse other questions tagged or ask your own question.