Decisional Diffie-Hellman

The Decisional Diffie-Hellman (DDH) assumption is a central assumption in cryptography, and one of the first used to construct key exchange DH76. It is implied by the CDH assumption. In other words, an adversary which can solve the CDH problem can also solve DDH in the same group.

Assumption

Informally, the DDH assumption concerns a cyclic group generation algorithm $\mathsf{GrGen},$ which takes as input a security parameter $1^{\lambda }$ and outputs a succinct¹ description of a cyclic group $(\mathbb{G},g,p),$ where $\mathbb{G}$ is the group set, $g$ is a generator for the group, and $p$ is the order of the group.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{ddh}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG,g,p) \gets \GrGen(1^\secpar)$
\State $x \getsr [p]$ ; $y \getsr [p]$ ; $z \getsr [p]$
\State $X \gets g^x$ ; $Y \gets g^y$
\State $b \getsr \bits$
\State $Z_0 \gets g^{xy}$ ; $Z_1 \gets g^{z}$
\State $\hat{b} \gets \calA(1^\secpar, \GG, g, p, X, Y, Z_b)$
\Return $[\hat{b} = b]$
\end{algorithmic}
\end{algorithm}

We say that DDH is hard for a group generation algorithm $\mathsf{GrGen}$ if for all efficient $\mathcal{A},$

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{ddh}}(\lambda ):=\left|2\cdot \mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A}}^{\text{ddh}}(\lambda )=1\right]-1\right|$$

is negligible.

Known Results

• It is easy to see that if $\mathcal{A}$ can compute $g^{xy}$, then $\mathcal{A}$ can easily distinguish between $g^{xy}$ and a random group element. This establishes that CDH is not easier than DDH.
• In the Generic Group Model, ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{ddh}}(\lambda )\le O(\frac{q^2}{p})$, where $q$ is the number of queries that $\mathcal{A}$ issues — Shoup97
• DDH implies PKE via the ElGamal encryption scheme: encrypt $m$ under public key $y=g^x$ as $(g^r,m\cdot y^r)$; decryption uses $x$ to compute $y^r$ and recover $m$ — ElGamal85
• DDH implies PRFs via the Naor-Reingold construction, which maps inputs in $\{0,1{\}}^n$ to group elements using a secret exponent vector — NR97
• DDH is easy in groups that admit efficient bilinear pairings (e.g., certain supersingular elliptic curves): given $(g^x,g^y,g^z)$, check whether $e(g^x,g^y)=e(g,g^z)$

Attacks

• Baby-step giant-step: a generic algorithm for the underlying discrete logarithm problem. Given $X=g^x$, it finds $x$ in $O(\sqrt{p})$ time and $O(\sqrt{p})$ space by writing $x=im+j$ (where $m=\lceil \sqrt{p}\rceil$) and matching $g^{im}=X\cdot g^{-j}$ across a hash table. Since DDH reduces to DLOG, this attack applies: any DDH distinguisher that computes $g^{xy}$ by solving DLOG runs in $O(\sqrt{p})$.
• DDH is easy in groups with efficient pairings: in groups $\mathbb{G}$ that admit an efficient bilinear pairing $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$ (symmetric/Type-1 pairings, e.g., certain supersingular elliptic curves), DDH is trivially broken. Given $(g^x,g^y,g^z)$, check whether $e(g^x,g^y)=e(g,g^z)$; this holds iff $z=xy$. DDH is therefore not a reasonable assumption in Type-1 pairing groups — see bilinear map assumptions.
• Pohlig-Hellman: if the group order $p$ is smooth (factors into small primes), discrete log (and hence DDH) is easy via the Chinese Remainder Theorem on the prime-order subgroups. This is why DDH is only assumed in prime-order groups or carefully chosen subgroups.

Variations

In the above definition, we implicitly allow $\mathsf{GrGen}$ to choose a random generator $g$ for the group $\mathbb{G}$. However, BMZ19 has explored technical differences between this model and one where $g$ is selected deterministically.

Footnotes

1. Succinct means that the tuple $(\mathbb{G},g,p)$ is at most $\mathrm{poly}(\lambda )$-bits, but $|\mathbb{G}|=p$ may be super-polynomial in $\lambda .$ ↩