# Building a combined encryption scheme from two encryption schemes that's secure if at least on of them is secure

Any thoughts on how this can be done?

Let $$\Pi_1 = (\mathrm{Gen}_1, \mathrm{Enc}_1, \mathrm{Dec}_1)$$ and $$\Pi_2 = (\mathrm{Gen}_2, \mathrm{Enc}_2, \mathrm{Dec}_2)$$ be two encryption schemes for which it is known that at least one is CPA-secure. The problem is that you don't know which one is CPA-secure and which one may not be. Show how to construct an encryption scheme $$\Pi$$ that is guaranteed to be CPA-secure as long as at least one of $$\Pi_1$$ or $$\Pi_2$$ is CPA-secure.

Problem 3.21 - Jonathan Katz, Yehuda Lindell - Introduction to Modern Cryptography: Principles and Protocols.

You can generate a random string $s_1$ as long as the plaintext. Then XOR this value with the plaintext generating $s_2$. Now encrypt both parts using $\mathrm{Enc}_1$ and $\mathrm{Enc}_2$. You need to decrypt both to XOR the two parts together again. This is similar to secret sharing where you need two parts of a key to decrypt.
If $\mathrm{Gen}_1$ and $\mathrm{Gen}_2$ are two random generators then you may want to XOR those together as well when generating $s_1$. I presume however that they are used to generate the secret keys.
• @fgrieu : $\:$ The inner scheme could be such that the lengths of its ciphertexts noticeably depend on their corresponding plaintexts, and the outer scheme could be CPA-secure but still such that its ciphertexts reveal enough about the lengths of their corresponding plaintexts. $\;\;\;\;$ – user991 May 19 '15 at 23:22
• @MaartenBodewes : $\:$ You're missing the point: In the case I described, the cascade $\hspace{1.13 in}$ would not be CPA-secure, even though one of the schemes would be CPA-secure. $\hspace{1.39 in}$ – user991 May 20 '15 at 1:07