subgroup of th residues modulo a prime , where is also a large prime (also called a Schnorr group). For the case of , this corresponds to the group of quadratic residues modulo a safe prime. A prime-order elliptic curve over the field , where is prime, provided has large embedding degree. A Jacobian of a hyper-elliptic curve over the field with a prime number of reduced divisors, where is prime, provided the Jacobian has large embedding degree. Importantly, the DDH assumption does not hold in the multiplicative group , where is prime. This is because if is a generator of , then the Legendre symbol of reveals if is even or odd. Given , and , one can thus efficiently compute and compare the least significant bit of , and , respectively, which provides a probabilistic method to distinguish from a random group element. The DDH assumption does not hold on elliptic curves over with small embedding degree (say, less than ), a class which includes supersingular elliptic curves. This is because the Weil pairing or Tate pairing can be used to solve the problem directly as follows: given on such a curve, one can compute and . By the bilinearity of the pairings, the two expressions are equal if and only if modulo the order of . If the embedding degree is large (say around the size of ) 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. See also Diffie–Hellman problem Diffie–Hellman key exchange Computational hardness assumptions XDH assumption Decisional Linear assumption References Computational hardness assumptions Elliptic curve cryptography