In section 11.4.4 of Introduction to Modern Cryptography (Lindell and Katz, 2nd edition) it is shown that El Gamal encryption is malleable, and specifically that given a ciphertext c1 , c2 that is the encryption of some unknown message m , it is possible to produce a ciphertext c1 , c2 that is the encryption of ? m (for known ? ). A receiver who receives both these ciphertexts might be suspicious since both ciphertexts share the ?rst component. Show that it is possible to generate c1 , c2 that is the encryption of ?m , with c1 = c1 and c2 = c2 .