Type 1 pairing + CDH ⇒ Multi-signatures in the KOSK model (Boldyreva)

Random oracle model · Bol03

Statement

Let $\mathbb{G}$ be a group of prime order $p$ with a symmetric pairing $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$, so that the pairing decides DDH in $\mathbb{G}$, in which CDH is hard, and let $H:\{0,1{\}}^{\ast }\to \mathbb{G}$ be a random oracle. In Boldyreva’s multisignature, signer $i$ holds $x_i$ with ${\mathsf{pk}}_i=g^{x_i}$; the aggregate key of a set of signers is ${\prod }_i{\mathsf{pk}}_i$, their multisignature on $m$ is $\sigma ={\prod }_{i}H(m{)}^{x_i}$, and $\mathsf{Vrfy}$ accepts iff $e(\sigma ,g)=e(H(m),{\prod }_i{\mathsf{pk}}_i)$. The scheme is unforgeable in the knowledge-of-secret-key model, in which every adversarial public key is registered together with its secret key — Bol03. Bol03 prove this in every gap Diffie–Hellman group, and a symmetric pairing group in which CDH is hard is one.

Notes

• In the plain public-key model the rogue key ${\mathsf{pk}}^{\prime }=g^r({\prod }_j{\mathsf{pk}}_j{)}^{-1}$ gives the set $\{{\mathsf{pk}}_1,\dots ,{\mathsf{pk}}_k,{\mathsf{pk}}^{\prime }\}$ the aggregate key $g^r$, so $H(m{)}^r$ is a forgery; registration with the secret key rules this out — standard.
• Registering each key with a proof of possession instead of its secret key also suffices (Type 1 pairing + CDH ⇒ Multi-signatures with proofs of possession) — RY07. Hashing the keys into the aggregate removes the need for registration altogether (co-CDH ⇒ BLS multi-signatures with public-key aggregation) — BDN18.
• Efficiency: a multisignature is one group element whatever the number of signers, and verification costs two pairings after multiplying the public keys — Bol03.