# 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.

• While this certainly is valid, and matches the hint given in the question before it vanished, I do not see anything wrong with cascaded encryption (using independent keys), which does not depend on a random generator, and has shorter ciphertext.
– fgrieu
May 19, 2015 at 6:52
• Ok all seems well now. @fgrieu I would happily upvote another answer. This one is indeed more complex than strictly necessary. May 19, 2015 at 9:38
• @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, 2015 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, 2015 at 1:07
• @Ricky Demer: indeed if the first and non-CPA-secure encryption scheme causes an expansion of 1000 bytes for plaintext that starts with the string "fubar", cascaded encryption is insecure, but the answer gives a CPA-secure scheme. Good catch; I will remember considering leaks by size in questions on cascaded encryption.
– fgrieu
May 20, 2015 at 5:30