# CPA-secure of $\Pi$ implies CPA-security of $\Pi||\Pi||\ldots||\Pi$

Katz and Lindell book claim that from the theorem:

1. Any private-key encryption scheme that is CPA-secure is also CPA-secure for multiple encryptions.

Follows the fact that:

1. If $$(Gen,Enc,Dec)$$ is a fixed-length ($$M_n = \{0,1\}^n$$) CPA-secure ES then $$(Gen,Enc',Dec')$$ with $$M_n' = (\{0,1\}^n)^{*}$$ and $$Enc_k'(m) = Enc_k(m^{(1)})||\ldots||Enc_k(m^{(s)})$$ is also CPA-secure.

Why is it the case?

What strikes me more is that a similar theorem to 1. holds for CCA-security:

1. Any private-key encryption scheme that is CCA-secure is also CCA-secure for multiple encryptions.

However, the construction does not hold (according to my slides) in the later case:

1. Assuming $$(Gen,Enc,Dec)$$ is CCA-secure with $$M_n = \{0,1\}^n$$ then one can show that $$(Gen,Enc',Dec')$$ is not CCA-secure.
• Doesn't CCA fail with multiple encryptions? – kelalaka Nov 18 '18 at 22:38
• @kelalaka from what I understand you mean that you know how to proof statement 4. i've tried some malleability argument but it didn't work out – Rodrigo Nov 18 '18 at 22:47
• See proposition 3.20 in the second ed. – kelalaka Nov 18 '18 at 22:57
• @kelalaka the problem I see is that in that proposition the are assumming that encryption is deterministic (the example taken is the one-time-pad). However, here the encryption does not need to be deterministic – Rodrigo Nov 18 '18 at 23:06
• Note: Heavy theory is not really the emphasis of Katz-Lindell. If you want to go there, get Goldreich (draft version are available for free on his homepage). – fkraiem Nov 19 '18 at 3:54

The proof of (1) is not given in the chapter on symmetric encryption since it requires knowing the hybrid proof technique that is taught in Chapter 7. However, the argument is proven in Chapter 11 for the asymmetric case (see Theorem 11.6 and the proof on page 383). Essentially the same proof holds for the symmetric case as well (except that instead of the reduction $$\mathcal{A}'$$ on page 385 computing the plaintexts itself for $$j and $$j>i$$ in steps 2(a) and 2(c) respectively, it asks its encryption oracle to do it and uses the responses).