# 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.

• Elliptic curves with pairings are the prime example exactly for that kind of group. I am not aware of any other groups where the DDH problem is "easy" (in the sense of "can be decided for all inputs").
– tylo
Feb 28 '17 at 16:16

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.
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$
• Hi there. Thanks for your answer. So, to confirm, in $\mathbb{Z}^{*}_p$, the CDH is (assumed to be) hard, right? And if your answer about bilinear pairings fully accurate (because for example the pairing might be hard to compute)? Many thanks. Feb 28 '17 at 16:23
• When we talk about curves with pairing, it is implicitly assumed that the pairing is efficiently computable (we can always build an inefficient pairing). Yes, CDH is conjectured to be hard in $\mathbb{Z}_p^*$. Note that this extends to some cases where $p$ is not a prime - e.g. a product of two large primes would do (you would use the Jacobi symbol instead of the Legendre symbol to distinguish, but it works the same otherwise). Feb 28 '17 at 17:18