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.