# Construct IND-CPA secure encryption scheme by combining two given schemes

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!

• Encrypt the message using an OTP. Encrypt the (OTP-)ciphertext using $\Pi_0$ and the (OTP-)key using $\Pi_1$. – SEJPM Dec 22 '15 at 20:28

The first remark is that the cryptosystems are used with independent keys. This is important, otherwise it is usually very hard to prove anything.

### The simple solution

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

### Composition

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.

• Could you explain what's meant by "secret-share your message into two shares and encrypt each share separately"? Do I split the message into two halves and encrypt one of them using $\Pi_0$ and the other using $\Pi_1$ (with a separate key for each scheme)? And what do I do with the result? XOR? – Lemon Dec 23 '15 at 10:58
• I have added some text to the answer. Is it clear now? – K.G. Dec 23 '15 at 18:46
• So I choose $s_0$ being as long as the message and compute $s_1 = m \oplus r$. Then I encrypt $c_0 = \Pi_0(s_0), c_1 = \Pi_1(s_1)$. So the ciphertext is given by the set [c_0, c_1]? And before doing all that I need to choose two random keys, correct? I think I get the general idea (if the above is correct), but I still don't know how to formally proof that the scheme is IND-CPA secure. – Lemon Dec 24 '15 at 12:36
• So you understand how the construction works. Do you know how security proofs work in general? – K.G. Dec 24 '15 at 14:01
• In general I would do a proof by contraposition. So in this case I could try to show that if an attacker could break the whole scheme, he could also break the IND-CPA security of the secure inner scheme. Am I on the right track? – Lemon Dec 25 '15 at 16:18