Forward-Secure Multi-signatures

Abstract

In many applications a document needs to be signed by more than one signer. When a signature depends on more than one signer we call it a multi-signature. Further, ordinary digital signatures have an inherent weakness: if the secret key is leaked, then all signatures, even the ones generated before the leak, are no longer trustworthy. Forward-secure digital signatures were proposed to address this weakness, they ensure that the past signatures remain secure even if the current secret key is leaked. We propose to apply the concept of Forward-Security to multi-signatures. The basic signature scheme that we have considered is ElGamal Signature scheme which is based on discrete log problem. We initially make this signature scheme forward-secure and then apply it to multi-signatures. By this all signers of the document can guarantee the security of document signed in the past even if their secret key is exposed today. An adversary will not be able to forge a multi-signature unless the secret key of all the signers are compromised in the same time period, which is practically not possible. Further, we propose two types of Forward-Secure multi-signatures : Forward-Secure Parallel multi-signatures and Forward-Secure Serial multi-signatures. Once a user switches to use forward-secure signatures in place of ordinary signatures, he can easily extend it to use it as a multi-signature. In all applications where parallel or serial multi-signatures are used, the corresponding forward-secure multi-signatures can be used.