Practical forward secure group signature schemes

Abstract

A group signature scheme allows a group member to sign messages anonymously on behalf of the group, while in case of a dispute, a designated entity can reveal the identity of a signature's originator. Group signature schemes can be used as a basic building block for many security applications such as electronic banking systems and electronic voting. Two important issues -- forward security and efficient revocation -- have not been addressed by prior schemes. We construct the first forward-secure group signature schemes. While satisfying all the security properties proposed in previous group signature schemes, our schemes provide a new desired security property, forward-security: while the group public key stays fixed, a group signing key of a group member evolves over time such that compromise of a group signing key of the current time period does not enable an attacker to forge group signatures pertaining to the past time periods. Such forward-security is important to mitigate the damage caused by key exposure and particularly desirable for group signature schemes because the risk of signing key exposure escalates as the size of the group increases. Our schemes are provably secure in the random oracle model and under the strong RSA and decisional Diffie Hellman assumptions.Furthermore, we extend our forward-secure group signature scheme to provide a solution for the problem of group member exclusion without the need to re-key all other group members. When a group member is excluded, he should not be able to generate valid signatures any more and yet his previous signatures remain anonymous. We provide the first solutions which support both retroactive public revocation and backward unlinkability and the signature size is independent of the number of revoked members.