Problem 5.2,

You learned that the ElGamal scheme is not INDCCA secure. Consider the following attempt to make the ElGamal scheme IND-CCA secure.

Fix a cyclic group G of order q and a generator g. Let H be a public function such that for any message in the message space MkH(M) can be viewed as a group element.

A proposed HEG= (K, E, D) scheme is as follows.

Algorithm K:

x $ Zq,

X g^x,

pk X,

sk x,

Return (pk, sk)

Algorithm EX(M):

y $ Zq,

Y g^y,

K X^y,

W K (M||H(M)),

Return (Y, W)

Algorithm Dx(Y, W):

K Y^x

M' WK^-1

Parse M' as M||Z

If Z = H(M) then return M else return

Show that HEG is still IND-CCA insecure even if DDH is hard for G, g. Assume that an adversary knows G, g, q.