An Efficient and Flexible Forward-Secure Signature Scheme

[[abstract]]In 2001, Itkis and Reyzin proposed the first forward-secure signature scheme in which both the signing and the verifying are as efficient as the underlying ordinary signature scheme. However,their method will require to generate many larger primes for keys, and key update algorithm is very slow, making it impractical for some applications. This paper proposes a new efficient method to implement the forward-secure signature. The proposed method can solve the problem raised by Itkis and Reyzin?s scheme of finding many larger primes and the efficiency of this method is the same as the underlying signature scheme. In the proposed scheme, no modular exponentiation and inverse computations are required for the key update algorithm. Moreover, only four modular multiplications, three modular additions and two hashing computations are performed by the key update procedure. That is more efficient than Itkis and Reyzin?s key update algorithm. Comparing with the existing forward-secure signature schemes in the literatures, the proposed scheme reduces a large of computations for the key update procedure. Hence, the fast key update algorithm could be used for electronic checkbook application. Furthermore, in our scheme, the total number of time periods T could be extended to T+1 or more periods, and the storage space to store its keys and signatures is almost the same as in those ordinary signature schemes. Thus, the proposed scheme is more practical and has lower limitations