co-Computational Diffie-Hellman

The CDH problem across the two source groups of a bilinear group pair with an efficiently computable isomorphism $\psi :{\mathbb{G}}_2\to {\mathbb{G}}_1$: given $g_2,g_2^a\in {\mathbb{G}}_2$ and $h\in {\mathbb{G}}_1$, compute $h^a$. It is the assumption under which BLS signatures are EUF-CMA secure in the random oracle model (co-CDH ⇒ BLS signatures) — BLS04.

Assumption

The assumption concerns a generator $\mathsf{GrGen}$ that on input $1^{\lambda }$ outputs $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T,p,e,g_2,\psi )$: cyclic groups ${\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T$ of prime order $p$, a generator $g_2$ of ${\mathbb{G}}_2$, a non-degenerate bilinear pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$, and an efficiently computable isomorphism $\psi :{\mathbb{G}}_2\to {\mathbb{G}}_1$, so that the pairing is of Type 1 or Type 2 — BLS04.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{co-cdh}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG_1, \GG_2, \GG_T, p, e, g_2, \psi) \gets \GrGen(1^\secpar)$
\State $a \getsr \ZZ_p$; $h \getsr \GG_1$
\State $y \gets \calA(1^\secpar, \GG_1, \GG_2, \GG_T, p, e, g_2, \psi, g_2^a, h)$
\Return $[y = h^a]$
\end{algorithmic}
\end{algorithm}

co-CDH is hard for $\mathsf{GrGen}$ if for all efficient $\mathcal{A}$,

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

is negligible.

The pairing decides co-DDH, whether $(g_2,g_2^a,h,h^b)$ has $a=b$, by testing $e(h,g_2^a)=e(h^b,g_2)$; a pair in which co-CDH is hard is therefore a co-gap Diffie–Hellman group pair — BLS04.

Variations

Without an isomorphism

For a generator $\mathsf{GrGen}$ that outputs $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T,p,e,g_1,g_2)$, with generators $g_1,g_2$ of the source groups and no isomorphism, so that the pairing may be of Type 3: given $g_1^{\alpha },g_1^{\beta }\in {\mathbb{G}}_1$ and $g_2^{\beta }\in {\mathbb{G}}_2$ for $\alpha ,\beta \stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, compute $g_1^{\alpha \beta }$ — BDN18. This form of co-CDH is hard for $\mathsf{GrGen}$ if every efficient adversary computes $g_1^{\alpha \beta }$ with negligible probability.

Participates in

Builds on co-Computational Diffie-Hellman

• co-CDH ⇒ BLS multi-signatures with public-key aggregation (via Without an isomorphism)
• co-CDH ⇒ Aggregate signatures (BGLS)
• co-CDH ⇒ co-CDH without an isomorphism
• co-CDH ⇒ BLS signatures

Produces co-Computational Diffie-Hellman

• co-CDH ⇒ co-CDH without an isomorphism (via Without an isomorphism)