Practice Problem $1$

Fix a cyclic group G of order q and generator g$.$ Let CBC$ $=\{\{0,1\}$k$,$ E$,$D$\}$ be

the randomized CBC scheme we studied. Let H : G $\{0,1\}$k be a public function.

The proposed DHCBC$=\{$K$,$ E$,$D$\}$ scheme with public key X and secret key x is as

follows:

Algorithm K

x $ $$ Zq

X $$ gx

Return $($pk$,$ sk$)$

Algorithm EX$($M$)$

y $ $$ Zq

Y $$ gy

K $$ Xy

W $$ E$$

H$($K$)($M$)$

Return $($Y$,$W$)$

Algorithm Dx$($Y$,$W$)$

K $$ Y x

M $$ D$$

H$($K$)($W$)$

return M

Show that DHCBC is IND$-$CCA insecure even if DDH is hard for G$,$ g$.$ Assume that

an adversary knows G$,$ g$,$ q$.$