Reference no: EM13162720

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.