Paper 2010/493

A Suite of Identity Based Aggregate Signatures and a Multi-Signature Scheme from RSA

S. Sharmila Deva Selvi, S. Sree Vivek, and C. Pandu Rangan

Abstract

Fully aggregateable identity based signature schemes without prior communication between the signing parties is an interesting issue in identity based cryptography. On this front, we identify that deterministic identity based signature schemes lead to full aggregation of signatures without the aforementioned overhead. Inspired by Shamir's identity based signature scheme, we propose a deterministic identity based signature scheme which is also based on RSA. Based on this newly proposed deterministic identity based signature scheme, we design a suite of four identity based aggregate signature schemes with different properties. The first two schemes are deterministic identity based aggregation signature schemes, supporting full aggregation for general and ordered sequential aggregation respectively. The third and fourth schemes are non-deterministic aggregate signature schemes, supporting full aggregation for general and ordered sequential aggregation respectively. We formally prove the schemes to be existentially unforgeable in the random oracle model. We also propose an efficient identity based multi-signature scheme which achieves aggregation in one round.

Note: In the previous version of this report, we had attached an appendix where we gave arguement for a possible weakness in the proof of Lu et al.'s PKI based aggregate signature scheme. However, Sanjit Chatterjee pointed out the flaw in our arguement. Hence, we remove the appendix and modified the text throughout by deleting remarks related to Lu et al.'s paper. Once again we thank Sanjith Chatterjee for his careful reading and insightful remark.