Decision Diffie-Hellman (DDH)

The Decision Diffie-Hellman (DDH) assumption is a common assumption made to construct a wide variety of primitives. It is the weakest of assumption of the common Diffie-Hellman type assumptions. And being able to break Computational Diffie-Hellman (CDH) and Discrete Logarithm (DLOG) immediately break DDH.

Formal assumption

Let $\mathbb {G} =\{\mathbb {G} _{\lambda }\}$ be a group ensemble. Then, we say that the Decision Diffie-Hellman (DDH) assumption holds for $\mathbb {G}$ if for any efficient algorithm $A$, there is a negligible function $\nu$ such that,

$|\Pr[A(g,g^{x},g^{y},g^{xy})]-\Pr[A(g,g^{x},g^{y},g^{z})]|\leq \nu (\lambda ),$

where $g$ is a random generator of the group $\mathbb {G} _{\lambda }$, $x,y,z$ are all uniform on $|\mathbb {G} _{\lambda }|$.

The problem of distinguishing between these two inputs is sometimes also referred to as the Decision Diffie-Hellman problem.

Known attacks

• A quantum computer can compute discrete logarithms (and therefore break DDH) in any group [Sho94]
• The | Baby-Step-Giant-Step algorithm computes discrete logarithms in any group in $O({\sqrt {n}})$ time and space for groups of order $n$. (Which is known to be optimal for generic groups [Sho97])

Relationship to other assumptions

• If DDH is hard in a group, then CDH is also hard in that group.

Implied primitives

• Key Agreement (KA) due to the original work [DH76]

Other notes

Some works define the DDH problem for a fixed generator rather than a random generator. The differences between these two definitions are discussed in [BMZ19].