Problem $6\mathrm{.}2$

You learned that the ElGamal scheme is not IND$-$CCA secure$,$ so consider the following variant of

the scheme.

Let $p$ and $q$ be large primes such that $q$ divides $p-1.$ Let $G$ be the order $q$ subgroup generated by

ginG. Assume that the DDH assumption holds in $G.$ Consider the following scheme $E{G}^{\text{'}}=(K,E,D)$

defined with Message space $Z_p^{**}$ and ciphertext space $(G{Z}_p^{**})$ :

Algorithm $E_K(M),$

Algorithm $K,ylar{r}^{\text{\$}}{Z}_q$ Algorithm $D_K(Y,W)$

$xlar{r}^{\text{\&}}{Z}_q,Ylarr{g}^y,Klarr{Y}^x$

$xlarr{g}^x,Klarr{x}^y,$MlarrW$*K^{-1}$

Return $(x,x),$WlarrK$*M$ return $M$

Return $(Y,W),$

Show that $E{G}^{\text{'}}$ is still not secure under IND$-$CCA even if DDH is hard for $G,g.($Remember that

adversaries know the public parameters $G,g,q.)$