# Decisional Diffie–Hellman assumption

The decisional Diffie–Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most notably the ElGamal and Cramer–Shoup cryptosystems.

## Definition

This intuitive notion is formally stated by saying that the following two probability distributions are computationally indistinguishable (in the security parameter, $n=\log(q)$ ):

Triples of the first kind are often called DDH triples or DDH tuples.

## Relation to other assumptions

DDH is considered a stronger assumption than discrete log, because there are groups for which detecting DDH tuples is easy, but computing discrete logs is believed to be hard. Thus, requiring that the DDH assumption holds in a group is a more restricting requirement.

The DDH assumption is also related to the computational Diffie–Hellman assumption (CDH). If it were possible to efficiently compute $g^{ab}$ from $(g^{a},g^{b})$ , then one could easily distinguish the two probability distributions above. Similar to above, DDH is considered 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

{{ safesubst:#invoke:Unsubst||$N=Disputed |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }}

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 DDH assumption does not hold on elliptic curves over $GF(p)$ with small embedding degree (say, less than $\log ^{2}(p)$ ), 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 $P,aP,bP,cP$ on such a curve, one can compute $e(P,cP)$ and $e(aP,bP)$ . By the bilinearity of the pairings, the two expressions are equal if and only if $ab=c$ modulo the order of $P$ . If the embedding degree is large (say around the size of $p$ ) 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.