Consider the following modification of the El Gamal encryption scheme over the group Z_p. The public key is
y = g^x mod p and the secret key is x where x is random in {0, . . . , p ? 1}. To encrypt a message m, one
chooses a random number r and sends c = (g^r mod p, y^r g^m mod p).
(a) Show how the receiver (who knows x) can recover g^m mod p from the ciphertext.
(b) Assuming the discrete logarithm problem is hard in Z_p, recovering g^m mod p, in general, will not allow
the recipient to recover m. Argue, however, that if we assume that the sender only sends messages in the
range {0, . . . , 100}, then the receiver can recover m.
(c) Assume (A1,B1) is an encryrption of some unknown m1. Prove that (A1,B2g^(m2) mod p) is a valid
encryption of m1 + m2 mod p. More generally, if (A2,B2) is an encryption of m2, what is (A1A2
mod p,B1B2 mod p) an encryption of?
(d) Assume the receiver R is conducting an auction in which two bidders each encrypt their bids using the
scheme above and send them to R. Assume also that both bidders can semd at most $100, so that R can
decrypt as in part b. Argue that the bidder who goes second can always bid $1 more than the first bidder,
without ever knowing the bid value of the first bidder.