co-CDH ⇒ Aggregate signatures (BGLS)

Fully-black-box reduction · random oracle model · BGLS03

Statement

Let $({\mathbb{G}}_1,{\mathbb{G}}_2)$ be a bilinear group pair of prime order $p$, with 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$, in which co-CDH is hard, and let $H:\{0,1{\}}^{\ast }\to {\mathbb{G}}_1$ be a random oracle. In the BGLS aggregate signature scheme, user $i$ holds $x_i$ with ${\mathsf{pk}}_i=g_2^{x_i}$ and signs as ${\sigma }_i=H(m_i{)}^{x_i}$, as in BLS; $\mathsf{Agg}$ outputs $\sigma ={\prod }_i{\sigma }_i$, and $\mathsf{AggVrfy}(({\mathsf{pk}}_i,m_i{)}_{i\le n},\sigma )$ accepts iff the $m_i$ are pairwise distinct and $e(\sigma ,g_2)={\prod }_{i=1}^{n}e(H(m_i),{\mathsf{pk}}_i)$. The scheme is unforgeable in the aggregate chosen-key model — BGLS03. BGLS03 state the theorem for co-gap Diffie–Hellman group pairs; the pairing decides co-DDH, so in a bilinear group pair this is hardness of co-CDH.

Sketch

The reduction answers each $H$-query with $\psi (g_2{)}^r$ for a known $r$ or, with small probability, with $h\cdot \psi (g_2{)}^r$, embedding the co-CDH challenge $h$, and signs a point of the first kind under ${\mathsf{pk}}^{\ast }$ as $\psi ({\mathsf{pk}}^{\ast }{)}^r$. In a forgery whose other messages all hash to points of the first kind, user $i$‘s contribution $H(m_i{)}^{x_i}$ equals $\psi ({\mathsf{pk}}_i{)}^{r_i}$, which the reduction computes without $x_i$. Dividing these out leaves the challenge user’s signature $(h\psi (g_2{)}^r{)}^{x^{\ast }}$ on the embedded point, which yields $h^{x^{\ast }}$.

Notes

• Without the distinctness check, the rogue key ${\mathsf{pk}}^{\prime }=g_2^r\cdot ({\mathsf{pk}}^{\ast }{)}^{-1}$ makes $H(m{)}^r$ a valid aggregate on $(m,m)$ under $({\mathsf{pk}}^{\ast },{\mathsf{pk}}^{\prime })$, since $e(H(m),{\mathsf{pk}}^{\ast })e(H(m),{\mathsf{pk}}^{\prime })=e(H(m{)}^r,g_2)$ — standard.
• The basic scheme is secure only for aggregates of distinct messages, and the enhanced scheme that prepends each signer’s public key to its message only for per-signer distinct messages. A new analysis lifts the restriction and gives an unrestricted aggregate signature scheme in the random oracle model; a second analysis removes the distinct-signer restriction of the sequential aggregate signatures of Lysyanskaya, Micali, Reyzin and Shacham, and variants with tight reductions are also given — BNN07.
• Efficiency: an aggregate is one element of ${\mathbb{G}}_1$ whatever $n$, and verification costs $n+1$ pairings — BGLS03.