Computational Diffie-Hellman

The Computational Diffie-Hellman (CDH) is a central assumption in cryptography. It is implied by the DDH assumption: an adversary which can solve the CDH problem can also solve DDH in the same group — folklore.

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{GrGen},\mathcal{A}}^{\text{cdh}}(\lambda )=1\right]$$

is negligible.

Known Results

• DDH ⇒ CDH
• GGM ⇒ CDH
• In the Generic Group Model, for groups of prime order $p$, ${\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 — Sho97

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.

Participates in

Builds on Computational Diffie-Hellman

• CDH ⇒ DLOG

Produces Computational Diffie-Hellman

• BDH ⇒ CDH
• DDH ⇒ CDH
• DLOG ⇒ CDH
• GGM ⇒ CDH

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