See Problem 11.3 for a definition of one-way for public-key encryption. Prove that any CPA secure public-key encryption scheme is also one-way. (You dont need to work (a) or (b) for this part.)

11.3 Say a public-key encryption scheme (Gen,Enc,Dec) for n-bit messages is one-way if any ppt adversary A has negligible probability of success in the following experiment:

Gen(1ⁿ) is run to obtain keys (pk,sk).

A message m {0,1}ⁿ is chosen uniformly at random, and a ciphertext c Enc_pk(m) is computed.

A is given pk and c, and outputs a message m'. We say A succeeds if m' = m. (a) Give a construction of a CPA-secure KEM in the random-oracle model based on any one-way public-key encryption scheme.

(b) Can a deterministic public-key encryption scheme be one-way? If not, prove impossibility; if so, give a construction based on any of the assumptions introduced in this book.