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?"
11
$\begingroup$
$\endgroup$
-
$\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
12
$\begingroup$
$\endgroup$
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.
answered Mar 31 '17 at 18:18
-
-
1$\begingroup$ As soon as my internet connection allows me to open pdfs, yes $\endgroup$ – Geoffroy Couteau Mar 31 '17 at 18:26
-
$\begingroup$ icsi.berkeley.edu/pubs/techreports/tr-89-31 groups.csail.mit.edu/cis/pubs/shafi/1986-jacm.pdf $\hspace{.4 in}$ $\endgroup$ – user991 Mar 31 '17 at 20:07
-
$\begingroup$ Thanks, finally got a correct connection (was in the train), I added references. $\endgroup$ – Geoffroy Couteau Mar 31 '17 at 20:26
