Improved Efficient Forward Secure Signature Scheme

B. Alomair, K. Sampigethaya and R. Poovendran proposed a generic method to construct forward secure signature schemes from standard signature schemes in EuroPKI 2008 workshop. They propose a forward secure signature scheme (ASP scheme) based on Schnorr signature scheme which is used as a black box. In this paper, we analyze the security of ASP scheme and show an attack to point out that this scheme doesn´t satisfy the forward security. Then we modify and improve ASP scheme to overcome the shortcoming. Our scheme can resist to the attack and satisfies the forward security. The most prominent performance of our scheme is that it has the most efficient key update of all known schemes, only running just a hash function once. The security of the modified forward secure signature scheme can be proved to be equivalent to the discrete logarithm problem.