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.