Question

Let Π1 = (Enc1, Dec1) and Π2 = (Enc2, Dec2) be two encryption schemes for which it is known that at least one is CPA-secure (but you don’t know which one). Show how to construct an encryption scheme Π that is guaranteed to be CPA-secure as long as at least one of Π1 or Π2 is CPA-secure.

********PROVIDE A FULL PROOF OF YOUR SOLUTION********

Hint: Generate two plaintext messages from the original plaintext so that knowledge of either one reveals nothing about the original plaintext, but knowledge of both enables the original plaintext to be computed.

Introduction to Modern Cryptography

Answer 1

Let us take the plain text.

Now we can consider a random string say x which is equal to the size of the plain text. We can xor both the random string and the plain text to get another string y.

Now we can encrypt both the generated strings x and y using the two encryption algorithm provided in the problem.

This final encrypted text will be CPA secure now as to decrypt the given plain text you need to decrypt both x and y to get the original plain text using the xor operation. Since one of them is CPA secure the above encryption scheme will be CPA secure.