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

Attacks

• TODO — baby step, giant step
• TODO — DDH is easy in certain groups (e.g., groups of non-prime order)

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 .$ ↩