Computational Diffie-Hellman

The Computational Diffie-Hellman (CDH) is a central assumption in cryptography. It is a natural strengthening of the DDH assumption. In other words, an adversary which can solve the CDH problem can also solve DDH in the same group.

Assumption

Informally, the CDH 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{cdh}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG,g,p) \gets \GrGen(1^\secpar)$
\State $x \getsr [p]$ ; $y \getsr [p]$
\State $X \gets g^x$ ; $Y \gets g^y$
\State $\hat{Z} \gets \calA(1^\secpar, \GG, g, p X, Y)$
\Return $[\hat{Z} = g^{xy}]$
\end{algorithmic}
\end{algorithm}

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

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{cdh}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{MAC},\mathcal{A}}^{\text{cdh}}(\lambda )=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{cdh}}(\lambda )\le O(\frac{q^2}{p})$, where $q$ is the number of queries that $\mathcal{A}$ issues — Shoup97

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