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?"

Improve this question
$\endgroup$
2
  • $\begingroup$ Thank you Geoffroy, that is very helpful (& a complete answer!) --m $\endgroup$
    – Martin Hofmann
    Apr 3 '17 at 11:42
  • $\begingroup$ Happy to help :) If you got the answer you were looking for, you should mark it as accepted. $\endgroup$
    – Geoffroy Couteau
    Apr 5 '17 at 23:16
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.

Improve this answer
$\endgroup$
4

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.