co-CDH ⇒ BLS signatures

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.
• BLS signatures are unique: for each $\mathsf{pk}\in {\mathbb{G}}_2$ and $m$, exactly one $\sigma \in {\mathbb{G}}_1$ verifies, namely $H(m{)}^x$, so EUF-CMA security implies SUF-CMA security — standard.
• Meta-reductions show that reductions of restricted kinds from non-interactive assumptions lose a factor of about $q_S$: Coron proved this for unique signatures — Cor02, and it was extended to efficiently re-randomizable signatures — HJK12, BJLS16. The loss $e(q_S+1)$ above is of that order. These bounds rule out only restricted reductions: for a chain-based unique signature scheme, whose signature is $n$ BLS signatures computed in sequence, a reduction from CDH in the random oracle model loses at most $n\cdot q_H^{1/n}$ for $q_H$ hash queries, with $n$ any integer independent of the security parameter — GCS+17.