co-CDH ⇒ DS

Fully-black-box reduction · random oracle model · BLS01 · security loss: factor $e(q_S+1)$ in advantage for $q_S$ signing queries

Statement

BLS signatures: in a bilinear group pair $({\mathbb{G}}_1,{\mathbb{G}}_2)$ of prime order $p$ with pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$, an efficiently computable isomorphism $\psi :{\mathbb{G}}_2\to {\mathbb{G}}_1$ and hash $H:\{0,1{\}}^{\ast }\to {\mathbb{G}}_1$, $\mathsf{sk}=x\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, $\mathsf{pk}=g_2^x$ for a generator $g_2$ of ${\mathbb{G}}_2$, $\mathsf{Sign}(\mathsf{sk},m)=H(m{)}^x$, and $\mathsf{Vrfy}$ accepts $(m,\sigma )$ iff $e(\sigma ,g_2)=e(H(m),\mathsf{pk})$. With $H$ a random oracle, the scheme is EUF-CMA secure if co-CDH is hard in $({\mathbb{G}}_1,{\mathbb{G}}_2)$ — BLS01. The journal version states the theorem in the general co-GDH framework, with the asymmetric-pairing formulation of co-CDH and an explicit loss — BLS04.

Sketch

The reduction receives a co-CDH challenge $(g_2^a,h)$ with $h\in {\mathbb{G}}_1$, sets $\mathsf{pk}=g_2^a$, and answers each new $H$-query by $\psi (g_2{)}^r$ for a fresh known $r$, except with probability $1/(q_S+1)$ by $h\cdot \psi (g_2{)}^r$. It signs a point of the first kind as $\psi (g_2^a{)}^r$, and a forgery $\sigma$ on a point of the second kind yields $h^a=\sigma /\psi (g_2^a{)}^r$.

Notes

• A forger with advantage $\epsilon$ making $q_H$ hash and $q_S$ signing queries yields a co-CDH solver with advantage $\epsilon /(e(q_S+1))$, $e$ here Euler’s number, using $O(q_H+q_S)$ extra group operations — BLS04.