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?"
Asked
Active
Viewed 1,485 times
11
-
Thank you Geoffroy, that is very helpful (& a complete answer!) --m – Martin Hofmann Apr 03 '17 at 11:42
-
Happy to help :) If you got the answer you were looking for, you should mark it as accepted. – Geoffroy Couteau Apr 05 '17 at 23:16
1 Answers
14
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.
Geoffroy Couteau
- 18,016
- 2
- 43
- 59
-
-
1As soon as my internet connection allows me to open pdfs, yes – Geoffroy Couteau Mar 31 '17 at 18:26
-
http://www.icsi.berkeley.edu/pubs/techreports/tr-89-31 http://groups.csail.mit.edu/cis/pubs/shafi/1986-jacm.pdf $\hspace{.4 in}$ – Mar 31 '17 at 20:07
-
Thanks, finally got a correct connection (was in the train), I added references. – Geoffroy Couteau Mar 31 '17 at 20:26