A Multisignature Scheme for Implementing Safe Delivery Rule in Group Communication Systems

The safe delivery rule guarantees that any message delivered to the application by the group communication system has been received and acknowledged by all group members. In this paper, we present a new multisignature scheme which can be used in client-server model of group communication systems to deal with certain problems that arise while implementing safe delivery rule in such systems. If security is incorporated into safe delivery rule by encrypting the acknowledgement messages from each group member using group-key (to ensure message integrity) or by requiring each member to digitally sign these messages (to prevent malicious members from disrupting the system), the sender of a message which receives these messages would have to decrypt or verify all these messages. The proposed multisignature scheme enables the group communication server to combine acknowledgements of a message from all group members into a single group-acknowledgement message of constant size and send it to the sender of the message. This single acknowledgement can be verified by any member in constant time and thereby avoids the problem of having to perform $n-1^1$ cryptographic operations