Let f(x) be a One-Way Homomorphic Function where f(kp+1)=f(1) for any integer k and a big prime p. Given the value f(1) and the ElGamal ciphertext CT=(f(r), f(r*b)M) where pk=f(b) and sk=b. Here, r is a random number chosen by the encryptor and f(r*b) is a bit string.

Q1: Show how to quickly compute f(111) step by step. Q2b: Suppose that the output f(x) for all x has the problem that the first bit (MSB) is equal to 1 with probability 99.9999%. Show how to break the ElGamal ciphertext in the IND-CPA security model.