co-CDH ⇒ BLS multi-signatures with public-key aggregation

Random oracle model · BDN18

Statement

Let $({\mathbb{G}}_1,{\mathbb{G}}_2)$ be a bilinear group pair of prime order $p$ with generators $g_1,g_2$, in which co-CDH without an isomorphism is hard, and let $H_0:\{0,1{\}}^{\ast }\to {\mathbb{G}}_1$ and $H_1$ be random oracles. In the BLS multi-signature of BDN18, signer $i$ holds $x_i$ with ${\mathsf{pk}}_i=g_2^{x_i}$; the aggregate key of $L=\{{\mathsf{pk}}_1,\dots ,{\mathsf{pk}}_n\}$ is $\mathsf{KeyAgg}(L)={\prod }_i{\mathsf{pk}}_i^{a_i}$ with $a_i=H_1({\mathsf{pk}}_i,L)$, the multi-signature on $m$ is $\sigma ={\prod }_i{H}_0(m{)}^{a_i{x}_i}$, and $\mathsf{Vrfy}$ accepts iff $e(\sigma ,g_2)=e(H_0(m),\mathsf{KeyAgg}(L))$. The scheme is unforgeable in the plain public-key model, with no proof of possession or knowledge of secret keys — BDN18. The plain public-key model is that of BN06.

Notes

• Efficiency: a multi-signature and an aggregate key are one group element each, and verification costs two pairings after aggregating the keys — BDN18.
• Without the coefficients $a_i$, the rogue key ${\mathsf{pk}}^{\prime }=g_2^r({\prod }_j{\mathsf{pk}}_j{)}^{-1}$ makes $H_0(m{)}^r$ a forgery, which is why Boldyreva’s scheme needs registered keys — standard.
• When $g_1=\psi (g_2)$ for an isomorphism $\psi$, co-CDH in its isomorphism form also suffices (co-CDH ⇒ co-CDH without an isomorphism) — folklore.