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.