Editing Decisional Diffie–Hellman assumption (section)

==Groups for which DDH is assumed to hold==

<!-- using {{disputed}} instead of {{disputed-section}} otherwise the talk page link is missing 
{{disputed|Incorrect claims|date=July 2013}} -->

When using a cryptographic protocol whose security depends on the DDH assumption, it is important that the protocol is implemented using groups where DDH is believed to hold:

* The subgroup <math>\mathbb{G}_q</math> of <math>k</math>-th residues modulo a prime <math>p=kq+1</math>, where <math>q</math> is also a large prime (also called a [[Schnorr group]]). For the case of <math>k=2</math>, this corresponds to the group of [[quadratic residue]]s modulo a [[safe prime]].
* The [[quotient group]] <math>\mathbb{Z}^*_p/\{1,-1\}</math> for a [[safe prime]] <math>p=2q+1</math>, which consists of the [[cosets]] <math>\{\{1,-1\},\ldots\{q,-q\}\}</math>. These cosets <math>\{x,-x\}</math> can be represented by <math>x</math>, which implies <math>\mathbb{Z}^*_p/\{1,-1\}\equiv\{1,\ldots,q\}</math>. Since <math>\mathbb{Z}^*_p/\{1,-1\}</math> and <math>\mathbb{G}_q</math> are isomorphic, and the [[isomorphism]] can be computed efficiently in both direction, DDH is equally hard in both groups.
* A prime-order [[elliptic curve]] <math>E</math> over the [[field (mathematics)|field]] <math>GF(p)</math>, where <math>p</math> is prime, provided <math>E</math> has large embedding degree.
* A [[Jacobian variety|Jacobian]] of a [[hyper-elliptic curve]] over the [[field (mathematics)|field]] <math>GF(p)</math> with a prime number of reduced divisors, where <math>p</math> is prime, provided the Jacobian has large embedding degree.

Importantly, the DDH assumption '''does not hold''' in the multiplicative group <math>\mathbb{Z}^*_p</math>, where <math>p</math> is prime. This is because if <math>g</math> is a generator of <math>\mathbb{Z}^*_p</math>, then the [[Legendre symbol]] of <math>g^a</math> reveals if <math>a</math> is even or odd. Given <math>g^a</math>, <math>g^b</math> and <math>g^{ab}</math>, one can thus efficiently compute and compare the least significant bit of <math>a</math>, <math>b</math> and <math>ab</math>, respectively, which provides a probabilistic method to distinguish <math>g^{ab}</math> from a random group element.

The DDH assumption does not hold on elliptic curves over <math>GF(p)</math> with small embedding degree (say, less than <math>\log^2(p)</math>), a class which includes [[supersingular elliptic curve]]s.  This is because the [[Weil pairing]] or [[Tate pairing]] can be used to solve the problem directly as follows: given <math>P,aP,bP,cP</math> on such a curve, one can compute <math>e(P,cP)</math> and <math>e(aP,bP)</math>.  By the bilinearity of the pairings, the two expressions are equal if and only if <math>ab=c</math> modulo the order of <math>P</math>.  If the embedding degree is large (say around the size of <math>p</math>) then the DDH assumption will still hold because the pairing cannot be computed.  Even if the embedding degree is small, there are some subgroups of the curve in which the DDH assumption is believed to hold.