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

is negligible.

Known Results

• DDH ⇒ CDH
• No free reduction from GGM to CDH
• 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 — 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 ⇒ BDH
• CDH ⇒ DDH
• CDH ⇒ DLOG

Produces Computational Diffie-Hellman

• DDH ⇒ CDH
• DLOG ⇒ CDH

Barriers

• No free reduction from GGM to 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 .$ ↩