Consider two public key encryption schemes, an inner scheme Π = (gen, enc, dec), and an outer scheme Π' = (gen', enc', dec'), where λ is the security parameter. We say Π and Π' are compatible if the plaintext space of the outer scheme Π' is identical to the ciphertext space of the inner scheme Π. Based on the compatible schemes Π and Π', we may use the inner scheme to encrypt some data, and then use the outer scheme to encrypt the encrypted data further. Formally, we design a new public key encryption scheme II = (Gen, Enc,Dec) as follows.
The key generation algorithm (PK, SK) ← Gen(1λ):
- Compute (pk, sk) ← gen(1λ)
- Compute (pk', sk') ← gen'(1λ)
- Set PK := (pk, pk') and SK := (sk, sk')
The encryption algorithm C ← EncPK(m):
- Compute c ← encpk(m)
- Compute C ← enc'pk'(c)
The decryption algorithm m' ← DecSK(C):
- Compute c' ← dec'sk'(C)
- Compute m ← decsk (c)
Assume all schemes Π, Π' and II are correct. We here intend to investigate the security of the new scheme II. Please choose one of the following two problems, and provide your solutions. If you believe the new scheme is secure, then you are supposed to provide a clear reduction proof by using proper notations. If you believe it is insecure, then you are supposed to give a counter-example, or at least provide convincing argument that the scheme is insecure.
1. Please de ne and then show the correctness of the new scheme II.
2. If both Π and Π' are CPA-secure, then will the new scheme II be CPA-secure? If so, please prove it. If not, please disprove it.
3. If both Π and Π' are CCA-secure, then will the new scheme II be CCA-secure? If so, please prove it. If not, please disprove it.
4. If the inner scheme Π is CPA-secure while the outer scheme Π' is CCA-secure, then will the new scheme II be CCA-secure? If so, please prove it. If not, please disprove it.
5. If the inner scheme Π is CCA-secure while the outer scheme Π' is CPA-secure, then will the new scheme II be CCA-secure? If so, please prove it. If not, please disprove it.