I have two encryption schemes $\Pi_0, \Pi_1$, at least one of them is IND-CPA secure but I don't know which one. The task is to construct a scheme $\Pi$ that is guaranteed to be CPA secure and to provide a proof for this.
Despite reading q1, q2 I still don't understand the best way to construct the scheme and how to fully prove its security.
Any ideas or hints into the right direction are appreciated!
The first remark is that the cryptosystems are used with independent keys. This is important, otherwise it is usually very hard to prove anything.
Now, the simple solution is, as is mentioned in the comment and the linked question, is to secret-share your message into two shares and encrypt each share separately. The final ciphertext consists of these two ciphertexts. (This can also be phrased in terms of a "one-time-pad" encryption, but it is better to think about it as a secret sharing, since it is then trivial to generalize to the case where you have more than two cryptosystems.)
The proof strategy is straight-forward. In order to learn anything about the message, an adversary needs (the same parts of) both shares. If at least one of the cryptosystems are IND-CPA-secure, the adversary can learn nothing about at least one of the shares. IND-CPA-security follows.
A proof based on games would probably first use real-or-random (RoR-CPA, equivalent to IND-CPA) for the secure encryption scheme to encrypt a random string instead of the secret share. Once this is done, the properties of the secret sharing guarantees that the adversary cannot learn anything about the message.
As for secret sharing, the simplest is usually the best. If your message is $m$, choose a random string $r$ of the same length. The random string is your first share. Then compute the xor of $m$ and $r$, this is the second share. (This generalizes to more shares in the obvious way by choosing more random strings.)
A more complicated thing happens if you try to compose the cryptosystems in the sense that you first encrypt the message with one system, and then encrypt the resulting ciphertext with the other system.
If you encrypt with the secure system first (the importance of being first!), everything is ok. Anything the second encryption does, an adversary could have done, so the second encryption cannot destroy the secure inner encryption.
What about if you encrypt with an insecure system first? The intuition is that the outer system (which is now secure) should hide the insecure ciphertext, which would then make the composition secure. But this is not true, and the problem with your intuition is that a cryptosystem hides the message only up to message length. What can happen is that the insecure cryptosystem produces ciphertexts whose length depends on the message. That length (which contains information about the message) can leak through the secure cryptosystem and result in an insecure construction.
However, if you restrict your attention to some sort of "length-preserving" cryptosystems, where the ciphertext length is a function of the message length only, not on the exact content of the message, then your intution should work again.
