Let 1 = (Kgen1 , Enc1, Dec1), 2 = (Kgen2 , Enc2, Dec2), and 3 = (Kgen3 , Enc3, Dec3) be three secret-key encryption schemes, with key space {0, 1} k , message space {0, 1} n , and ciphertext space {0, 1} m. We know that one of them is semantically secure. But we dont know which one. Nevertheless, show that we can combine the three schemes to construct a secret key encryption scheme = (Kgen, Enc, Dec) that is definitely semantically secure. You do not need to give a full proof of your scheme, but you need to justify why you think it is semantically secure.

Hint: Instead of trying to directly encrypt a message m, think about how to generate three messages m1, m2 and m3, such that, given all of them, m can be reconstructed, but any two of them reveals no information about m.