, where and are randomly and independently chosen from.
, where are randomly and independently chosen from.
Triples of the first kind are often called DDH triplet or DDH tuples.
Relation to other assumptions
The DDH assumption is related to the discrete log assumption. If it were possible to efficiently compute discrete logs in, then the DDH assumption would not hold in. Given, one could efficiently decide whether by first taking the discrete of, and then comparing with. DDH is considered to be a stronger assumption than the discrete logarithm assumption, because there are groups for which computing discrete logs is believed to be hard, but detecting DDH tuples is easy. Because of this, requiring that the DDH assumption holds in a group is believed to be a more restrictive requirement than DL. The DDH assumption is also related to the computational Diffie–Hellman assumption. If it were possible to efficiently compute from, then one could easily distinguish the two probability distributions above. Similar to the above, DDH is considered to be a stronger assumption than CDH.
Other properties
The problem of detecting DDH tuples is random self-reducible, meaning, roughly, that if it is hard for even a small fraction of inputs, it is hard for almost all inputs; if it is easy for even a small fraction of inputs, it is easy for almost all inputs.
Groups for which DDH is assumed to hold
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 of th residues modulo a prime, where is also a large prime. 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.
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 onelliptic curves over with small embedding degree, 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 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.
