(Exercise 2.13 from Introduction to Modern Cryptography, 2nd Edition by Katz & Lindell)

In this problem we consider definitions of perfect secrecy for the encryption of two messages (using the same key). Here we consider distributions over pairs of messages from the message space M; we let M1, M2 be random variables denoting the first and second message, respectively. We generate a (single) key k, sample messages (m1, m2) according to the given distribution, and then compute ciphertexts ci - Enck (mi) and c2 + Enck (m2); this induces a distribution over pairs of ciphertexts and we let C1, C2 be the corresponding random variables. (a) Say encryption scheme (Gen, Enc, Dec) is perfectly secret for two messages if for all distributions over M M, all mi, m2 E M, and all ciphertexts C1, C2 E C with Pr[C1 = C1 A C2 = c2] > 0: Pr[M1 = m1 A M2 = m2|C1 = C1 A C2 = c2) = Pr[M1 = m1 A M2 = m2). Prove that no encryption scheme can satisfy this definition. Hint: Take mit m2 but c1 = C2