Comparing two pairing-based aggregate signature schemes (Q970534)

This paper describes detailed security and performance comparisons of two aggregate signature schemes. The first (BGLS), due to \textit{D. Boneh, C. Gentry, B. Lynn} and \textit{H. Shacham} [Eurocrypt 2003, Lect. Notes Comput. Sci. 2656, 416--432 (2003; Zbl 1038.94553)], uses bilinear pairings and has a reductionist security proof assuming the random oracle model. The second (LOSSW), due to \textit{S. Lu, R. Ostrovsky, A. Sahai, H. Shacham} and \textit{B. Waters} [Eurocrypt 2006, Lect. Notes Comput. Sci. 4004, 465--485 (2006; Zbl 1140.94358)], also uses bilinear pairings but does not make use of the random oracle model for its security result. The schemes are compared when realized with a particular elliptic curve offering 128 bits of security due to \textit{P. S. L. M. Barreto} and \textit{M. Naehrig} [SAC 2005, Lect. Notes Comput. Sci. 3897, 319--331 (2006; Zbl 1151.94479)], and the protocol specifications and parameter selections are based on the best-known reductionist security arguments. The authors show that both signature schemes can be described using so-called Type 3 pairings (asymmetric pairings \(e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T\) for which no efficiently-computable isomorphism between \(\mathbb{G}_1\) and \(\mathbb{G}_2\) is known) as opposed to the original setting of Type 2 pairings (an efficiently-computable isomorphism does exist). They argue that Type 3 pairings offer at least as much security in this context and that Type 2 pairings offer no performance benefits over Type 3 pairings using the the Barreto-Naehrig curves. Finally, the authors demonstrate that the BGLS scheme outperforms the LOSSW scheme with respect to size of public keys and signatures as well as signature generation and verification time.