Groups for which DDH is easy but CDH is hard For prime p, is $\mathbb{Z}^{*}_{p}$ a group for which the Decision Diffie-Hellman problem is easy (because one can compute the Legendre symbol of ($g^{ab}$) while CDH is thought to be hard? Of course, computing the Legendre symbol won't always help differentiate right? But it'll work enough times to beat the DDH assumptions ("non-negligible probability"?)

Are there any more examples? For example with bilinear pairings on elliptic curves?

Many thanks.
Of course, computing the Legendre symbol won't always help differentiate right? But it'll work enough times to beat the DDH assumptions ("non-negligible probability"?)


Yes, if $g$ is an element with Legendre symbol -1, then a simple test of the symbols of $g^a, g^b, g^c$ will show that $ab \ne c$ half the time for random $a, b, c$.  That is certainly non-negligible, and is sufficient to invalidate any proof of a cryptosystem that assumes that DDH is hard.  However, depending on why you want the DDH problem to be easy, it might not be non-negligible enough.


  Are there any more examples?


If you need a group with a more reliable test, we can consider a group with a nontrivial bilinear pairing, in particular, one where $G$ and $e(G, G)$ have the same order.  In that case, we have a test that always gives the correct answer to DDH; $e( aG, bG ) = e( G, cG )$ will hold if and only if $ab = c$