Exercise 8.3 (CPA Security with several messages) Consider a security definition that is exactly the same as Definition 8.3 of CPA security, except that the adversary can send two messages m1,m2m_1, m_2m1​,m2​ to the oracle. It either gets back ciphertexts c1,c2c_1, c_2c1​,c2​ that are either encryptions of m1,m2m_1, m_2m1​,m2​, in case of the real oracle (that we will call Oreal2O^2_{\text{real}}Oreal2​ to emphasize that it takes two messages as input). Or it gets back encryptions of random messages, in case of the ideal oracle Oideal2O^2_{\text{ideal}}Oideal2​. We will say the system has CPA2CPA_2CPA2​ security if no PPT (Probabilistic Polynomial Time) algorithm can distinguish the two cases with non-negligible advantage.

Show that CPA security implies CPA2CPA_2CPA2​ security.

Hint: consider an oracle OhybridO_{\text{hybrid}}Ohybrid​ that on input m1,m2m_1, m_2m1​,m2​ will return c1=Epk(m1)c_1 = E_{pk}(m_1)c1​=Epk​(m1​), c2=Epk(r)c_2 = E_{pk}(r)c2​=Epk​(r) for a random message rrr. Show that for any PPT algorithm AAA, we have AdvA(Ohybrid,Oreal2)Adv_A (O_{\text{hybrid}}, O^2_{\text{real}})AdvA​(Ohybrid​,Oreal2​) is negligible and that also AdvA(Ohybrid,Oideal2)Adv_A (O_{\text{hybrid}}, O^2_{\text{ideal}})AdvA​(Ohybrid​,Oideal2​) is negligible. For this you need to use the assumption that the cryptosystem is CPA secure. Use this to conclude that the system is CPA2CPA_2CPA2​ secure.

Note that we can define CPAlCPA_lCPAl​-security for any lll in the natural way and prove, similarly to above, that CPA security implies CPAlCPA_lCPAl​ security as long as lll is polynomial.