A fast forward-secure signature scheme based on DL with unlimited number of key-updating

摘要

We present a fast forward-secure signature scheme in which the number of key-updating is practically unlimited. Our solution to unlimited key-updating is essentially different from and much simpler than the solution of the tree-like digital signature scheme proposed recently in [4], which is the first efficient forward-secure signature scheme with an exponentially-bounded number of key-updating. The scheme we propose is as fast as the original Schnorr signature scheme, and can be proven forward-secure in the random oracle model under the discrete logarithm assumption. The size of all the objects for the scheme, such as the public-key, the secret-key and the signatures, is independent of the number of key-updating, except for the signer's inner list of indexes to past periods in which signatures are issued. The list of indexes does not have to be kept secret and are not used except for the case of revocation.