7
$\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.

$\endgroup$
  • 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 '17 at 16:16
6
$\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$

$\endgroup$
  • $\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 '17 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 '17 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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