Problem 1:
1. Please describe one-time pad encryption scheme.
2. Please show the one-time pad encryption scheme is perfectly secure.
3. Let M be the message space, and K the key space of the perfectly secure one-time pad encryption scheme. Please show |K| ≥ |M|.
Problem 2:
1. Define the CPA-security notion for symmetric key encryption = (Gen; Enc;Dec).
2. Let II = (Gen; Enc;Dec) where Enc is a deterministic encryption algorithm. Please prove that such cannot achieve the CPA-security notion defined in item 1.
3. Provide the security definition of pseudorandom function (PRF).
4. Let F be a PRF. Please construct a CPA-secure private-key encryption scheme based on such F.
5. Please prove that the private-key encryption scheme you constructed in item 4 is CPA-secure if the underlying PRF F is secure.