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?"
$\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
$\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
Not the answer you're looking for? Browse other questions tagged pseudo-random-function chosen-plaintext-attack or ask your own question.
Hot Network Questions
- When to add version numbers to documentation
- What should players roll to "deduce" a solution?
- What do the numbers on this 1960s anti-integration sign mean?
- Are all pure entangled states `robust'?
- Can I use potassium acetate instead of potassium carbonate?
- Could a US state allow non-citizens to vote in presidential elections?
- What is “a place with a lot of wind“ called in English?
- Spelling Bee Bee Bee
- Checking singularity of a matrix
- awk - count pattern in the entire column
- GMing with an overtuned skill monkey
- Would a President get to fill a Supreme Court vacancy just after he lost an election in November/December?
- Looking for a story about ancient sound recordings in stone
- Why pulmonary vein and artery are not like the rest of circulatory system?
- Why would an advanced civilization even want slaves?
- Why don't bypass ducts in jet engines narrow down the flow to accelerate it?
- Balance implications of +3 racial bonuses
- Which particles does the Higgs Field give mass to?
- Ordering a list of rules by its 4 last elements of LHS
- Can you find the datasheet for this IC
- Jupiter with a mobile phone and Celestron Astro FI 102mm Maksutov
- What is the meaning of "sticking out your tongue"?
- Why is the photon clock equivalent to all clocks?
- What is the relationship between communism and 'a classless system'?
