8
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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"). $\endgroup$
    – tylo
    Feb 28, 2017 at 16:16

1 Answer 1

Reset to default
7
$\begingroup$

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$

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user32609
    Feb 28, 2017 at 16:23
  • $\begingroup$ 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). $\endgroup$
    – Geoffroy Couteau
    Feb 28, 2017 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.