Unrestricted aggregate signatures
Mihir Bellare, Chanathip Namprempre
and Gregory Neven. In L. Arge, C. Cachin, and A. Tarlecki, editors, 34th International Colloquium on Automata, Languages and Programming - ICALP 2007, volume 4596 of Lecture Notes in Computer Science,
pages 411-422. Springer-Verlag, 2007. Also available from Cryptology ePrint Archive, Report 2006/285.
Abstract: Secure use of the BGLS aggregate signature schemes is restricted to the aggregation of distinct messages (for the basic scheme) or per-signer distinct messages (for the enhanced, prepend-public-key version of the scheme). We argue that these restrictions preclude interesting applications, make usage of the schemes error-prone and are generally undesirable in practice. Via a new analysis and proof, we show how the restrictions can be lifted, yielding the first truly unrestricted aggregate signature scheme. Via another new analysis and proof, we show that the distinct signer restriction on the LMRS sequential aggregate signature schemes can also be dropped, yielding an unrestricted sequential aggregate signature scheme. Finally, we present variants of these schemes with tight security reductions.