An Efficient Forward Secure Signature Scheme

Introduction Exposureofsecretkeysthreatensthesecurity ofadigitalsignaturegreatly.Totacklethisprob-lem,severaldifferentmethodshavebeenpro-posed,includingsecretsharing1],thresholdsigna-ture2],andproactivesignature3].Thesemethods,however,needcooperativeandinteractivecompu-tationsinmultiplesevers,whicharequitecostly.Forwardsecuresignatureschemecanreducethe damageofkeyexposurewithoutcooperativeand interactivecomputations.Intheparadigmoffor-wardsecuresignature,thewholelifetimeofsigna-tureisdivid…

An Efficient Forward Secure Signature Scheme

A new efficient forward secure signature scheme based on bilinear pairings is presented in this paper. Each complexity of key generation, key update, signing and verifying algorithms in this scheme is O(1) in terms of the total number of time periods T. Because a new structure in node secret key storage and a unique strategy in key update are employed, the signing and verifying costs don't grow when T increases. At the same time, the key generation and key update algorithms are efficiently constructed thanks to using the pre-order traversal technique of binary trees. Compared with other schemes based on bilinear pairings, the signature size in this scheme is very short, which doesn't change with T increasing. The scheme is forward secure in random oracle model assuming CDH problem is hard.