0
$\begingroup$

I have recently understood how we can construct a pseudorandom function from a PRG. However, I would like to prove the reverse - how can I construct a PRG from a PRF?

$\endgroup$
1
  • $\begingroup$ This direction is a bit easier. As a hint: think of what is the distribution of a PRF key with a random key and evaluated at $n$ distinct points. $\endgroup$ Nov 17, 2022 at 21:00

1 Answer 1

1
$\begingroup$

I suggest you go through the section 4.4.4 of the book titled "A Graduate Course in Applied Cryptography" written by Boneh. In this section, the PRG is constructed by this way:

$G(k):=(F(k,x_1),...,F(k,x_l))$

where $G(\cdot)$ is a PRG, and $F(\cdot,\cdot)$ is a PRF.

Therefore, we can prove that: If F is a secure PRF, then the PRG $G$ described above is a secure PRG.

$\endgroup$

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.