Consider the following decision problem DP. Let G be a cyclic group of prime order m and let g, q be generators of G. Consider the experiments associated with an adversary A: Experiment ExpDP-1 G,g,q(A) x $ Zm X gx ; Y qx d A(g, q,X, Y ) Return d Experiment ExpDP-0 G,g,q(A) x $ Zm ; y $ Zm X gx ; Y qy d A(g, q,X, Y ) Return d The DP-advantage of A is defined in the usual way, as: AdvDP G,g,q (A) = Pr h ExpDP-1 G,g,q(A) = 1 i Pr h ExpDP-0 G,g,q(A) = 1 i The DP problem is said to be hard in G if the DP-advantage of any adversary with reasonable resources is small. Show that DP is equivalent to DDH. In other words, explain why in any group, DP is as hard as DDH and vice-versa, in the same group of prime order. You don't have to do the formal reduction proofs (though you are welcome to); try to think of a simpler justification.