Diffie-Helman Assumptions

Decisional Diffie-Helman Assumption (DDH)

The Decisional Diffie-Helman (DDH) assumption in a cyclic group $G$ with generator $g$ states that, given $g^a$ and $g^b$ for $a$, $b$ chosen uniformly and independently from $\{0, . . . , |G| − 1\}$, the value $g^{ab}$ is computationally indistinguishable from a random group element. Formally, the assumption is that the following two distributions cannot be distinguished, except for negligible advantage over random guessing, by any efficient algorithm:

• $(g, g^a, g^b, g^{ab})$ where $a$ and $b$ are chosen uniformly at random from $\{0, . . . , |G| − 1\}$ and $g$ from $G$.

• $(g, g^a, g^b, g^c)$ where $a$, $b$, and $c$ are chosen uniformly at random from $\{0, . . . , |G| − 1\}$ and $g$ from $G$.

If we assume the DDH problem is infeasible to solve in $G$, we call $G$ a DDH-secure group.

Computational Diffie-Helman Assumption (CDH)

The Computational Diffie-Helman (CDH) assumption in a cyclic group $G$ with generator $g$ states that, given $g$, $g^a$, and $g^b$, no efficient algorithm can compute $g^{ab}$. If this is the case for $G$, we call $G$ a CDH-secure group.

Several variations and special cases of CDH exist. For example, the square Computational Diffie–Hellman Assumption assumes that, given $g$ and $g^x$, it is computationally hard to compute $g^{x^2}$ . The inverse Computational Diffie–Hellman Assumption assumes that, given $g$ and $g^x$, it is computationally hard to compute $g^{x^{−1}}$.

Relations

• DDH is a stronger assumption than CDH in the sense that if one can compute $g^{ab}$ given $g$, $g^a$ and $g^b$, then one can also solve the DDH problem of distinguishing $(g, g^a, g^b, g^{ab})$ from $(g, g^a, g^b, g^c)$ for random $a, b, c ∈ F_p$. Given a tuple $(g, g^a, g^b, g^c)$, one simply computes $g^{ab}$ and outputs "yes" if and only if $g^c = g^{ab}$. There are groups in which CDH is believed to hold but DDH does not.

• The DDH assumption is a stronger assumption than hardness of the Discrete Logarithm problem. If one could compute discrete logarithms efficiently in $G$, then one could break the DDH assumption in that group: given as input a triple of group elements $(g, g_1, g_2, g_3)$, one could compute the discrete logarithms $a, b, c$ of $g_1, g_2, g_3$ in base $g$, and check whether $c = a·b$, outputting "yes" if so. This algorithm would always output "yes" under draws from the first distribution above, and output "yes" with probability just $1/|G|$ under draws from the second distribution. There are groups in which the DDH assumption is false, yet the discrete logarithm problem is nonetheless believed to be hard.