11
$\begingroup$

It is well-known that a pseudorandom function (PRF) can be used to build a CPA-secure symmetric cryptosystem. My question: is PRF necessary for this, i.e., can one show something like "If there exists an IND-CPA scheme then there exist PRF?"

$\endgroup$
2
  • $\begingroup$ Thank you Geoffroy, that is very helpful (& a complete answer!) --m $\endgroup$ Apr 3, 2017 at 11:42
  • $\begingroup$ Happy to help :) If you got the answer you were looking for, you should mark it as accepted. $\endgroup$ Apr 5, 2017 at 23:16

1 Answer 1

14
$\begingroup$

If there exists an IND-CPA symmetric encryption scheme (where the key is shorter than the total length of the messages, i.e., the scheme is not the OTP), then there are one-way functions. A sequence of articles have shown how to construct pseudorandom generators out of OWFs (culminating with this paper). By the GGM construction, pseudorandom generators can be used to construct PRFs. Therefore, IND-CPA symmetric encryption implies PRFs.

$\endgroup$
4

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.